The Colourful Feasibility Problem

Simple item page
dc.creatorDeza, Antoine
dc.creatorHuang, Sui
dc.creatorStephen, Tamon
dc.creatorTerlaky, Tamás
dc.date2005-11-30
dc.date.accessioned2026-07-07T06:51:57Z
dc.date.available2026-07-07T06:51:57Z
dc.descriptionWe 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.
dc.description19 pages, 7 figures
dc.identifierhttps://arxiv.org/abs/math/0511749
dc.identifierhttp://arxiv.org/abs/math/0511749
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/105156
dc.subjectCombinatorics
dc.subject52C45, 68W40, 90C60, 68Q25
dc.titleThe Colourful Feasibility Problem
dc.typetext

Files

Collections

arXiv