# 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.

179 questions
Filter by
Sorted by
Tagged with
113 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.
207 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?
77 views

663 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 ...
166 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 ...
176 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 ...
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?
149 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 ...
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 ...
68 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 ...
137 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 ...
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 ...
317 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 ...
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....
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$ ...
295 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 ...
398 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 ...
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 ...
157 views

119 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_{...
195 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 ...
205 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?
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 ...
217 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 ...
511 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 ...
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.
287 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$...
267 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,...
178 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 ...