Detta dokument motiveras av att många system måste underhållas kontinuerligt medan de underliggande kostnaderna förändras över tiden. Utmaningen är då att kontinuerligt upprätthålla nära-optimala lösningar på de underliggande optimeringsproblemen, utan att skapa för mycket curn i själva lösningen. Vi modellerar detta som ett flerstegskombinatoriskt optimeringsproblem där inmatningen är en sekvens av kostnadsfunktioner (en för varje steg); medan vi kan ändra lösningen från steg till steg, får vi en extra kostnad för varje sådan förändring. Vi studerar först flerstegs matroid underhållsproblem, där vi behöver behålla en bas av en matroid i varje gång steg under ändrade kostnadsfunktioner och anskaffningskostnader för att lägga till nya element. Online-versionen av detta problem generaliserar onine personsökning, och är ett välstrukturerat fall av de metriska uppgiftssystem. E.g., med tanke på en graf, vi måste upprätthålla en spännvidd träd Tt vid varje steg: vi betalar ct(Tt) för kostnaden för trädet vid tidpunkten t, och även  till Tt\ Tt-1 till antalet kanter ändras vid detta steg. Vårt huvudsakliga resultat är en polynom tid O (log m log r)-tillnärmning till online flerstegs matroid underhållsproblem, där m är antalet element/kanter och r är rangen av matroiden. Detta förbättrar resultaten av Buchbinder et al. [7] som hanterade den delmässiga versionen av detta problem under enhetliga anskaffningskostnader, och Buchbinder, Chen och Naor [8] som studerade den delmässiga versionen av ett mer allmänt problem. Vi ger också en O(log m) approximation för offline-versionen av problemet. Dessa gränser håller när förvärvskostnaderna är icke-uniform, i vilket fall båda dessa resultat är det bästa möjliga om inte P=NP. Vi studerar också den perfekta matchande versionen av problemet, där vi måste upprätthålla en perfekt matchning vid varje steg under ändrade kostnadsfunktioner och kostnader för att lägga till nya element. Förvånansvärt nog ökar hårdheten drastiskt: för varje konstant ε > 0, det finns ingen O(n 1−ε )- tillnärmning till flerstegs matchande underhållsproblem, även i offline fallet.
Gupta m.fl. REF studerade flerstegs underhåll Matroid problem för både offline och online-inställningar.
Changing Bases: Multistage Optimization for Matroids and Matchings
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}