Using separation algorithms in fixed dimension

DOI10.1016/0196-6774(92)90006-XMaRDI QIDQ3990616zbMATH OpenFDO

Authors Carolyn Haibt Norton, Éva Tardos, Serge Plotkin

Publication date 28 June 1992

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(92)90006-X

zbMATH Keywords

concurrent multi-commodity flow problemseparationstrongly polynomial algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Recommendations

• Equivalence of \(\varepsilon\)-approximate separation and optimization in fixed dimensions.
• Convex separable optimization is not much harder than linear optimization
• Linear Programming in Linear Time When the Dimension Is Fixed
• A polynomial-time descent method for separable convex optimization problems with linear constraints
• Publication:4886036

Cited in

(9)

• Decomposable multi-parameter matroid optimization problems.
• Optimization with additional variables and constraints
• An efficient, strongly polynomial, -approximation parametric optimization scheme
• Generalized max flows and augmenting paths
• Optimal algorithms for separating a polyhedron from its single-part mold
• Weighted search in the plane
• (Near)-optimal algorithms for sparse separable convex integer programs
• A combinatorial approximation algorithm for concurrent flow problem and its application
• A fast polynomial time algorithm for logistics network flows

This page was built for publication: Using separation algorithms in fixed dimension

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