Violator Spaces: Structure and Algorithms

DOI10.1007/11841036_36MaRDI QIDQ5449544zbMATH OpenOpenAlexFDO

Authors Leo Rüst, P. Škovroň, B. Gärtner, Jiří Matoušek

Publication date 11 March 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Randomized algorithms (68W20) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Abstract: Sharir and Welzl introduced an abstract framework for optimization problems, called LP-type problems or also generalized linear programming problems, which proved useful in algorithm design. We define a new, and as we believe, simpler and more natural framework: violator spaces, which constitute a proper generalization of LP-type problems. We show that Clarkson's randomized algorithms for low-dimensional linear programming work in the context of violator spaces. For example, in this way we obtain the fastest known algorithm for the P-matrix generalized linear complementarity problem with a constant number of blocks. We also give two new characterizations of LP-type problems: they are equivalent to acyclic violator spaces, as well as to concrete LP-type problems (informally, the constraints in a concrete LP-type problem are subsets of a linearly ordered ground set, and the value of a set of constraints is the minimum of its intersection).

Recommendations

• Violator spaces: Structure and algorithms
• Clarkson's algorithm for violator spaces
• Violator spaces vs closure spaces
• Some randomized algorithms for convex quadratic programming
• Low-Dimensional Linear Programming with Violations

Cited in

(8)

• Removing degeneracy in LP-type problems revisited
• k-violation linear programming
• Violator spaces vs closure spaces
• Removing degeneracy may require unbounded dimension increase
• Clarkson's algorithm for violator spaces
• Cospanning characterizations of violator and co-violator spaces
• Property testing of LP-type problems
• Violator spaces: Structure and algorithms

This page was built for publication: Violator Spaces: Structure and Algorithms

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