Sammanfattning av denna webbsida: Vi ger nya approximationsalgoritmer för paketering av heltalsprogram (PIPs) genom att använda metoden för randomiserad avrundning i kombination med ändringar. Vårt första resultat är en enklare approximationsalgoritm för allmänna PIPs som matchar de mest kända gränserna, och som medger ett effektivt parallellt genomförande. Vi utvidgar också dessa resultat till en multikriteriell version av PIPs. Vårt andra resultat är för den klass av förpackning heltal program (PIPs) som är kolumn sparse, dvs., där det finns en specificerad övre gräns k på antalet begränsningar som varje variabel visas i. Vi ger en (ek + o(k))-uppskattning algoritm för k-kolumn sparse PIPs, förbättra över tidigare kända O(k 2 )-uppskattning förhållanden. Vi generaliserar också vårt resultat till fallet med att maximera icke-negativa monotona submodulära funktioner över k-kolumn sparse förpackning begränsningar, och få en e 2 k e‐1 + o(k) - approximation algoritm. När vi får detta resultat, bevisar vi en ny egenskap hos submodulära funktioner som generaliserar den fraktionerade subadditionsegendomen, som kan vara av oberoende intresse.
Vårt problem är ett specialfall av k-kolumn sparse förpackningsproblem studeras i REF, där en randomiserad approximation algoritm föreslås.
Solving Packing Integer Programs via Randomized Rounding with Alterations
{'venue': 'THEORY OF COMPUTING', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}