Optimization Everywhere: Convex, Combinatorial, and Economic

Sam Wong

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2018-185

December 14, 2018

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-185.pdf

In this thesis we study fundamental problems that arise in optimization and its applications. We present provably efficient algorithms that achieve better running times or approximation guarantees than previously known. Our method draws on the toolkit from convex and combinatorial optimization as well as economics. By intertwining techniques from these disciplines, we are able to make progress on multiple old and new problems, some of which have stood open for many years. Main results of this thesis include the following:

Convex Programming: We show how to solve convex programming with an expected O(n log(nR/\epsilon)) evaluations of the separation oracle and additional time O(n^3\log^{O(1)}(nR/\epsilon)). This matches the oracle complexity and improves upon the O(n^{\omega+1}\log(nR/\epsilon)) additional time of the previous fastest algorithm achieved over 25 years ago for the current value of the matrix multiplication constant when R/\epsilon=O(\poly(n)).

Submodular Function Minimization: We provide new weakly and strongly polynomial time algorithms with a running time of O(n^{2}\log nM\cdot\text{EO}+n^{3}\log^{O(1)}nM) and O(n^{3}\log^{2}n\cdot\text{EO}+n^{4}\log^{O(1)}n), improving upon the previous best of O((n^{4}\cdot\text{EO}+n^{5})\log M) and O(n^{5}\cdot\text{EO}+n^{6}) respectively. We also provide the first subquadratic time algorithm for computing an approximately optimal solution.

Matroid Intersection: We provide new algorithms with a running time of O(nr\mathcal{T_{\text{rank}}}\log n\log(nM)+n^{3}\log^{O(1)}nM) and O(n^{2}\mathcal{T_{\text{ind}}}\log(nM)+n^{3}\log^{O(1)}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.

Submodular Flow: We obtain a faster weakly polynomial running time of O(n^{2}\log(nCU)\cdot\EO+n^{3}\log^{O(1)}(nCU)), improving upon the previous best of O(mn^{5}\log(nU)\cdot\EO) and O\left(n^{4}h\min\left\{ \log C,\log U\right\} \right) from 15 years ago by a factor of \tilde{O}(n^{4}).

Semidefinite Programming: We obtain a running time of \tilde{O}(n(n^{2}+m^{\omega}+S)), improving upon the previous best of \tilde{O}(n(n^{\omega}+m^{\omega}+S)) for the regime S is small.

Market Equilibrium: We present the first polynomial time algorithm for computing market equilibrium in an economy with indivisible goods and general buyer valuations having only access to an aggregate demand oracle.

Vertex Cover with Hard Capacity: We give a f-approximation algorithm for the minimum unweighted Vertex Cover problem with Hard Capacity constraints on f-hypergraphs This improves over the previous 2f-approximation and is the best possible assuming the unique game conjecture.

Network Design for Effective Resistance: We initiate the study of network design for s-t effective resistance. Among other results we present a constant factor approximation by applying classic techniques to a convex quadratic programming relaxation.

Advisors: Christos Papadimitriou

BibTeX citation:

@phdthesis{Wong:EECS-2018-185,
    Author= {Wong, Sam},
    Title= {Optimization Everywhere: Convex, Combinatorial, and Economic},
    School= {EECS Department, University of California, Berkeley},
    Year= {2018},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-185.html},
    Number= {UCB/EECS-2018-185},
    Abstract= {In this thesis we study fundamental problems that arise in optimization and its applications. We present provably efficient algorithms that achieve better running times or approximation guarantees than previously known. Our method draws on the toolkit from convex and combinatorial optimization as well as economics. By intertwining techniques from these disciplines, we are able to make progress on multiple old and new problems, some of which have stood open for many years. Main results of this thesis include the following:

Convex Programming: We show how to solve convex programming with an expected O(n log(nR/\epsilon)) evaluations of the separation oracle and additional time 
O(n^3\log^{O(1)}(nR/\epsilon)). This matches the oracle complexity and improves upon the O(n^{\omega+1}\log(nR/\epsilon)) additional time of the previous fastest algorithm achieved over 25 years ago for the current value of the matrix multiplication constant when R/\epsilon=O(\poly(n)).

Submodular Function Minimization: We provide new weakly and strongly polynomial time algorithms with a running time of O(n^{2}\log nM\cdot\text{EO}+n^{3}\log^{O(1)}nM) and O(n^{3}\log^{2}n\cdot\text{EO}+n^{4}\log^{O(1)}n), improving upon the previous best of O((n^{4}\cdot\text{EO}+n^{5})\log M) and O(n^{5}\cdot\text{EO}+n^{6}) respectively. We also provide the first subquadratic time algorithm for computing an approximately optimal solution.

Matroid Intersection: We provide new algorithms with a running time of O(nr\mathcal{T_{\text{rank}}}\log n\log(nM)+n^{3}\log^{O(1)}nM)
and O(n^{2}\mathcal{T_{\text{ind}}}\log(nM)+n^{3}\log^{O(1)}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.

Submodular Flow: We obtain a faster weakly polynomial running time of O(n^{2}\log(nCU)\cdot\EO+n^{3}\log^{O(1)}(nCU)), improving upon the previous best of O(mn^{5}\log(nU)\cdot\EO) and O\left(n^{4}h\min\left\{ \log C,\log U\right\} \right) from 15 years ago by a factor of \tilde{O}(n^{4}).

Semidefinite Programming: We obtain a running time of \tilde{O}(n(n^{2}+m^{\omega}+S)), improving upon the previous best of \tilde{O}(n(n^{\omega}+m^{\omega}+S))
for the regime S is small.

Market Equilibrium: We present the first polynomial time algorithm for computing market equilibrium in an economy with indivisible goods and general buyer valuations having only access to an aggregate demand oracle.

Vertex Cover with Hard Capacity: We give a f-approximation algorithm for the minimum unweighted Vertex Cover problem with Hard Capacity constraints on f-hypergraphs This improves over the previous 2f-approximation and is the best possible assuming the unique game conjecture.

Network Design for Effective Resistance: We initiate the study of network design for s-t effective resistance. Among other results we present a constant factor approximation by applying classic techniques to a convex quadratic programming relaxation.},
}

EndNote citation:

%0 Thesis
%A Wong, Sam 
%T Optimization Everywhere: Convex, Combinatorial, and Economic
%I EECS Department, University of California, Berkeley
%D 2018
%8 December 14
%@ UCB/EECS-2018-185
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-185.html
%F Wong:EECS-2018-185