Abstrakt. Vi studerar ett brett spektrum av problem med online-graf och nätverksoptimering, med fokus på problem som uppstår i studien av konnektivitet och skärningar i grafer. I ett generellt online nätverk design problem, har vi ett kommunikationsnätverk känt för algoritmen i förväg. Vad som inte är känt Tillstånd att göra digitala eller hårda kopior av delar eller allt detta arbete för personligt bruk eller klassrum beviljas utan avgift under förutsättning att kopior inte görs eller distribueras för vinst eller direkt kommersiell fördel och att kopior visar detta meddelande på första sidan eller första skärmen av en display tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Behörighet kan begäras från publikationsavdelningen., ACM, Inc., 2 Penn Plaza, Suite 701 New York, NY 10121-0701 USA, fax +1 (212) 869-0481, eller behörigheter@acm.org.  En allmän strategi för online-nätverk Optimering Problem i förväg är konnektivitet (bandbredd) eller minska kraven mellan hörn i nätverket som anländer online. Vi utvecklar ett enhetligt ramverk för att utforma online-algoritmer för problem som rör konnektivitet och nedskärningar. Vi presenterar först en allmän O(log m)-konkurrenskraftig deterministisk algoritm för att generera en fraktionerad lösning som uppfyller online-anslutningen eller skära krav, där m är antalet kanter i grafen. Detta kan vara av oberoende intresse för att lösa problem med delad bandbredd online, och är tillämpligt på både riktade och oriktade grafer. Vi visar sedan hur vi kan få fram integrerade lösningar via en online-avrundning av den fraktionerade lösningen. Denna del av ramverket är problemberoende, och tillämpar olika verktyg inklusive resultat på ungefärligt maxflöde min-cut för multicommodity flow, Hierarchical Separated Trees (HST) metod och dess förlängningar, vissa avrundning tekniker för beroende variabler, och Räckes nya hierarkiska nedbrytning av grafer. Specifikt, våra resultat för det integrala fallet inkluderar en O (log m log n)-konkurrenskraftiga randomiserade algoritm för online icke-metrisk anläggning plats problem och för en generalisering av problemet som kallas multicast problem. I den icke-metriska anläggningens lokaliseringsproblem är m antalet anläggningar och n antalet kunder. Konkurrensförhållandet är nästan jämnt. Vi presenterar också en O(log 2 n log k)-konkurrenskraftig randomiserad algoritm för onlinegruppen Steiner problem i träd och en O(log 3 n log k)-konkurrenskraftig randomiserad algoritm för problemet i allmänna grafer, där n är antalet hörn i grafen och k är antalet grupper. Slutligen utformar vi en deterministisk O(log 3 n log log n)-kompetitiv algoritm för online multi-cut problem.
I REF utförs den första fasen med en allmän O(log n)-konkurrensmetod som är tillämplig på en bred klass av online-grafoptimeringsproblem.
A general approach to online network optimization problems
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}