Vi ger en algoritmisk ram för att minimera allmänna konvexa mål (som är differentiable och monoton icke-decreasing) över en uppsättning av täcka begränsningar som anländer online. Detta utvidgar avsevärt det tidigare arbetet med online-täckning för linjära mål (Alon m.fl., STOC 2003) och online-täckning med begränsningar för paketering offline (Azar m.fl., SODA 2013). Såvitt vi vet är detta det första resultatet i online-optimering för generiska icke-linjära mål; särskilda fall av sådana mål har tidigare övervägts, särskilt för energiminimering. Som ett specifikt problem i denna genre, anser vi att den orelaterade maskin schemaläggning problem med startkostnader och godtyckliga l p normer på maskinlaster (inklusive överraskande icke-trivial l 1 norm som representerar total maskinbelastning). Detta problem undersöktes tidigare för makespan normen i både offline (Khuller et al., SODA 2010; Li och Khuller, SODA 2011) och online-inställningar (Azar et al., SODA 2013). Vi anpassar den tvåfasiga metoden att få en bråkdelslösning och sedan avrunda den online (används framgångsrikt för många linjära mål) till det icke-linjära målet. Den fraktionerade algoritmen använder idéer från vårt allmänna ramverk som vi beskrev ovan (men passar inte ramverket exakt på grund av icke-positiva poster i begränsningsmatrisen). Den avrundning algoritm använder idéer från offline avrundning av LPs med icke-linjära mål (Azar och Epstein, STOC 2005; Kumar et al., FOCS 2005). Vårt konkurrensförhållande är nära en logaritmisk faktor. Slutligen, för det viktiga specialfallet av total belastning (l 1 norm), ger vi en annan avrundningsalgoritm som ger ett bättre konkurrensförhållande än den generiska avrundningsalgoritmen för l p normer. Vi visar att detta konkurrensförhållande är asymptotiskt snävt.
På grund av ett lägre bundet resultat av Azar et al. REF, vårt konkurrensförhållande är snävt.
Online Covering with Convex Objectives and Applications
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}