Abstract-Vi presenterar online-algoritmer för att täcka och packa problem med (icke-linjära) konvexa mål. Konvexa täckningsproblem definieras som: min x på R n + f (x) s.t. Ax ≥ 1, där f : R n + → R+ är en monoton konvex funktion, och A är en m × n matris med icke-negativa poster. I online-versionen, en ny rad av begränsningsmatrisen, som representerar en ny täckning begränsning, avslöjas i varje steg och algoritmen krävs för att upprätthålla en genomförbar och monotont icke-decreasing uppdrag x över tid. Vi anser också att ett konvext förpackningsproblem definieras som: + → R+ är en monoton konvex funktion. I online-versionen kommer varje variabel yj online och algoritmen måste bestämma värdet av yj vid sin ankomst. Detta representerar Fenchel dual av konvex täckande program, när g är konvex konjugat av f. Vi använder en primal-dual strategi för att ge online-algoritmer för dessa generiska problem, och använda dem för att förenkla, förena, och förbättra tidigare resultat för flera program.
Nyligen, REF anses förpackning / täcka problem med allmänna (icke-skiljbara) konvexa mål, men (som diskuterats tidigare) detta resultat kräver en monoton gradient antagande på konvex funktion.
Online Algorithms for Covering and Packing Problems with Convex Objectives
{'venue': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}