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

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

• 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
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 1054763 (Why is no real title available?)
• Quadratically Many Colorful Simplices
• The colourful feasibility problem

Cited in

(13)

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

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)