A combinatorial bound for linear programming and related problems

DOI10.1007/3-540-55210-3_213zbMath1494.68276OpenAlexW1789652828MaRDI QIDQ5096811

Micha Sharir, Ermo Welzl

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55210-3_213

zbMATH Keywords

linear programmingcombinatorial optimizationcomputational geometryrandomized incremental algorithms

Mathematics Subject Classification ID

Convex programming (90C25) Linear programming (90C05) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Related Items (35)

Random sampling in computational algebra: Helly numbers and violator spaces ⋮ Helly-type theorems and generalized linear programming ⋮ Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Computing the Rectilinear Center of Uncertain Points in the Plane ⋮ On geometric optimization with few violated constraints ⋮ A short proof of an interesting Helly-type theorem ⋮ Bipartite diameter and other measures under translation ⋮ Linear time algorithms for Euclidean 1-center in \(\mathfrak {R}^d\) with non-linear convex constraints ⋮ Covering points by disjoint boxes with outliers ⋮ Removing degeneracy may require unbounded dimension increase ⋮ No dimension-independent core-sets for containment under homothetics ⋮ A Meeting Scheduling Problem Respecting Time and Space ⋮ Bounding Helly Numbers via Betti Numbers ⋮ Random sampling with removal ⋮ Helly’s theorem: New variations and applications ⋮ Unnamed Item ⋮ Linear Time Algorithm for 1-Center in $$\mathfrak {R}^d$$ Under Convex Polyhedral Distance Function ⋮ Polynomial-time algorithms for energy games with special weight structures ⋮ Helly-type theorems for approximate covering ⋮ Violator spaces: Structure and algorithms ⋮ An optimal randomized algorithm for \(d\)-variate zonoid depth ⋮ Random edge can be exponential on abstract cubes ⋮ Some Discrete Properties of the Space of Line Transversals to Disjoint Balls ⋮ Krein-Milman spaces ⋮ A dual simplex-type algorithm for the smallest enclosing ball of balls ⋮ Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization ⋮ Clustering in Hilbert’s Projective Geometry: The Case Studies of the Probability Simplex and the Elliptope of Correlation Matrices ⋮ Output-sensitive results on convex hulls, extreme points, and related problems ⋮ Violator spaces vs closure spaces ⋮ Removing degeneracy in LP-type problems revisited ⋮ A characterization theorem and an algorithm for a convex hull problem ⋮ Optimal Algorithms for Geometric Centers and Depth ⋮ Efficient algorithms for the minimum diameter bridge problem ⋮ Combinatorial structure and randomized subexponential algorithms for infinite games

Cites Work

• Unnamed Item
• Über das Löwnersche Ellipsoid und sein Analogon unter den einem Eikörper einbeschriebenen Ellipsoiden
• Small-dimensional linear programming and convex hulls made easy
• A randomized algorithm for fixed-dimensional linear programming
• A subexponential bound for linear programming
• Linear programming in \(O(n\times 3^{d^2})\) time
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Linear Programming in Linear Time When the Dimension Is Fixed
• Las Vegas algorithms for linear and integer programming when the dimension is small
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem

This page was built for publication: A combinatorial bound for linear programming and related problems