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.
172
questions
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
58 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
46 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 ...
0
votes
0answers
44 views
Structure of an Optimal Solution to a Fractional Packing Problem
Packing LP
We have the following optimization problem:
$$ \max_{x_{ij}} x_{ij} c_{ij}$$
s.t. $$(i)\forall j\mbox{ }\sum_{i} x_{ij} \leq \beta_j$$
$$(ii)\forall i\mbox{ }\sum_{j} x_{ij} D_{ij} \leq 1$...
2
votes
1answer
146 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
99 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
141 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 ...
0
votes
0answers
11 views
Extension complexity of convex hull of vertex intersection of nicely behaved polytopes?
Take two convex bounded polytopes $P_1$ and $P_2$ where
a. $P_2\subseteq P_1$
b. $\mathcal{V}(P_1)\cap\mathcal{V}(P_2)\neq\emptyset$ where $\mathcal{V}(P_i)$ is vertex set of $P_i$ at $i\in\{1,2\}$.
...
0
votes
0answers
30 views
Does simplex algorithm work in this case?
Essentially I want to know if we have two polytopes $P_1$ and $P_2$ in $\mathbb R^n$ and we maximize on $P_1\cap P_2$ where
a. $P_2\subseteq P_1$
b. $\mathcal{V}(P_2)\cap\mathcal{V}(P_1)\neq\...
1
vote
0answers
121 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 ...
0
votes
0answers
20 views
The set of weight functions for which the assignment problem has non-trivial solutions
The standard assignment problem is specified with a square matrix ${\bf W}$ of weights (values, costs):
$$
V_{\cal P} = \sum_i w(i, b(i)) = \sum_{(i, j) \in {\cal P}} w_{ij},
$$
where $\cal P$ is a ...
0
votes
0answers
49 views
What is the complexity of Parametric Mixed Integer Linear Programming?
We know
$$\forall\bf y\in\mathbb Z^n:K\bf y\leq b$$
$$\exists\bf x\in\mathbb Z^m:A\bf x + B\bf y\leq c$$
is in $\bf P$ if $n,m$ are fixed from Kannan's result (refer page $1$ in reference).
What is ...
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
632 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
161 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
160 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
78 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
145 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
84 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
65 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
121 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 ...
4
votes
1answer
412 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
229 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
128 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
283 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
376 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
69 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
147 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
117 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
190 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
193 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
91 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
208 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
483 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
244 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
260 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
141 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
281 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
270 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
275 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
650 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
70 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
905 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
395 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 ...
0
votes
2answers
450 views
NP completeness of linear $0-1$ assignment problem
Supposing we have a linear equation in $n^2$ variables with integer (negatives allowed) coefficients of at most $m$ bits each.
Partition $\Pi_1$ the variables into $n$ disjoint sets of $n$ variables ...
