Name
Abstract | ||
|---|---|---|
We study a colourful generalization of the linear programming feasibility problem, comparing the algorithms introduced by Barany and Onn with new methods. This is a challenging problem on the borderline of tractability, its complexity is an open question. We perform benchmarking on generic and ill-conditioned problems, as well as recently introduced highly structured problems. We show that some algorithms can lead to cycling or slow convergence and we provide extensive numerical experiments which show that others perform much better than predicted by complexity arguments. We conclude that the most efficient method is a proposed multi-update algorithm. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.dam.2008.01.016 | Discrete Applied Mathematics |
Keywords | Field | DocType |
extensive numerical experiment,colourful linear programming,proposed multi-update algorithm,open question,colourful generalization,efficient method,new method,challenging problem,complexity argument,ill-conditioned problem,linear programming feasibility problem,colourful feasibility problem,linear program | Convergence (routing),Mathematical optimization,Linear programming,Benchmarking,Mathematics | Journal |
Volume | Issue | ISSN |
156 | 11 | Discrete Applied Mathematics |
Citations | PageRank | References |
10 | 0.76 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Antoine Deza | 1 | 106 | 25.41 |
| Sui Huang | 2 | 21 | 2.02 |
| Tamon Stephen | 3 | 121 | 16.03 |
| Tamás Terlaky | 4 | 677 | 65.75 |