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.
173
questions
1
vote
0answers
62 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
109 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
88 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
117 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
59 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
137 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
63 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 ...
0
votes
0answers
60 views
What is the run-time of LP?
Are there any further generalizations known to the result about run-time of a LP than what is stated in Theorem 1 of these lecture notes,
https://nisheethvishnoi.files.wordpress.com/2018/05/lecture71....
1
vote
0answers
48 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
150 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
103 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
152 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
130 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
61 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
654 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
164 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
166 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
79 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
147 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
86 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
66 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
124 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
421 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
300 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
129 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
288 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
384 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
70 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
156 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
166 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
118 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
194 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
195 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
92 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
214 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
494 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
56 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
258 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$...
4
votes
1answer
263 views
Solving linear equations involving min
Solve for $\alpha$ if solution exists:
$\min(r_1, s_1 \alpha_1) + \min(r_2, s_2\alpha_1) = d_1$,
where $r_1,r_2,s_1,s_2,d_1$ are integer constants.
One way seems to be enumerate all possible outcomes,...
3
votes
1answer
143 views
Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K
I find myself with another graph problem that I can't find the name of. I was wondering if anyone was able to identify if this problem and any efficient algorithms to solve it are known.
The ...
6
votes
1answer
147 views
Brute force search algorithm for semidefinite programming (representation of spectrahedron)
I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for ...
3
votes
1answer
320 views
List of Pivot rules for simplex methods
Any implementation of the simplex method depends on the choice of pivot rule, which determines how the corners of the search space polyhedron are traversed. Many different have been proposed ...
4
votes
0answers
275 views
Are there integer programs with small coefficients that only have large solutions?
It is well-known that if an integer linear program has a feasible solution, then it has a feasible solution whose bit size is polynomially bounded. For example, here is Theorem 13.4 from Papadimitriou ...
1
vote
1answer
276 views
Is finding an optimal solution to this Knapsack-like problem NP-hard?
Suppose our inputs are a set of objects with weights $w_1,...,w_n$. We have two separate sets of profits: $p_1,...,p_n$ and $v_1,...,v_n$. We wish to maximize $ \sum_{i=1}^{n} p_i(1-x_i)+\alpha_i ...
5
votes
1answer
698 views
The Average-case Complexity of Simplex Algorithm
I was wondering if there are any results on the average case complexity of the simplex algorithm. Let $A \in \mathbb{R}^{m \times n}$ be the matrix in the linear constraint. I know that Smale did ...
1
vote
0answers
72 views
Convex hull of codebook (LP-decoding)
So the well-cited article by Feldman et al from 2005 has a method of constructing the convex hull of the feasible set for ML-decoding.
Basically, he considers the parity check matrix $H$ as a Tanner ...
13
votes
4answers
920 views
Finding the sparsest solution to a system of linear equations
How hard is it to find the sparsest solution to a system of linear equations?
More formally, consider the following decision problem:
Instance: A system of linear equations with integer coefficients ...
2
votes
0answers
397 views
How to prove integrality of LP with not totally unimodular matrix
I have a linear program (LP) for which the constraint matrix is NOT totally unimodular (TU). However, even though constraint matrix is small (14x20), extensive generation of random coefficients for ...
