Violator spaces: Structure and algorithms

DOI10.1016/j.dam.2007.08.048zbMath1163.90651OpenAlexW2037741686MaRDI QIDQ943850

P. Škovroň, Ji{ří} Matoušek, Bernd Gärtner, Leo Rüst

Publication date: 10 September 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.08.048

zbMATH Keywords

generalized linear programmingLP-type problemviolator spacegeneralized linear complementarity problemunique sink orientationClarkson's algorithms

Mathematics Subject Classification ID

Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Randomized algorithms (68W20)

Related Items

Tight bounds on discrete quantitative Helly numbers ⋮ Random sampling in computational algebra: Helly numbers and violator spaces ⋮ Clarkson's algorithm for violator spaces ⋮ Constant-Factor Approximation for TSP with Disks ⋮ Helly numbers of algebraic subsets of \(\mathbb{R}^{d}\) and an extension of Doignon's theorem ⋮ Random sampling with removal ⋮ Helly’s theorem: New variations and applications ⋮ A quantitative Doignon-Bell-Scarf theorem ⋮ Krein-Milman spaces ⋮ Quantitative combinatorial geometry for concave functions ⋮ Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization ⋮ Deterministic Algorithms for Unique Sink Orientations of Grids ⋮ Violator spaces vs closure spaces ⋮ The complexity of optimization on grids ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

Cites Work

• Unnamed Item
• Unnamed Item
• Helly-type theorems and generalized linear programming
• Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
• Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
• On geometric optimization with few violated constraints
• A short proof of an interesting Helly-type theorem
• A subexponential bound for linear programming
• The number of unique-sink orientations of the hypercube
• Linear programming and unique sink orientations
• Unique Sink Orientations of Grids
• Jumping Doesn’t Help in Abstract Cubes
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Linear programming — Randomization and abstract frameworks
• LP-orientations of cubes and crosspolytopes
• A combinatorial bound for linear programming and related problems
• A generalization of the linear complementarity problem
• A simple sampling lemma: Analysis and applications in geometric optimization