2005/11/30 by Antoine Deza, Deza, Antoine, Sui Huang +5
Computer Science · Mathematics · #52C45 #68Q25 #68W40 #90C60 #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Search Problems #math.CO #msc:52C45 #msc:68Q25 #msc:68W40 #msc:90C60
paper · pdf · doi:10.48550/arxiv.math/0511749
19 pages, 7 figures
arxiv created 2005/11/30 · openalex publication_date 2005/11/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.