http://www.cnr.it/ontology/cnr/individuo/prodotto/ID83494

Randomized combinatorial algorithms for linear programming when the dimension is moderately high (Contributo in atti di convegno)

Type

Label

Randomized combinatorial algorithms for linear programming when the dimension is moderately high (Contributo in atti di convegno) (literal)

Anno

Alternative label

Pellegrini M. (2003)
Randomized combinatorial algorithms for linear programming when the dimension is moderately high
in 12th ACM-SIAM Symposium on Discrete Algorithms
(literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#descrizioneSinteticaDelProdotto

In the last decade researchers in computational geometry have produced a series of algorithms for linear programming, based on a randomized combinatorial approach, which are tuned for linear programs where the number of variables d is small compared to the number n of constraints, although not so small to be considered a constant of the problem. One natural question is how practical are these algorithms for classes of LP instances not necessarily derived from problems in computational geometry. In this paper, building within the randomized combinatorial approach, we propose two algorithms for linear programming and we give evidence of their empirical running times on several classes of randomly generated instances. Comparisons with state of the art free software (lp solve) and state of the art commercial software (Cplex) lead to the conclusion that the randomized combinatorial approach for systems with n \approx d, at the present state of our research, can be competitive for dense systems and for sparse systems where a large fraction of the constraints are equalities. We also consider the case of dense systems where n >> d, which is typical in instances from computational geometry problems, for which we improve upon recent results of Gartner and Schonherr. (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni