Colourful Linear Programming and its Relatives

DOI10.1287/MOOR.22.3.550MaRDI QIDQ4361784zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Colourful linear programming
• Colorful linear programming, Nash equilibrium, and pivots
• The colourful feasibility problem
• Computational aspects of the colorful Carathéodory theorem
• The rainbow at the end of the line -- a \textsf{PPAD} formulation of the colorful Carathéodory theorem with applications

Cited in

(30)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4361784)