4
$\begingroup$

It is known that Linear Programming (LP) is P-complete. I am interested in approximation algorithms for LP.

There are numerous inapproximability results for NP optimization problems, e.g. it is NP-hard to achieve approximation ratio better than 7/8 for MAX-3SAT.

Are there similar P-hardness results for approximation optimization problems in P?
In particular, is it known if LP is P-hard to approximate?

$\endgroup$
5
  • 1
    $\begingroup$ An LP is an optimization also: $\max c^\top x$ such that $Ax \le b$ $\endgroup$ Apr 30 '14 at 23:22
  • 1
    $\begingroup$ Yeah, but the usual notions of approximation don't apply. What if the optimal objective value is zero? What if it's negative? $\endgroup$
    – Jeffε
    May 1 '14 at 0:24
  • $\begingroup$ Negativity doesn't change anything if you replace the usual A/OPT by |A - OPT|/|OPT|. As for when OPT is $0$, that problem occurs even outside LPs: one response is "this shows that approximating LPs is also P-complete" and the other would be to relax to a $(\alpha, \beta)$ style approximation. $\endgroup$ May 1 '14 at 17:35
  • $\begingroup$ OP, as Suresh points out, the answer to your question will depend on what kind of approximation you ask about Can you clarify what you have in mind? $\endgroup$
    – Neal Young
    May 2 at 1:41
  • $\begingroup$ The feasibility problem with no objective is already P-complete. Adding in the promise that a feasible solution exists does nothing to help identify a solution, as otherwise the prover can guess that a solution exists and work from there. It's hard to imagine a particularly useful objective function / approximation guarantee pair we can tack on to an already P-complete problem that suddenly makes the problem not P-hard. $\endgroup$
    – Yonatan N
    May 5 at 21:30
6
$\begingroup$

See the paper "A parallel approximation algorithm for positive linear programming." by Luby and Nisan. (Some kinds of) linear programs can be approximated in log^(O(1)) n time.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.