Las Vegas algorithms for linear and integer programming when the dimension is small

DOI10.1145/201019.201036zbMath0885.65063OpenAlexW1987752344WikidataQ56555512 ScholiaQ56555512MaRDI QIDQ4369872

Kenneth L. Clarkson

Publication date: 2 February 1998

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/201019.201036

zbMATH Keywords

algorithmlinear programmingconvex programminginteger linear programmingsmallest sphere

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Integer programming (90C10) Linear programming (90C05)

Related Items (45)

On polynomial kernels for sparse integer linear programs ⋮ Tight bounds on discrete quantitative Helly numbers ⋮ Random sampling in computational algebra: Helly numbers and violator spaces ⋮ Solving Linear Programming with Constraints Unknown ⋮ Unnamed Item ⋮ On the planar piecewise quadratic 1-center problem ⋮ APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS ⋮ Linear programming, the simplex algorithm and simple polytopes ⋮ THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS ⋮ A short proof of an interesting Helly-type theorem ⋮ Bipartite diameter and other measures under translation ⋮ Quantitative Tverberg theorems over lattices and other discrete sets ⋮ A subexponential bound for linear programming ⋮ A combinatorial bound for linear programming and related problems ⋮ Clarkson's algorithm for violator spaces ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ Optimal partition trees ⋮ Sublinear Bounds for a Quantitative Doignon--Bell--Scarf Theorem ⋮ Simplex Range Searching and Its Variants: A Review ⋮ The 2-center problem in three dimensions ⋮ Unnamed Item ⋮ 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 ⋮ Provably fast training algorithms for support vector machines ⋮ Unique sink orientations of grids ⋮ Violator spaces: Structure and algorithms ⋮ A quantitative Doignon-Bell-Scarf theorem ⋮ Two-variable linear programming in parallel ⋮ An optimal randomized algorithm for \(d\)-variate zonoid depth ⋮ A Newton method for linear programming ⋮ ALMOST OPTIMAL SOLUTIONS TO k-CLUSTERING PROBLEMS ⋮ A linear algorithm for integer programming in the plane ⋮ Unnamed Item ⋮ Two-variable linear programming in parallel ⋮ Polyhedral circuits and their applications ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Practical methods for shape fitting and kinetic data structures using coresets ⋮ Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization ⋮ A space decomposition-based deterministic algorithm for solving linear optimization problems ⋮ Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Streaming algorithms for extent problems in high dimensions ⋮ Optimal Algorithms for Geometric Centers and Depth ⋮ Enumerating a subset of the integer points inside a Minkowski sum

This page was built for publication: Las Vegas algorithms for linear and integer programming when the dimension is small