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.
3
votes
1answer
106 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
66 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?
2
votes
1answer
116 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 ...
0
votes
0answers
67 views
Where is the flaw in this proof that an LP solves TSP? [duplicate]
In this preprint on Arxiv, M. Diaby, M.H. Karwan, and L. Sun give a Linear Program which they claim solves the Traveling Salesman Problem. In contrast to their prior work, which was asked about here, ...
2
votes
0answers
71 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
59 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
108 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 ...
3
votes
1answer
383 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
192 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
36 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
121 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$ ...
5
votes
2answers
338 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
59 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
141 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
112 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
113 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
171 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
181 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
85 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
184 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 ...
18
votes
1answer
421 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
53 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
201 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$...
5
votes
1answer
230 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,...
4
votes
1answer
130 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
141 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
225 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
206 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
267 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 ...
6
votes
1answer
509 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
63 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
797 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
350 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
396 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 ...
1
vote
1answer
191 views
On a Linearization of the Quadratic Assignment Problem
The Quadratic Assignment Problem formulated as an integer program:
\begin{align}
\mbox{minimize}\quad & \sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n ...
1
vote
0answers
204 views
Linear Programing with Rounding for the Fire Station Problem
Consider the following fire station problem: The input is a positive
integer k and a complete undirected graph $G = (V,E)$ with distances on the edges. The distances form a
metric: $d(v, v) = 0$, $d(...
12
votes
0answers
194 views
Linear programming with superpolynomially many constraints?
(The specific problem I have is stated as precisely as I could in the very last paragraph which starts with a boldface "Question:", up until then the question provides context for it.)
Say we have an ...
2
votes
0answers
163 views
Inclusion of polytopes
Consider the following two system of linear (in)eqaulities:
$S = Ax \leq b;\; Cx = e$
$T = Dx \leq d;\; Gx = g$
How can I check if $S\cap \neg T=\emptyset$ where $\neg T$ is the complement of the ...
3
votes
0answers
94 views
Equivalence of weighted Minkowski sums
Given $n$ polytopes $P_1, \cdots, P_n$, each $P_i$ is given as the V-representation, i.e., a set of $m$ points as its set of vertices.
Furthermore, consider a variant of the Minkowski sum (somehow ...
6
votes
1answer
253 views
Decide whether a point is a vertex of a polytope?
Inspired by the question, I would like to ask the following question:
Input: A polytope specified by $\Theta=\{\vec{x}\mid A\vec{x}\leq b\}$, and its affine projection
$f(\Theta)= \{(\vec{c}_1\cdot \...
2
votes
0answers
69 views
Check whether a point is a vertex of Minkowski sum of polytopes
Given $n$ polytopes
$$\begin{align*}
P_1&=\{(f^1_1(\vec{x}_1), \cdots, f^1_m(\vec{x}_1))\mid A_1\vec{x}_1\leq b_1\}\\
P_2&=\{(f^2_1(\vec{x}_2), \cdots, f^2_m(\vec{x}_2))\mid A_2\vec{x}_2\leq ...
2
votes
0answers
52 views
How to compute the basis
Given $n$ sets of linear constraints $\Theta_1, \cdots, \Theta_n$ which are over $\vec{x}_1, \cdots, \vec{x}_n$ respectively where $\vec{x}_i$ and $\vec{x}_j$ are pairwise disjoint, and
$W=
\begin{...
14
votes
2answers
936 views
Checking equivalence of two polytopes
Consider a vector of variables $\vec{x}$, and a set of linear constraints specified by $A\vec{x}\leq b$.
Furthermore, consider two polytopes
$$\begin{align*}
P_1&=\{(f_1(\vec{x}), \cdots, f_m(\...
5
votes
0answers
95 views
LPs with “sparse solutions”
Consider a graph optimization on a graph with n vertices and m edges that can be written as an LP (like say bipartite matching). By the duality with vertex cover, we know that there's a sparse dual ...
1
vote
0answers
122 views
Runtime of Gomory's Cutting Plane Algorithm
I read in several sources that the use of Gomory's cuts exclusively in Integer Programming was shown to be inefficient in practice when Gomory had created them. But later down the line they were shown ...
4
votes
1answer
113 views
Polytopes convex hull
Assume $P_1$, $P_2$ and $Q$ are axis-parallel polytopes in $\mathbb{R}^d$. Is it true to say that checking $CH(P_1\cup P_2)\neq Q$ is NP-hard? There is a similar result for the general polytopes but I ...
7
votes
0answers
144 views
SVM - running time for detecting if data is linearly separable?
If my understanding is correct, one way to check if a set of $m$ data points is linearly separable is to use support vector machines to find a maximum margin hyperlane for separating the data; the ...
2
votes
1answer
165 views
H-representation of convex hull
Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows:
$P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ ...
7
votes
2answers
255 views
What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?
What are some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems, especially any linear programs which had helped in getting good ...
1
vote
0answers
83 views
Minimum cost flow with Demand and Edge Capacity scaling
Consider a the splittable minimum cost flow problem on network $G(V,E,W,C)$ and a set of commodities $(s_i,t_i)$ with demand $d_i$ for $i=1,2,\dots,k$. Here, $w_e$ and $c_e$ is the weight of edge $e$ ...
