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

DOI10.1137/0804004zbMATH Open0808.90105OpenAlexW1993161326MaRDI QIDQ4294745FDOQ4294745

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

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

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)

Cited In (24)

• A generalized approximation framework for fractional network flow and packing problems
• Algorithm Theory - SWAT 2004
• Sparse Approximate Solutions to Semidefinite Programs
• Faster min-max resource sharing in theory and practice
• 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
• Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
• A penalty function heuristic for the resource constrained shortest path problem
• Faster Algorithms for Integer Programs with Block Structure
• Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence
• 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
• 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

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)