Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints

DOI10.1137/0804004zbMath0808.90105OpenAlexW1993161326MaRDI QIDQ4294745

Michael D. Grigoriadis, Leonid G. Khachiyan

Publication date: 18 May 1994

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0804004

zbMATH Keywords

parallel computation approximate solution large-scale convex programming exponential potential function reduction technique

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Transportation, logistics and supply chain management (90B06) Parallel numerical computation (65Y05)

Related Items (20)

Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time ⋮ A sublinear-time randomized approximation algorithm for matrix games ⋮ Drawings of graphs on surfaces with few crossings ⋮ Faster and simpler approximation algorithms for mixed packing and covering problems ⋮ Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence ⋮ Barrier subgradient method ⋮ Unnamed Item ⋮ Approximation algorithms for general packing problems and their application to the multicast congestion problem ⋮ Fast approximation of minimum multicast congestion – Implementation VERSUS Theory ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ Memory-Efficient Structured Convex Optimization via Extreme Point Sampling ⋮ A generalized approximation framework for fractional network flow and packing problems ⋮ Mobile facility location: combinatorial filtering via weighted occupancy ⋮ Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem ⋮ Faster min-max resource sharing in theory and practice ⋮ An approximation algorithm for the general max-min resource sharing problem ⋮ Sparse Approximate Solutions to Semidefinite Programs ⋮ Rounding of convex sets and efficient gradient methods for linear programming problems ⋮ Packing trees in communication networks ⋮ A penalty function heuristic for the resource constrained shortest path problem

This page was built for publication: Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints