I detta dokument ger vi nya resultat för det set cover problemet i den fullt dynamiska modellen. I denna modell, den uppsättning "aktiva" element som ska omfattas förändringar över tiden. Målet är att upprätthålla en nästan optimal lösning för de nuvarande aktiva elementen, samtidigt som man gör få ändringar i varje tidssteg. Denna modell är populär i både dynamiska och online-algoritmer: i det förra, är målet att minimera uppdateringstiden för lösningen, medan i det senare, tillvägagångssättet (antal förändringar) begränsas. Vi presenterar generiska tekniker för den dynamiska uppsättningen omslag problem inspirerad av den klassiska giriga och primal-dual o ine algoritmer för set omslag. Det förstnämnda leder till ett konkurrensförhållande mellan O(log n t ), där n t är antalet för närvarande aktiva element vid tidssteg t, medan det senare ger konkurrensförhållanden beroende på f t, det maximala antalet uppsättningar som ett för närvarande aktivt element tillhör. Vi visar att dessa tekniker är användbara för att uppnå snäva resultat i båda inställningarna: uppdatera tidsgränser och begränsad användning, uppvisar algoritmiska tekniker som är gemensamma för dessa två parallella trådar av forskning. • Teori för beräkning → Online-algoritmer; KEYWORDS Ställ in omslag, anrop, dynamiska algoritmer, konkurrensförhållande, online-algoritmer, vertex-omslag, grafmatchning, hypergraph matchning.
En annan version av online set cover problem är i den helt dynamiska modellen, som presenteras i REF, där element anländer och också avgår.
Online and dynamic algorithms for set cover
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}