Classes of linear programs solvable by coordinate-wise minimization

DOI10.1007/s10472-021-09731-9zbMath1492.90078OpenAlexW4238305491MaRDI QIDQ2163850

Tomáš Dlask, Tomáš Werner

Publication date: 11 August 2022

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-021-09731-9

zbMATH Keywords

linear programmingLP relaxationcoordinate-wise minimization

Mathematics Subject Classification ID

Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Duality theory (optimization) (49N15)

Related Items (1)

Activity propagation in systems of linear inequalities and its relation to block-coordinate descent in linear programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Diffusion algorithms and structural recognition optimization problems
• Understanding and using linear programming
• Primal-dual algorithms for the assignment problem
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• Approximating a generalization of MAX 2SAT and MIN 2SAT
• A taxonomy and evaluation of dense two-frame stereo correspondence algorithms
• An efficient cost scaling algorithm for the assignment problem
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Algorithms and codes for dense assignment problems: The state of the art
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• Coordinate descent algorithms
• Linear-Time Approximation for Maximum Weight Matching
• A Sufficient Condition for Backtrack-Free Search
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• The Minimum Satisfiability Problem
• LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP
• Maximum matching and a polyhedron with 0,1-vertices
• Convergence of a block coordinate descent method for nondifferentiable minimization

This page was built for publication: Classes of linear programs solvable by coordinate-wise minimization