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.
183
questions
2
votes
0answers
27 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 ...
0
votes
0answers
26 views
Which algorithm for linear programming is suitable for the context of quantum computing?
There are two major types of algorithms for linear programming : extreme point based, interior point based.
Which will be suitable for quantum computing?
0
votes
0answers
37 views
are there approximation algorithms that use primal-dual with LP values and/or rounding?
Are there approximation algorithms that use primal-dual with LP values and/or rounding?
e.g. An algorithm that during any iteration first tries to see an extreme point to the LP has any value above a ...
2
votes
0answers
92 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 ...
2
votes
1answer
122 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
1answer
218 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?
5
votes
1answer
78 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 ...
5
votes
0answers
53 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, ...
1
vote
1answer
101 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 ...
1
vote
0answers
80 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, ...
0
votes
0answers
109 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
0answers
72 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
2answers
166 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
1answer
102 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 ...
1
vote
1answer
119 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 ...
0
votes
0answers
134 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 ...
-1
votes
1answer
61 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
1answer
143 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. ...
1
vote
0answers
66 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 ...
1
vote
0answers
52 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 [...
2
votes
1answer
158 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
1answer
117 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 ...
5
votes
1answer
159 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
0answers
161 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 ...
4
votes
1answer
62 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
1answer
673 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 ...
4
votes
1answer
173 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 ...
3
votes
1answer
180 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
0answers
80 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?
4
votes
1answer
152 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
0answers
87 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 ...
4
votes
1answer
71 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
2answers
143 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
1answer
425 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 ...
8
votes
1answer
341 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 ...
1
vote
0answers
37 views
Monotone complexity of PLP
Blum and Nisan show Positive Linear Programming could be done in $NC$ if we only ask for approximate solutions. This paper https://pdfs.semanticscholar.org/8dc7/5aa9d72864022d848c3e599c5f24d9d527e7....
3
votes
1answer
131 views
On complexity of linear programming with quadratic equality/inequality constraints?
Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ ...
7
votes
1answer
300 views
Reaching the double exponential upper bound in Fourier-Motzkin elimination
One round of Fourier-Motzkin elimination may yield $n^2/4$ inequalities where $n$ is the original number of linear inequalities, whence an upper bound of $n^{2^d}/2^{2^{d+1}-2}$ for $d$ rounds of ...
4
votes
2answers
423 views
Complexity of finding a consistent hyperplane
Given $m$ binary labeled points in $\mathbb{R}^d$, it is well-known that in general it's NP-hard to find a hyperplane that minimizes sample error. A brute-force search considers all $O(m^d)$ sample ...
2
votes
0answers
79 views
Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$
The problem of giving an explicit formula for $A_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A_q(n,d)$ is given by the maximum number of codewords in a q-ary ...
3
votes
0answers
160 views
Max and Min Equations with Linear Programing
I am given constants $c_{i,j}$ as inputs. I want to find values for the variables $x_i$ that satisfy a system of equations, where each equation either takes the form
$$x_i = \max\{x_j + c_{i,j} : j \...
2
votes
1answer
209 views
Solving linear program with 1 quadratic constraint complexity
Consider the following linear program,
$$\min y \\
xc_1 \leq c_2 + yz,\\
x = x_1 + \dots + x_n,\\
z \leq x_1 + x_2, \\
z \leq x_2 + x_3, \\
\vdots\\
z \leq x_{n-1} + x_n, \\
x,x_1, \dots, x_n,y,z \...
-3
votes
1answer
122 views
What is wrong with this procedure to convert quadratic programming to convex quadratic programming?
Consider the feasibility quadratic program with constraint
$$\sum_{i=1}^nc_{i1}x_{i}\leq \ell_1$$
$$\vdots$$
$$\sum_{i=1}^nc_{it}x_{i}\leq \ell_t$$
$$\sum_{i,j=1}^na_{ij}x_{i}x_{j}+\sum_{i=1}^nb_{i}x_{...
4
votes
0answers
198 views
What exactly did Lenstra prove on mixed integer linear program?
I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
6
votes
1answer
206 views
Cases of Linear programming known to be in $NC$?
Linear programming is $P$-complete.
However are there special situations where we know an $NC$ algorithm?
3
votes
1answer
93 views
About the sign-rank of the Minsky-Pappert function
Apologies this might be a very trivial thing I am getting confused by!
Firstly in corollary 1.1 (page 3) in this paper, https://eccc.weizmann.ac.il/report/2016/075/ the authors claim that they have ...
1
vote
1answer
225 views
Max weight travel on a graph with deadline
Given a deadline $D>0$ and a complete graph $K_n$ (with loops) in which each edge $e_{ij}$ has a weight $w(e_{ij}) \ge 0$ and a travel time $l(e_{ij}) > 0$. Starting from one of the nodes, we ...
17
votes
1answer
543 views
How not to compute the smallest circle enclosing a finite set of circles
Suppose we have a finite set $L$ of disks in $\mathbb{R}^2$, and we wish to compute the smallest disk $D$ for which $\bigcup L\subseteq D$. A standard way to do this is to use the algorithm of ...
0
votes
1answer
57 views
How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming? [closed]
Edges are given in form of $X_{ij}$, which denotes whether there is edge in between $i^{th}$ and $j^{th}$ vertex. I am solving integer optimization problem and want to add this constraint to it.
2
votes
1answer
330 views
Are there specific examples of integral polyhedra that are neither Totally Unimodular nor Total Dual Integral?
It is well known that if a constraint matrix $A$ is total dual integral or totally unimodular, then this is a sufficient condition of integrality of the polyhedron defined by the system $Ax \leq \beta$...
