Colourful Linear Programming and its Relatives

DOI10.1287/moor.22.3.550zbMath0887.90111OpenAlexW1994709142MaRDI QIDQ4361784

Shmuel Onn, Imre Bárány

Publication date: 28 October 1997

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.22.3.550

zbMATH Keywords

strongly NP-completecolourful linear programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items (28)

Examples with decreasing largest inscribed ball for deterministic rescaling algorithms ⋮ Computing colourful simplicial depth and Median in \(\mathbb{R}_2\) ⋮ Enumerating trichromatic triangles containing the origin in linear time ⋮ A colorful theorem on transversal lines to plane convex sets ⋮ Carathéodory, Helly and the others in the max-plus world ⋮ A note on lower bounds for colourful simplicial depth ⋮ Quantitative Tverberg theorems over lattices and other discrete sets ⋮ Tropical Carathéodory with matroids ⋮ The colorful Helly theorem and general hypergraphs ⋮ Algorithms for Colourful Simplicial Depth and Medians in the Plane ⋮ Extensions of the colorful Helly theorem for d-collapsible and d-Leray complexes ⋮ More colourful simplices ⋮ The intersection of a matroid and an oriented matroid ⋮ Colorful linear programming, Nash equilibrium, and pivots ⋮ Helly’s theorem: New variations and applications ⋮ Robust Tverberg and Colourful Carathéodory Results via Random Choice ⋮ The colourful feasibility problem ⋮ Tverberg plus minus ⋮ Computational aspects of the colorful Carathéodory theorem ⋮ Quantitative combinatorial geometry for continuous parameters ⋮ Notes about the Carathéodory number ⋮ Radon numbers and the fractional Helly theorem ⋮ Tverberg’s theorem is 50 years old: A survey ⋮ The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential ⋮ A quadratic lower bound for colourful simplicial depth ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ The Colorful Helly Property for Hypergraphs ⋮ No-dimensional Tverberg theorems and algorithms

This page was built for publication: Colourful Linear Programming and its Relatives