Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
aram's user avatar
  • 2,005
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 ...
Tal Alon's user avatar
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 ...
Daniil Kozhemiachenko's user avatar
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 ...
Yvan's user avatar
  • 11
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 ...
Star's user avatar
  • 404
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 &...
Phillip Feldman 's user avatar
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 ...
user1868607's user avatar
  • 6,255
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 ...
stats_noob's user avatar
  • 4,089
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 ...
MDescamps's user avatar
  • 171
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 ...
Garrett's user avatar
  • 1,671
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*} ...
borealis's user avatar
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} & ...
Sébastien Loisel's user avatar
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 ...
3nondatur's user avatar
  • 4,404
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 ...
userAN82's user avatar
  • 441
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 ...
Reccho's user avatar
  • 55

15 30 50 per page