I detta dokument förbättrar vi körtiden för att hitta en punkt i ett konvext set med tanke på en separation orakel. I synnerhet, med tanke på en separation orakel för en konvex uppsättning K  på R n som finns i en ruta med radien R visar vi hur man antingen beräknar en punkt i K eller visar att K inte innehåller en boll av radie med hjälp av en förväntad O(n log(nR/ )) utvärderingar av orakel och ytterligare tid O(n 3 log O(1) (nR/ )). Detta matchar oraklet komplexitet och förbättrar på O(n  på + 1 log(nR/ )) ytterligare tid av den tidigare snabbaste algoritmen som uppnåddes för över 25 år sedan av Vaidya [91] för det aktuella värdet av matrisen multiplikationskonstanten. < 2.373 Med hjälp av en blandning av standardreduceringar och nya tekniker visar vi hur vår algoritm kan användas för att förbättra körtiden för att lösa klassiska problem i kontinuerlig och kombinatorisk optimering. I synnerhet ger vi följande förbättringar körtid: • Submodulär funktion minimering: n är storleken på marken uppsättning, M är det maximala absoluta värdet av funktionsvärden och EO är tiden för funktionsutvärdering. Våra svagt och starkt polynomiska tidsalgoritmer har en drifttid på O(n • Submodulärt flöde: n =  på V, m =  på E, C är den maximala eggkostnaden i absolut värde och U är maximal eggkapacitet i absolut värde. Vi får en snabbare svagt polynom körtid av O(n 2 log nCU · EO + n 3 log O(1) NCU ), förbättring på föregående bästa av O(mn 5 log nU · EO) och O n 4 h min {log C, log U } från 15 år sedan av en faktor av O(n 4). Vi uppnår också snabbare starkt polynom tid algoritmer som en följd av vårt resultat på submodulär minimering. • Matroid Intersektion: n är storleken på marken uppsättning, r är den maximala storleken på oberoende uppsättningar, M är det maximala absoluta värdet av elementets vikt, Trank och Tind är tiden för varje rank och oberoende oracle fråga. Vi får en körtid av O((nr log 2 nTrank+n 3 log O(1) n) log nM ) och O(n 2 log nTind+n 3 log O(1) n) log nM ), uppnå den första quadratic bunden på frågan komplexitet för självständighet och rank oracles. I det oviktade fallet är detta den första förbättringen sedan 1986 för oberoende orakel. • Halvdefinierad programmering: n är antalet begränsningar, m är antalet dimensioner och S är det totala antalet icke-nollvärden i begränsningsmatriserna. Vi får en körtid på Õ (n(n 2 + m + S)), förbättring på det tidigare bästa av Õ (n(n  och m + S)) för regimen S är liten.
För en submodulär funktion över n objekt, den nuvarande bästa allmänna algoritmen kräver  på (n 2 ) oracle frågor REF.
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
{'venue': '2015 IEEE 56th Annual Symposium on Foundations of Computer Science', 'journal': '2015 IEEE 56th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}