Vi omtolkar några online giriga algoritmer för en klass av icke-linjära "load-balancing" problem som att lösa ett matematiskt program på nätet. Till exempel, vi anser problemet med att tilldela jobb till (orelaterade) maskiner för att minimera summan av α th - potenser av laster plus tilldelningskostnader (den online Generalized Inmission Problem); eller välja vägar för att ansluta terminalpar för att minimera α th -powers av kanten laster (dvs. online routing med hastighetsskalbara routrar). Vi ger analyser av dessa online-algoritmer med hjälp av dubbla av det primära programmet som en lägre gräns för den optimala algoritmen, mycket i andan av online primal-dual resultat för linjära problem. Vi konstaterar sedan att en bred klass av problem med en processor hastighetsskalning (med i huvudsak godtyckliga schemaläggningsmål) kan ses som sådana problem med belastningsbalansering med linjära tilldelningskostnader. Denna anslutning ger nya algoritmer för problem som hade motstått lösningar med hjälp av de dominerande potentiella funktionsmetoder som används i hastighetsskalningslitteraturen, samt alternativa, renare bevis för andra kända resultat.
Gupta m.fl. REF gav en primal-dual algoritm för en allmän klass av schemaläggning problem med kostnadsfunktion f (z) = z α.
Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}