6
$\begingroup$

Linear Programming is in polynomial time weakly (when numbers are encoded in unary). AFAIK it remains open if it is possible to solve LP in polynomial time strongly (when numbers are encoded in binary).

My questions is about a special subclass of LP called Packing LP:

Packing LP
Variables: $\vec{x}$
Constraints:

  • $A\vec{x} \leq \vec{b}$
  • $\vec{x} \geq 0$

Objective: $\max \vec{c}^T \vec{x}$
where $\vec{c} > 0$, $\vec{b} > 0$, and $A \geq 0$ (component-wise)

Is there a strongly polynomial-time algorithms for Packing LP or is it "nearly as difficult" as solving LP in general?

I am interested in exact algorithms. For approximation, there is a strongly polynomial-time FPTAS for Packing LP according to [Garg and Könemann, 2007].

$\endgroup$
  • 1
    $\begingroup$ IIRC LP is strongly polynomial-time but I may be recalling incorrectly. Hopefully someone more knowledgeable will chime in. $\endgroup$ – Kaveh Apr 24 '16 at 17:12

Your Answer

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

Browse other questions tagged or ask your own question.