Ett omfattande heltal program (CIP) är ett matematiskt program av formen: där A  till R m×n ≥0, c, u R n ≥0. I online-inställningen kommer begränsningarna (dvs. raderna i begränsningsmatris A) med tiden, och algoritmen kan bara öka koordinaterna för x för att upprätthålla genomförbarheten. Som ett mellansteg, vi överväger att lösa det täckande linjära programmet (CLP) online, där kravet x  på Z n ersätts med x  på R n. Våra huvudsakliga resultat är (a) en O (log k)-konkurrenskraftig online algoritm för att lösa CLP, och (b) en O (logg k · log l)-konkurrenskraftiga randomiserade online algoritm för att lösa CIP. Här k ≤ n och l ≤ m betecknar det maximala antalet icke-nollposter i varje rad och kolumn i begränsningsmatrisen A. Genom ett resultat av Feige och Korman, är detta det bästa möjliga för polynom-tid online-algoritmer, även i det speciella fallet av set cover (där A  med 0, 1} m×n och c, u med 0, 1} n ). Den nya ingrediensen i vår strategi är att tillåta de dubbla variablerna att öka och minska under hela algoritmens gång. Vi visar att tidigare tillvägagångssätt, som antingen bara höjer dubbla variabler, eller lägre dubbletter endast inom en gissning-och-dubbel ram, inte kan ge en prestanda bättre än O(log n), även när varje begränsning bara har en enda variabel (dvs. k = 1).
Konkurrensförhållandet för att täcka linjära program förbättrades till O(log d) av Gupta och Nagarajan REF, där d ≤ n är det maximala antalet icke-noll poster i någon rad.
Approximating Sparse Covering Integer Programs Online
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}