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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ An LP is an optimization also: $\max c^\top x$ such that $Ax \le b$ $\endgroup$
    – Suresh Venkat
    Apr 30, 2014 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, 2014 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$
    – Suresh Venkat
    May 1, 2014 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, 2021 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, 2021 at 21:30

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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