Bookcover of Colourful Linear Programming Feasibility Problem
Booktitle:

Colourful Linear Programming Feasibility Problem

Algorithms

LAP LAMBERT Academic Publishing (2012-11-16 )

Books loader

Omni badge eligible for voucher
ISBN-13:

978-3-659-28677-3

ISBN-10:
365928677X
EAN:
9783659286773
Book language:
English
Blurb/Shorttext:
This problem was presented by Barany and Onn in 1997 and it is still not known if a polynomial-time algorithm for the problem exists. The monochrome version of this problem, expressing p as a convex combination of points in a set S, is a traditional linear programming feasibility problem. The colourful Caratheodory Theorem, due to Barany in 1982, provides a sufficient condition for the existence of a colourful set of points containing p in its convex hull. Barany's result was generalized by Holmsen et al. in 2008 and by Arocha et al. in 2009 before being recently further generalized by Meunier and Deza. We study algorithms for colourful linear programming under the conditions of Barany and their generalizations. In particular, we implement the Meunier-Deza algorithm and enhance previously used random case generators. Computational benchmarking and a performance analysis including a comparison between the two algorithms of Barany and Onn and the one of Meunier and Deza, and random picking are presented.
Publishing house:
LAP LAMBERT Academic Publishing
Website:
https://www.lap-publishing.com/
By (author) :
Guohong Rong
Number of pages:
80
Published on:
2012-11-16
Stock:
Available
Category:
Other
Price:
49.00 €
Keywords:
algorithms, Colourful Linear Programming

Books loader

Newsletter

Adyen::amex Adyen::mc Adyen::visa Adyen::cup Adyen::unionpay Paypal Wire Transfer

  0 products in the shopping cart
Edit cart
Loading frontend
LOADING