The colourful feasibility problem

DOI10.1016/J.DAM.2008.01.016MaRDI QIDQ944700zbMATH OpenOpenAlexFDO

Authors Antoine Deza, Sui Huang, Tamon Stephen, Tamás Terlaky

Publication date 10 September 2008

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0511749

zbMATH Keywords

colourful feasibility problemcolourful linear programming

Mathematics Subject Classification ID

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

Abstract: We study a colourful generalization of the linear programming feasibility problem, comparing the algorithms introduced by Barany and Onn with new methods. We perform benchmarking on generic and ill-conditioned problems, as well as as recently introduced highly structured problems. We show that some algorithms can lead to cycling or slow convergence, but we provide extensive numerical experiments which show that others perform much better than predicted by complexity arguments. We conclude that the most efficient method for all but the most ill-conditioned problems is a proposed multi-update algorithm.

Recommendations

• Colourful Linear Programming and its Relatives
• Rescaling algorithms for linear conic feasibility
• Colourful linear programming
• Colorful linear programming, Nash equilibrium, and pivots
• Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem

Cites work

• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 1054763 (Why is no real title available?)
• A continuous analogue of the upper bound theorem
• A generalization of Caratheodory's theorem
• A quadratic lower bound for colourful simplicial depth
• Colourful Linear Programming and its Relatives
• Colourful simplicial depth
• Finding the nearest point in A polytope
• Quadratically Many Colorful Simplices
• The colourful feasibility problem

Cited in

(12)

• Examples with decreasing largest inscribed ball for deterministic rescaling algorithms
• Algorithms for colourful simplicial depth and medians in the plane
• The intersection of a matroid and an oriented matroid
• Colorful linear programming, Nash equilibrium, and pivots
• Computing colourful simplicial depth and Median in \(\mathbb{R}_2\)
• A note on lower bounds for colourful simplicial depth
• Further consequences of the colorful Helly hypothesis
• The 1-Color Problem and the Brylawski Model
• Colouring solutions of the ice problem
• The colourful feasibility problem
• A quadratic lower bound for colourful simplicial depth
• Colourful linear programming

Describes a project that uses

Uses Software

• CLP

This page was built for publication: The colourful feasibility problem

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