Många kombinatoriska optimeringsproblem (knapsack, maximal vikt matchning, etc.) kan uttryckas som delmängd maximering problem: En ges en grunduppsättning N = {1,..., n}, en samling F  på 2 N av delmängder därav sådan att ∅  på F, och en objektiv (vinst) funktion p : F → R+. Uppgiften är att välja en uppsättning S  på F som maximerar p(S). Vi anser att flerstegsversionen (Eisenstat et al., Gupta et al., båda ICALP 2014) av sådana problem: Vinstfunktionen pt (och möjligen uppsättningen av genomförbara lösningar Ft) kan förändras över tid. Eftersom det i många applikationer är kostsamt att ändra lösningen blir uppgiften att hitta en sekvens av lösningar som optimerar avvägningen mellan bra per-time-lösningar och stabila lösningar med hänsyn till en ytterligare likhetsbonus. Som likhetsmått för två på varandra följande lösningar betraktar vi antingen storleken på skärningspunkten mellan de två lösningarna eller skillnaden mellan n och hammingavståndet mellan de två karakteristiska vektorerna. Vi studerar flera steg delmängd maximering problem i online-inställningen, det vill säga pt (tillsammans med möjligen Ft) endast anländer en efter en och, vid en sådan ankomst, online algoritmen har att producera motsvarande lösning utan kunskap om framtiden. Vi utvecklar generella tekniker för flerstegsundergruppsmaximering online och därmed karakteriserar de modeller (som ges av typen av datautveckling och typen av likhetsmått) som medger en konstant konkurrenskraftig onlinealgoritm. När inget konstant konkurrensförhållande är möjligt, använder vi oss av siktet framåt för att kringgå denna fråga. När ett konstant konkurrensförhållande är möjligt, ger vi nästan matchande lägre och övre gränser på den bästa möjliga.
I REF utvecklas allmänna tekniker för en familj av flerstegsproblem online, som kallas Subset Maximization, och därmed karakteriseras modellerna (som ges av typen av datautveckling och typ av likhetsmått) som medger en konstant konkurrenskraftig online-algoritm.
Online Multistage Subset Maximization Problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}