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

colourful linear programmingstrongly NP-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) 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

(31)

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

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)