# Questions tagged [linear-programming]

Mathematical and computational method for finding the best outcome in a given mathematical model where the list of requirements is represented as linear relationships.

29 questions
Filter by
Sorted by
Tagged with
943 views

### What classes of mathematical programs can be solved exactly or approximately, in polynomial time?

I am rather confused by the continuous optimization literature and TCS literature about which types of (continuous) mathematical programs (MPs) can be solved efficiently, and which cannot. The ...
3k views

### Integer programming with a fixed number of variables

The famous 1983 paper by H. Lenstra Integer Programming With A Fixed Number Of Variables states that integer programs with a fixed number of variables are solvable in time polynomial in the length of ...
1k views

4k views

### LP relaxation of independent set

I've tried the following LP relaxation of maximum independent set $$\max \sum_i x_i$$ $$\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E$$ $$x_i\ge 0$$ I get $1/2$ for every variable for every cubic ...
491 views

Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$, is given. E.g. $S=\{(1,3), (2,3), (1,4), (2,4), (3,1), (3,4)\}$ . For each element $(i,j)$, we have weight $w_{... 2answers 153 views ### Minimum relevant variables in linear system - additive approximation In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.: $$A x = b$$ and the goal is to find a solution$x$with as few nonzero variables as ... 0answers 146 views ### Exactly solvable but non-trivial integrality gap Are there interesting polynomial time solvable problems that we know of for which the natural convex relaxation has a non-trivial integrality gap? Note: Maximum matching doesn't qualify because I ... 2answers 306 views ### A variant of linear programming Consider this "variant" of linear programming: Notation:$\max\{ x_1, \cdots, x_n \}$denotes the maximal number among$x_1, \cdots, x_n$; minimize$\sum a_i x_i$such that$\max\{x_i\mid i\...
I saw somewhere that optimal solutions of LP Relaxation of independent set are half-integral, by what I mean the possible values of a solution are ${ \{0,0.5,1 \} }$. I'm looking for proof of that. ...