An update-and-stabilize framework for the minimum-norm-point problem

DOI10.1007/978-3-031-32726-1_11zbMath1528.90175arXiv2211.02560OpenAlexW4377200033MaRDI QIDQ6085996

László A. Végh, Satoru Fujishige, Tomonari Kitahara

Publication date: 9 November 2023

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2211.02560

Mathematics Subject Classification ID

Quadratic programming (90C20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Zonotopes and the LP-Newton method
• A strongly polynomial minimum cost circulation algorithm
• A primal-dual interior point method whose running time depends only on the constraint matrix
• New characterizations of Hoffman constants for systems of linear constraints
• Linear convergence of first order methods for non-strongly convex optimization
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• A Nearest Point Algorithm for Convex Polyhedral Cones and Applications to Positive Linear Approximation.
• Finding the nearest point in A polytope
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Learning with Submodular Functions: A Convex Optimization Perspective