자료유형  

 학위논문

Control Number  

0016934520

International Standard Book Number  

9798380482769

Dewey Decimal Classification Number  

515

Main Entry-Personal Name  

Liu, Yang.

Publication, Distribution, etc. (Imprint  

[S.l.] : Stanford University., 2023

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2023

Physical Description  

1 online resource(302 p.)

General Note  

Source: Dissertations Abstracts International, Volume: 85-04, Section: B.

General Note  

Advisor: Sidford, Aaron;Vondrak, Jan;Charikar, Moses.

Dissertation Note  

Thesis (Ph.D.)--Stanford University, 2023.

Restrictions on Access Note  

This item must not be sold to any third party vendors.

Summary, Etc.  

요약This thesis designs efficient algorithms for combinatorial and continuous optimization problems. By combining new techniques developed in this thesis pertaining to iterative methods, dynamic algorithms, and high-dimensional geometry, we give an almost-linear-time algorithm that computes an exact maximum flow and minimum cost flows in directed graphs. Our insights lead to algorithms for broader classes of combinatorial and continuous optimization problems including online discrepancy minimization, regression, and dynamic maxflow.In the first part of the thesis we study iterative methods, which are procedures which solve an optimization problem through a sequence of simpler subproblems. By understanding the geometry of the underlying optimization problem, we give iterative methods with improved convergence rates and runtimes for the problems of ℓpregression, maximum flow, and mincost flow.In the second part of the thesis we study dynamic algorithms and online optimization which naturally arise from studying iterative methods. In particular, we give the improved algorithms that maintain an approximate maximum flow in dynamic graphs undergoing edge insertions, and also nearly-optimal algorithms for minimizing the discrepancy of vectors arriving online.In the third part of the thesis, we study sparsification problems motivated by high-dimensional geometry. The goal of sparsification is to reduce the size of an objective while approximately maintaining the desired properties, such as the value on all inputs. We give improved and nearlyoptimal size bounds for sparsification of several objectives including spectral hypergraph energies and sums of symmetric submodular functions. Finally, we give nearly-linear size bounds for sparsification of generalized linear models satisfying natural bounds on their growth, which imply nearly-optimal algorithms for solving ℓp-regression for p ∈ (1, 2].This thesis contains material from the papers [KLS20,ALS21,LSS22,CKL+22, JLS22b, JLS22a, BLS23, JLLS23b, JLLS23a].

Subject Added Entry-Topical Term  

Graphs.

Subject Added Entry-Topical Term  

Iterative methods.

Subject Added Entry-Topical Term  

Convex analysis.

Subject Added Entry-Topical Term  

Design.

Subject Added Entry-Topical Term  

Linear programming.

Subject Added Entry-Topical Term  

Energy.

Subject Added Entry-Topical Term  

Geometry.

Subject Added Entry-Topical Term  

Mathematics.

Added Entry-Corporate Name  

Stanford University.

Host Item Entry  

Dissertations Abstracts International. 85-04B.

Host Item Entry  

Dissertation Abstract International

Electronic Location and Access  

로그인을 한후 보실 수 있는 자료입니다.

Control Number  

joongbu:643562