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

DOI10.1137/0804004MaRDI QIDQ4294745zbMATH OpenOpenAlexFDO

Authors M. 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

approximate solutionparallel computationlarge-scale convex programmingexponential potential function reduction technique

Mathematics Subject Classification ID

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

Recommendations

• An exponential‐function reduction method for block‐angular convex programs
• Approximate max-min resource sharing for structured concave optimization
• Algorithm Theory - SWAT 2004
• An approximation algorithm for the general max-min resource sharing problem

Cited in

(26)

• Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem
• Coordination Complexity of Parallel Price-Directive Decomposition
• Multicommodity network flows: A survey. II: Solution methods
• A generalized approximation framework for fractional network flow and packing problems
• Resource sharing revisited: local weak duality and optimal convergence
• Algorithm Theory - SWAT 2004
• Faster min-max resource sharing in theory and practice
• Sparse Approximate Solutions to Semidefinite Programs
• Fast approximation of minimum multicast congestion – Implementation VERSUS Theory
• Approximation algorithms for general packing problems and their application to the multicast congestion problem
• Drawings of graphs on surfaces with few crossings
• Rounding of convex sets and efficient gradient methods for linear programming problems
• A sublinear-time randomized approximation algorithm for matrix games
• Faster and simpler approximation algorithms for mixed packing and covering problems
• An approximation algorithm for the general max-min resource sharing problem
• Barrier subgradient method
• Approximate max-min resource sharing for structured concave optimization
• High-accuracy multicommodity flows via iterative refinement
• Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
• A penalty function heuristic for the resource constrained shortest path problem
• Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and =(1/)-convergence
• Faster Algorithms for Integer Programs with Block Structure
• Mobile facility location: combinatorial filtering via weighted occupancy
• Memory-efficient structured convex optimization via extreme point sampling
• Scientific contributions of Leo Khachiyan (a short overview)
• Packing trees in communication networks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4294745)