All Questions
Tagged with computational-complexity linear-programming
40 questions
2
votes
2
answers
109
views
LP relaxation leads to exponential Branch & Bound
Consider the following LP program
$$ \min x_{n+1} $$
subject to:
$$ \sum_{i=0}^n 2 x_i + x_{n+1} = n $$
$$ x_i \in \{ 0, 1 \} $$
And $n$ odd.
The claim is that using the standard B&B algorithm ...
0
votes
0
answers
25
views
Inexact Approximation Oracles with Multiplicative Error?
I have a linear program (LP) with $n$ variables and $2^m$ constraints:
$$
\min \sum_{i \in [n]} x_i \quad \text{subject to} \quad x_i \geq y_j \quad \forall j \in 2^m, \, i \in [n].
$$
I can compute ...
2
votes
1
answer
196
views
Complexity of solving systems of linear inequalities with two variables per inequality with additional constraints
Consider a system $X$ of linear inequalities containing at most two variables. In the general case, finding a solution over $\mathbb{R}\cap[0,1]$ can be done deterministically in polynomial time due ...
1
vote
1
answer
382
views
What is the time complexity of deciding whether a linear program is feasible?
I have a question: What is the time complexity for solving a convex feasibility problem (particularly, this question focuses on the linear feasibility problem)?
Specifically, the feasibility problem ...
1
vote
1
answer
350
views
Tractability of linear programming
Consider a linear program
$$
\max_{x} c^\top x\\
\text{s.t. } Ax \leq b\\
\text{and } x\geq 0
$$
I have been asked to comment on the "computational tractability" of such a program.
I am ...
3
votes
1
answer
92
views
Upper bound on amount of "pieces" created by nested absolute values.
If I have a nested absolute value equation such as:
y = |||3x-2|-|8-7x|| -2|x+3||
where all terms in absolute values are linear, what is the complexity (Big -O) of the upper bound on the amount of &...
3
votes
1
answer
282
views
Proof of bounded Farkas lemma
In this paper, Papadimitriou gives a proof of the fact that integer linear programming is in NP. There are some points that are obscure to me. Let me state the theorems involved:
Lemma 1: Let A be a ...
3
votes
1
answer
540
views
Importance of the Klee-Minty Cube in Optimization
Has anyone ever heard of the Klee-Minty Cube in Optimization?
Supposedly, the Klee-Minty Cube shows the "flaws" of the Dantzig's Simplex Algorithm. Supposedly, Dantzig's Simplex Algorithm ...
2
votes
0
answers
57
views
Efficient way of checking set inclusion for projected convex polytopes: $\pi(P_L) \subseteq \pi(P_M)$
I have two convex polytopes defined as
$$
P_L = \{x\in\mathbb{R}^L \mid A_Lx \leq b_L\}\\
P_M = \{x\in\mathbb{R}^M \mid A_Mx \leq b_M\}
$$
where $L$ and $M$ are in the order of $100$ or higher. Now ...
0
votes
1
answer
545
views
Solving 3-SAT with Linear Programming?
Suppose we have a set of indices $I = \{1, \dots, n\}$ and a corresponding set of boolean variables $\{X_1, \dots, X_n\}$. Suppose further that we have a 3-CNF expression with $m$ clauses, with ...
2
votes
1
answer
134
views
Polynomial time for a quadratic equation and linear inequalities?
Does anyone know how to find a feasible solution (or the infeasibility of any solution) in a polynomial time to the following problem:
\begin{align*}
xAx^t = 0, \\
Bx^t = c, \\
x_i \ge 0,
\end{align*}
...
2
votes
0
answers
48
views
Linear programming with approximate arithmetic
One of the big achievements since the 80s is the solution of linear programs, e.g., by barrier method. For example, to solve
$$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & ...
1
vote
1
answer
209
views
Linear Programming - A brute force approach
I was wondering what the main drawback for using a brute force approach in Linear Programming would be. My idea would be to just iterate over all possible basic solutions, filter out the infeasible ...
1
vote
0
answers
1k
views
complexity of linear programming
I am analyzing the computational complexity of an algorithm that includes as a step the solution of a linear subproblem of n variables and n constraints.
The linear subproblem can be solved by the ...
2
votes
0
answers
108
views
Linear Program such that Simplex (w/ any pivot rule) takes exponential time?
I had this exam question last semester, and it's still bothering me:
For every natural number $n$, you want an LP (not necessarily with $n$ inequalities)
such that simplex cannot solve it in ...