All publications

EUCLID / RESEARCH OUTPUT

Journal Article

The complexity of linear programming in -form

Pavlos S. Efraimidis

Information Processing Letters · Feb 2008

Abstract

Linear programming in (γ,κ)-form is a restricted class of linear programming (LP) introduced in [L. Trevisan, Parallel approximation algorithms by positive linear programming. Algorithmica 21 (1998) 72–88]. Since [L. Trevisan, Erratum: A correction to parallel approximation algorithms by positive linear programming. Algorithmica 27 (2000) 115–119] the complexity of (γ,κ)-form LP is an open problem. In this work, we show that LP in (γ,κ)-form is P-Complete to be approximated within any constant factor. An immediate consequence is that the extension of Positive Linear Programming (PLP) where the coefficients (matrix A) can have negative values is also P-Complete to be approximated within any constant factor.

CITATION

BibTeX

Efraimidis_2008 
@article{Efraimidis_2008,
    title={The complexity of linear programming in -form},
    volume={105},
    ISSN={0020-0190},
    url={http://dx.doi.org/10.1016/j.ipl.2007.08.025},
    DOI={10.1016/j.ipl.2007.08.025},
    number={5},
    journal={Information Processing Letters},
    publisher={Elsevier BV},
    author={Efraimidis, Pavlos S.},
    year={2008},
    month=Feb,
    pages={199–201}
}
Back to publications