Las Vegas algorithms for linear and integer programming when the dimension is small
From MaRDI portal
Publication:4369872
DOI10.1145/201019.201036zbMATH Open0885.65063OpenAlexW1987752344WikidataQ56555512 ScholiaQ56555512MaRDI QIDQ4369872FDOQ4369872
Authors: 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
Recommendations
Numerical mathematical programming methods (65K05) Convex programming (90C25) Linear programming (90C05) Integer programming (90C10)
Cited In (55)
- Massively parallel entity matching with linear classification in low dimensional space
- Two-variable linear programming in parallel
- Linear Time Algorithms for Two- and Three-Variable Linear Programs
- Practical methods for shape fitting and kinetic data structures using coresets
- APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
- On polynomial kernels for sparse integer linear programs
- A randomized algorithm for fixed-dimensional linear programming
- A short proof of an interesting Helly-type theorem
- A combinatorial bound for linear programming and related problems
- A quantitative Doignon-Bell-Scarf theorem
- A linear algorithm for integer programming in the plane
- Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization
- Random sampling in computational algebra: Helly numbers and violator spaces
- Title not available (Why is that?)
- An optimal randomized algorithm for \(d\)-variate zonoid depth
- Enumerating a subset of the integer points inside a Minkowski sum
- Violator spaces: Structure and algorithms
- Quantitative Tverberg theorems over lattices and other discrete sets
- Optimal algorithms for geometric centers and depth
- Randomized combinatorial algorithms for linear programming when the dimension is moderately high
- Fast integer programming in fixed dimension
- THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS
- Sublinear bounds for a quantitative Doignon-Bell-Scarf theorem
- Almost optimal solutions to \(k\)-clustering problems
- Unique sink orientations of grids
- Polyhedral circuits and their applications
- Algorithms for polytope covering and approximation
- Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time
- Tight bounds on discrete quantitative Helly numbers
- A subexponential bound for linear programming
- Clarkson's algorithm for violator spaces
- Random sampling with removal
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- Bipartite diameter and other measures under translation
- A randomized sieving algorithm for approximate integer programming
- Title not available (Why is that?)
- The 2-center problem in three dimensions
- Distance problems within Helly graphs and \(k\)-Helly graphs
- Algorithmes de poursuite pour la résolution de programmes (linéaires) en nombres entiers
- Helly’s theorem: New variations and applications
- Small-dimensional linear programming and convex hulls made easy
- Two-variable linear programming in parallel
- On the planar piecewise quadratic 1-center problem
- Provably fast training algorithms for support vector machines
- Simplex Range Searching and Its Variants: A Review
- Near-linear algorithms for geometric hitting sets and set covers
- Optimal partition trees
- A Newton method for linear programming
- A space decomposition-based deterministic algorithm for solving linear optimization problems
- On the efficient use of the architecture of a small computer for LP algorithms
- Linear programming, the simplex algorithm and simple polytopes
- Streaming algorithms for extent problems in high dimensions
- Linear Programming in Linear Time When the Dimension Is Fixed
- Helly numbers of algebraic subsets of \(\mathbb{R}^{d}\) and an extension of Doignon's theorem
- Solving linear programming with constraints unknown
This page was built for publication: Las Vegas algorithms for linear and integer programming when the dimension is small
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4369872)
