NDLI: A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization

Content Provider	IEEE Xplore Digital Library
Author	Yin Tat Lee Sidford, A. Sam Chiu-Wai Wong
Copyright Year	2015
Description	Author affiliation: Dept. of EECS, MIT, Cambridge, MA, USA (Sidford, A.) \|\| Dept. of Math., MIT, Cambridge, MA, USA (Yin Tat Lee) \|\| Dept. of EECS, UC Berkeley, Berkeley, CA, USA (Sam Chiu-Wai Wong)
Abstract	In this paper we improve upon the running time for finding a point in a convex set given a separation oracle. In particular, given a separation oracle for a convex set K ⊂ $R^{n}$ that is contained in a box of radius R we show how to either compute a point in K or prove that K does not contain a ball of radius ϵ using an expected O(n log(nR/ϵ)) evaluations of the oracle and additional time $O(n^{3}$ $log^{O(1)}(nR/ϵ)).$ This matches the oracle complexity and improves upon the $O(n^{ω+1}$ log(nR/ϵ)) additional time of the previous fastest algorithm achieved over 25 years ago by Vaidya [91] for the current value of the matrix multiplication constant w <; 2.373 [98], [36] when R/ϵ = O(poly(n)). Using a mix of standard reductions and new techniques we show how our algorithm can be used to improve the running time for solving classic problems in continuous and combinatorial optimization. In particular we provide the following running time improvements: · Submodular Function Minimization: n is the size of the ground set, M is the maximum absolute value of function values and EO is the time for function evaluation. Our weakly and strongly polynomial time algorithms have a running time of $O(n^{2}$ log nM · EO + $n^{3}$ $log^{O(1)}$ nM) and $O(n^{3}$ $log^{2}$ n · EO + $n^{4}$ $log^{O(1)}$ n), improving upon the previous best of $O((n^{4}$ · EO + $n^{5})logM)$ and $O(n^{5}$ · EO + $n^{6})$ respectively. · Submodular Flow: n = \|V\|, m = \|E\|, C is the maximum edge cost in absolute value and U is maximum edge capacity in absolute value. We obtain a faster weakly polynomial running time of $O(n^{2}$ log nCU · EO + $n^{3}$ logO(1) nCU), improving upon the previous best of $O(mn^{5}$ log nU · EO) and O $(n^{4}h$ min {log C, log U}) from 15 years ago by a factor of $Õ(n^{4}).$ We also achieve faster strongly polynomial time algorithms as a consequence of our result on submodular minimization. · Matroid Intersection: n is the size of the ground set, r is the maximum size of independent sets, M is the maximum absolute value of element weight, $T_{rank}$ and $T_{ind}$ are the time for each rank and independence oracle query. We obtain a running time of O((nr $log^{2}$ $nT_{rank}+n^{3}$ $log^{O(1)}$ n) log nM) and $O((n^{2}$ log $nT_{ind}+n^{3}$ $log^{O(1)}$ n) log nM), achieving the first quadratic bound on the query complexity for the independence and rank oracles. In the unweighted case, this is the first improvement since 1986 for independence oracle. · Semidefinite Programming: n is the number of constraints, m is the number of dimensions and S is the total number of non-zeros in the constraint matrices. We obtain a running time of $O(n(n^{2}$ + $m^{ω}$ + S)), improving upon the previous best of $Õ(n(n^{ω}$ + $m^{ω}$ + S)) for the regime S is small.
Starting Page	1049
Ending Page	1065
File Size	319986
Page Count	17
File Format	PDF
ISBN	9781467381918
ISSN	02725428
DOI	10.1109/FOCS.2015.68
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-10-17
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Ellipsoids Optimization Algorithm design and analysis Complexity theory Polynomials Convex functions Minimization Semidefinite Programming Cutting Plane Method Ellipsoid Method Submodular Function Minimization Submodular Flow Matroid Intersection
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in