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.

Filter by
Sorted by
Tagged with
3 votes
1 answer
166 views

Can the ellipsoid method be used with a randomized separation oracle?

Suppose we are trying to solve the following optimization problem: $$ \text{maximize } ~~ c\cdot y \\ \text{subject to } ~~ y\in S $$ where the region $S$ is described by an exponential number of ...
0 votes
0 answers
85 views

How to prove that a given class of convex programs cannot be solved by linear programming?

Given the following program, where $f, g$ are convex functions: $$ \text{minimize}~~ f(x) \\ \text{subject to}~~ g(x)\leq 0 $$ the problem can be solved by convex programming algorithms, but it would ...
3 votes
1 answer
169 views

Solving linear programs with special structure

We have an application and at some point we need to solve a linear programming problem that looks like this: $$ \min\ w_{1,2} + w_{3,4} + w_{5,6}\\ x_i - x_j \leq c_{ij},\ \forall\ (i,j) \in C\\ x_1 - ...
  • 73
1 vote
0 answers
89 views

Max-flow while restricting flow on subsets of edges to be equal

Consider a max-flow network $G(V,E,c)$. Consider disjoint subsets of the arcs $R_1,…, R_k$. I want to find the maximum $s-t$ flow such that all the edges in the $R_i$ have equal flow. Obviously, this ...
2 votes
0 answers
67 views

Parallel complexity of fixed dimension fixed constraints integer programming

Papadimitriou in https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf shows ILP is fixed parameter tractable in number of constraints and Lenstra in https://people.csail.mit....
  • 12.6k
0 votes
0 answers
35 views

What is the tightest lower bound known for the integrality gap of the Gilmore–Gomory LP for Bin Packing?

I know that it has been conjectured that the Gilmore–Gomory LP for 1-D BP (also known as configuration LP) has Modified Integer Roundup Property, i.e., Opt ≤ ⌈Opt_f⌉ + 1. However, I could not find the ...
  • 73
0 votes
0 answers
54 views

How can we convert from Robust Linear Programming to SOCP?

Problem establishment Suppose that in inequality constraint $i$ the true values $\tilde{a}_{ij}, j\in J_i$, of uncertain data can range in the interval $[a_{ij}-\epsilon|a_{ij}|,a_{ij}+\epsilon|a_{ij}|...
0 votes
0 answers
97 views

Separation oracle for breaking cycles in directed graph

I am working on a directed graph problem and am collaterally interested to know whether there is a separation oracle for the following set of linear constraints. We are given a directed graph $G$ ...
2 votes
1 answer
125 views

Is there an approximate version of the strong duality theorem for linear programming?

Consider the following dual linear programs: $$ \min \mathbf{c^T x} ~~ \text{s.t.} ~~ A \mathbf{x} \geq \mathbf{b}, \mathbf{x}\geq 0; \\ \max \mathbf{b^T y} ~~ \text{s.t.} ~~ A^T \mathbf{y} \leq \...
6 votes
1 answer
258 views

Is there a simplex-like algorithm that can be used with a separation oracle?

Linear programs can be solved in polynomial time using the ellipsoid method, but in practice the Simplex method is much more efficient, and the smoothed analysis framework of Spielman and Teng ...
5 votes
1 answer
219 views

What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?

What is known about the LP gap of (the natural Held-Karp relaxation of) the (symmetric) Travelling salesman in special instances? I'm only aware of one special case where the extreme points are all ...
  • 227
5 votes
0 answers
102 views

Why is the ellipsoid method numerically unstable?

In the Ellipsoid method wikipedia entry under the performance section, it is mentioned that the Ellipsoid method often times is numerically unstable in practice: "On even "small"-sized ...
0 votes
1 answer
178 views

Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?

Often, we can model combinatorial optimization problems with an Integer Program. Then there is an associated Linear Relaxation which drops the integrality constraints on the variables. Let's say we ...
1 vote
0 answers
113 views

Is this proof of $LP$ being in $coNP$ correct?

I am referring to the natural decision version of the Linear Programming problem: given $A \in \mathbb{Q}^{m \times n}, \ b \in \mathbb{Q}^m, \ c \in \mathbb{Q}^n, \ \alpha \in \mathbb{Q}$, does there ...
2 votes
1 answer
199 views

Characterization of integral polyhedra

A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$. Equivalently, $P$ is integral if ...
3 votes
0 answers
76 views

Using Baire Category to analyze the efficiency of the Simplex Method

I read from the wiki page of the Simplex Algorithm that we can "use Baire category theory from general topology, and to show that (topologically) "most" matrices can be solved by the ...
0 votes
0 answers
86 views

Prove that this linear relaxation has half-integral extreme points

Given a graph $G=(V,E)$, here is a Linear Relaxation of the edge cover polytope: (1) For each $v \in V, \sum_{e \in \delta(v)} x_e \geq 1.$ (2) For each $e \in E$, $0 \leq x_e \leq 1.$ Here $\delta(S)$...
4 votes
0 answers
133 views

Complexity of real coefficients Linear Programs

I would like to know if there are known any polynomial time algorithms for deciding the feasibility of linear programs with real (not integers) coefficients. I know that for linear programs with ...
  • 141
3 votes
0 answers
150 views

(Integer) Linear Program formulation of planarity?

Q: Is there an efficient (I)LP formulation of planarity? More specifically, I am looking for a set of constraints that are satisfied by exactly all planar graphs on $n$ vertices, in order to optimize ...
  • 241
2 votes
1 answer
184 views

Is this homework problem on T-joins wrong? [closed]

In Question 9.3a, it states that if $T=V$, then the minimum cost perfect matching is the minimum cost T-join. Is this actually true? I think I have a counterexample which I have drawn below.
4 votes
1 answer
295 views

Proof of $LP$ is in $coNP$ without showing it is in $P$?

Is there a proof that linear programming is in $coNP$ without showing it is in $P$? If so what is the strategy?
  • 12.6k
5 votes
1 answer
84 views

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

Let $G=(V,E)$ be graph. Recall that a cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in ...
  • 227
5 votes
0 answers
85 views

reference request: greedy algorithm for fractional interval covering

Reference Request I've found a natural greedy algorithm for the problem below. My question is: what is already known about fast algorithms for this problem (faster than general linear programming, ...
  • 9,223
1 vote
1 answer
111 views

Ensuring integral maximizer from integral linear program

An integral linear program is one that has a maximizer that is integral. Sometimes it's possible to prove that a particular LP has this property, for example by proving that it's constraint matrix is ...
  • 690
1 vote
0 answers
119 views

Is the edge cover polytope integral on graphs with self-loops?

It is well known that the edge cover polytope is integral on simple graphs. I am wondering whether this also holds for graphs with self-loops. Here is a Linear Relaxation of the edge cover polytope, ...
1 vote
0 answers
155 views

Is the matching polytope integral?

In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf they prove the integrality of the matching polytope using the integrality of the perfect matching polytope. The ...
1 vote
0 answers
144 views

Separation oracle for hitting all small cut on a graph?

We are given as input an undirected graph $G=(V,E)$, weights $w_e \ge 0$ for all $e\in E$ and an positive integer $k$. We aim to select a set of edges with the minimum weight, such that the cut set of ...
-2 votes
2 answers
432 views

Proof that optimal solutions of LP Relaxation of independent set are half-integral

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. ...
1 vote
1 answer
228 views

Intuition behind the Charikar's LP formulation for densest subgraph problem

I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper. Just mentioning the LP for maximum density of a ...
  • 23
1 vote
1 answer
182 views

Minimum non-zero variable in the optimal solution of linear programming

Suppose we have a linear programming about the vertex packing of a hypergraph G=(V,E), with size $n = \sum_{e \in E}|e|$. We introduce a variable $x_v$ for each vertex $v \in V$. $$\max \sum_{v} x_v ...
  • 49
0 votes
0 answers
152 views

linear programming with non-integer constraints

Suppose we have a linear progamming about vertex packing of a hypergraph (V,E), with size $n = \sum_{e \in E} |e|$. We introduce a variable $x_v$ for each vertex $v \in V$. The fractional version is ...
  • 49
-1 votes
1 answer
79 views

Is it possible to approximate the solution of NP-Hard problems in polynomial time using linear programming? [closed]

Suppose we have a NP-Hard problem such as the k-col, which is meant to determine if a graph may be colored using at most ...
3 votes
1 answer
195 views

Minimal number of hyperplanes needed to separate sets of points from one other set

Let $\mathbb{R}^d$ be our space. We have a single good set of points $g$, and a collection of bad sets of points $B$. We assume that for all $b \in B$ the convex hulls of $g$ and $b$ are disjoint. ...
  • 690
1 vote
0 answers
77 views

Time complexity of alternation free quantified linear program with no free variables and only existential quantifications

We know $\exists x\in\mathbb R^n:Ax\leq b$ is standard linear program. I am mainly looking at following case of quantified linear program with no free variables with only existential quantifications ...
  • 529
1 vote
0 answers
66 views

Sherali-Adams lowerbound instance of Unique Games constructed via CLT

The question comes from the following paper I have been reading: [1] Integrality Gaps for Sherali–Adams Relaxations. SODA'09. Moses Charikar, Konstantin Makarychev, Yury Makarychev. Theorem 6.1 of [...
  • 191
2 votes
1 answer
171 views

Finding whether $n$ polytopes have nontrivial intersection from pairwise comparisons

I have a set of $n$ convex polytopes of the form $$\mathcal{L_i} = \{ \beta \mid C_i \beta \leq 0 \}$$ where $C$ is a matrix and $\beta$ is a vector. I know that for each pair of polytopes $$(\...
0 votes
1 answer
229 views

finding maximum weight subgraph

My graph is as follows: I need to find a maximum weight subgraph. The problem is as follows: There are n Vectex clusters, and in every Vextex cluster, there are some vertexes. For two vertexes in ...
  • 57
5 votes
1 answer
182 views

Complexity of Finding Largest Set of Intersecting Convex Polytopes

I have a set of $n$ convex polytopes, and I wish to find the largest subset of those polytopes that shares at least one point in common. I think that this problem should be NP-hard, but I am ...
1 vote
0 answers
276 views

Does simplex algorithm run in polynomial on Bipartite Perfect matching polytope?

It is well known that simplex algorithm runs in exponential time in worst case. However are there situations (necessary and sufficient conditions) where simplex algorithm runs in polynomial time? In ...
  • 12.6k
4 votes
1 answer
66 views

Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length

If $a_{ij}$ is an $m \times n$ matrix of real numbers, and $b_j$ are $n$ more real numbers, then $$\max_i \sum_j (a_{ij} x_j + b_j) \qquad (\ast)$$ is a convex piecewise linear function of $(x_1, \...
15 votes
1 answer
755 views

Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

I have a polytope $P$ defined by $\{ x : Ax \leq b, x \geq 0\}$ . Question: Given a vertex $v$ of $P$, is there a polynomial time algorithm to uniformly sample from the neighbors of $v$ in the graph ...
  • 1,439
4 votes
1 answer
183 views

How small can extension complexity be?

In this article on extension complexity of regular polygons https://arxiv.org/pdf/1505.08031.pdf it is mentioned that extension complexity of $n$ regular polygons should be $\theta(\log n)$. This is ...
  • 529
3 votes
1 answer
217 views

How is SDP an extension of spectral algorithms?

In one of his lectures, Uri Feige described semidefinite programming (SDP) as ... an algorithmic technique that extends both linear programming and spectral algorithms. I know the basic ...
3 votes
0 answers
84 views

Reference request: strong polynomial-time for LP

A follow-up of sorts on this question: Complexity of finding a consistent hyperplane What is a good survey of partial results on the strong poly-time status of the general LP problem?
  • 10.1k
4 votes
1 answer
155 views

Generalizations of linear programming

Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs. Is there a survey/lecture notes describing ...
2 votes
0 answers
108 views

Best algorithms for real linear programming

Linear Programming asks for $x\in\mathbb R^n$ such that $Ax\leq L$ holds where $A\in\mathbb R^{m\times n}$ and $L\in\mathbb R^m$ are given. Karmarkar has shown that $\ell$ is the number of bits of ...
  • 12.6k
4 votes
1 answer
79 views

Solving an LP with at most m-1 nonzeros

Consider the linear program: $$ A x = b, ~~~~~~ x\geq 0 $$ where $A$ is an $m$-by-$n$ matrix, $x$ is an $n$-by-1 vector, $b$ is an $m$-by-1 vector, and $m<n$. It is known that, if this ...
3 votes
2 answers
173 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 ...
5 votes
1 answer
443 views

Is there a counterexample to this work?

Is there a counterexample to this claim https://arxiv.org/abs/1610.00353? They claim a $O(n^6)$ LP model with simulations to support. I think asking validity is not a reasonable problem. However ...
  • 12.6k
10 votes
1 answer
489 views

How "hard" is it to maximize a polynomial function subject to linear constraints?

General Problem Suppose we have a multivariate polynomial function $f(\mathbf{x})$, and several linear functions $\ell_i(\mathbf{x})$. What is known about the complexity of solving the following ...
  • 464