Nearly linear-time packing and covering LP solvers

Zeyuan Allen-Zhu, Lorenzo Orecchia

Type: Article

Publication Date: 2018-02-13

Citations: 16

DOI: https://doi.org/10.1007/s10107-018-1244-x

View Publication

Download PDF

Locations

Mathematical Programming - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Nearly Linear-Time Packing and Covering LP Solvers	2014	Zeyuan Allen-Zhu Lorenzo Orecchia
+	Nearly Linear-Time Packing and Covering LP Solvers	2014	Zeyuan Allen-Zhu Lorenzo Orecchia
+	Faster width-dependent algorithm for mixed packing and covering LPs	2019	Digvijay Boob Saurabh Sawlani Di Wang
+	Solving Packing and Covering LPs in $\tilde{O}(\frac{1}{ε^2})$ Distributed Iterations with a Single Algorithm and Simpler Analysis	2017	Jelena Diakonikolas Lorenzo Orecchia
+	Nearly-Linear Time Packing and Covering LP Solver with Faster Convergence Rate Than $O(1/\varepsilon^2)$.	2014	Zeyuan Allen Zhu Lorenzo Orecchia
+	Solving Packing and Covering LPs in $\tilde{O}(\frac{1}{\epsilon^2})$ Distributed Iterations with a Single Algorithm and Simpler Analysis	2017	Jelena Diakonikolas Lorenzo Orecchia
+	Solving Packing and Covering LPs in Õ(1/ε 2 ) Distributed Iterations with a Single Algorithm and Simpler Analysis.	2017	Jelena Diakonikolas Lorenzo Orecchia
+ PDF Chat	On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility	2013	Stefan Kratsch
+	Faster and simpler approximation algorithms for mixed packing and covering problems	2007	DiedrichFlorian JansenKlaus
+	Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction	2015	Di Wang Satish Rao Michael W. Mahoney
+ PDF Chat	A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs	2013	Christos Koufogiannakis Neal E. Young
+	On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility	2013	Stefan Kratsch
+	On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility	2013	Stefan Kratsch
+	Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs	2021	Khaled Elbassioni Kazuhisa Makino
+	On Approximating (Sparse) Covering Integer Programs	2018	Chandra Chekuri Kent Quanrud
+ PDF Chat	Approximating Sparse Covering Integer Programs Online	2014	Anupam Gupta Viswanath Nagarajan
+	$\ell_1$-sparsity Approximation Bounds for Packing Integer Programs	2019	Chandra Chekuri Kent Quanrud Manuel R. Torres
+	$\ell_1$-sparsity Approximation Bounds for Packing Integer Programs	2019	Chandra Chekuri Kent Quanrud Manuel R. Torres
+	Nearly linear-work algorithms for mixed packing/covering and facility-location linear programs	2016	Neal E. Young
+	Nearly Linear-Work Algorithms for Mixed Packing/Covering and Facility-Location Linear Programs	2014	Neal E. Young

Works That Cite This (12)

Action	Title	Year	Authors
+ PDF Chat	Towards optimal running times for optimal transport	2023	José Blanchet Arun Jambulapati Carson Kent Aaron Sidford
+ PDF Chat	Spencer's theorem in nearly input-sparsity time	2023	Vishesh Jain Ashwin Sah Mehtaab Sawhney
+	Distributionally robust optimization with marginals : theory and applications	2019	Louis Lester. Chen
+ PDF Chat	Hidden Hamiltonian Cycle Recovery via Linear Programming	2020	Vivek Bagaria Jian Ding David Tse Yihong Wu Jiaming Xu
+	Faster width-dependent algorithm for mixed packing and covering LPs	2019	Digvijay Boob Saurabh Sawlani Di Wang
+ PDF Chat	Advance Service Reservations with Heterogeneous Customers	2019	Clifford Stein Van‐Anh Truong Xinshang Wang
+	Semi-Streaming Bipartite Matching in Fewer Passes and Less Space.	2020	Yujia Jin Aaron Sidford Kevin Tian
+	Advance Service Reservations with Heterogeneous Customers	2018	Clifford Stein Van‐Anh Truong Xinshang Wang
+ PDF Chat	Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching	2023	Da Wei Zheng Monika Henzinger
+	Simple Combinatorial Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs.	2021	Adir Morgan Shay Solomon Nicole Wein

Works Cited by This (16)

Action	Title	Year	Authors
+	Accelerated, Parallel, and Proximal Coordinate Descent	2015	Olivier Fercoq Peter Richtárik
+	A parallel approximation algorithm for positive linear programming	1993	Michael Luby Noam Nisan
+ PDF Chat	Prox-Method with Rate of Convergence <i>O</i>(1/<i>t</i>) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems	2004	Arkadi Nemirovski
+ PDF Chat	Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems	2012	Yu. Nesterov
+	Rounding of convex sets and efficient gradient methods for linear programming problems	2007	Yu. Nesterov
+ PDF Chat	A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs	2013	Christos Koufogiannakis Neal E. Young
+ PDF Chat	Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel	2014	Zeyuan Allen-Zhu Lorenzo Orecchia
+ PDF Chat	Smooth minimization of non-smooth functions	2004	Yu. Nesterov
+	Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver	2016	Zeyuan Allen-Zhu Yin Tat Lee Lorenzo Orecchia
+	Even faster accelerated coordinate descent using non-uniform sampling	2016	Zeyuan Allen-Zhu Zheng Qu Peter Richtárik Yuan Yang