Skip to main content
Share Your Experience: Take the 2024 Developer Survey
25 votes
Accepted

How "hard" is it to maximize a polynomial function subject to linear constraints?

Your problem is NP-hard, even for polynomials of degree 2. The crucial reference is Theodore Motzkin and Ernst Strauss (1965) "Maxima for graphs and a new proof of a theorem of Turan" ...
Gamow's user avatar
  • 5,772
20 votes
Accepted

Is there a counterexample to this work?

Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first ...
Gamow's user avatar
  • 5,772
9 votes

Proof of $LP$ is in $coNP$ without showing it is in $P$?

Note: all vector inequalities in this reply are to be interpreted pointwise. Given a linear feasibility problem, you can always rewrite it in the following canonical form: given a matrix $A \in \...
Yonatan N's user avatar
  • 1,642
8 votes

Solving linear equations involving min

I assume the generalization you are thinking of is the following: Given value $d$, and values $s_i$ and $r_i$ for $i = 1,2,...,k$, find (if possible) an $\alpha$ such that $$\sum_{i = 1}^k\min(r_i, ...
Mikhail Rudoy's user avatar
8 votes
Accepted

Is there a simplex-like algorithm that can be used with a separation oracle?

I'm not sure if you would consider the algorithms I'll discuss here "Simplex-like" (but see the comment about column generation at the end). If you have a weak separation oracle for a ...
Neal Young's user avatar
  • 10.8k
7 votes
Accepted

Is finding an optimal solution to this Knapsack-like problem NP-hard?

NOTE: My original reduction didn't work. Fixed now. Can't subset-sum be reduced to this problem fairly easily? Suppose all the profits $v_i$ are the same, say $v_i = 1$, and all the profits $p_i$ are ...
Peter Shor 's user avatar
7 votes
Accepted

Complexity of finding a consistent hyperplane

Second version, hopefully correct. I claim that solving the feasibility problem $\exists? x: Ax \le b$ reduces in strongly polynomial time to finding a linear separator. Then it's easy to reduce ...
Sasho Nikolov's user avatar
6 votes
Accepted

On complexity of linear programming with quadratic equality/inequality constraints?

A famous result by Motzkin and Straus expresses the $k$-clique problem as the maximization of a quadratic function subject to a system of linear constraints. In particular, they prove: Let $G$ be ...
Gamow's user avatar
  • 5,772
6 votes

Reaching the double exponential upper bound in Fourier-Motzkin elimination

I think this upper bound is tight. As an example, consider the following system \begin{align*} +x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le 0 \\ +x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le ...
Sasha Kozachinskiy's user avatar
6 votes
Accepted

How is SDP an extension of spectral algorithms?

This is not a precise statement so it's hard to give a precise answer, but I think what is meant is that SDPs are powerful enough to express both linear programs, and problems like "compute the ...
Sasho Nikolov's user avatar
6 votes
Accepted

Complexity of Finding Largest Set of Intersecting Convex Polytopes

Suppose that the dimension $d$ of the Euclidean space is fixed, and that the input consists of $n$ convex polytopes in $\mathbb{R}^d$ that altogether have $p$ facets. Let $h_1,\ldots,h_p$ denote the ...
Gamow's user avatar
  • 5,772
6 votes
Accepted

Minimal number of hyperplanes needed to separate sets of points from one other set

Your problem is NP-complete, even in the following two highly restricted cases: The dimension $d$ is part of the input, and the question is whether you can separate set $B$ from set $G$ by $k=2$ ...
Gamow's user avatar
  • 5,772
6 votes
Accepted

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)|$

Theorem 1. The given problem is NP-hard, by reduction from MAX-CUT. Proof. Call the given problem Positive Discrepancy Cut (PDC). Define weighted PDC to be the generalization where the input is a ...
Neal Young's user avatar
  • 10.8k
6 votes
Accepted

Characterization of integral polyhedra

Here's a proof (sketch) that doesn't explicitly use duality. More precisely, it replaces duality by a seemingly weaker (and hopefully easily believable) geometric fact, in Step 3 below. EDIT: But, ...
Neal Young's user avatar
  • 10.8k
6 votes
Accepted

Is there an approximate version of the strong duality theorem for linear programming?

A candidate for a variant of the strong duality theorem is: the primal LP has a solution $\mathbf{x^*}$ for which: $$ \mathbf{b^T y'} \cdot (1+\epsilon) \geq \mathbf{c^T x^*} \geq b^T \mathbf{y'}/(1+\...
Neal Young's user avatar
  • 10.8k
5 votes

Cases of Linear programming known to be in $NC$?

Fixed dimensional linear programming (for any constant dimension $d$) is known to be in $\mathsf{NC}$; in fact, it can be done work-efficiently (in the same amount of work as the fastest sequential ...
xal's user avatar
  • 439
5 votes

Decide whether a point is a vertex of a polytope?

This answer expands on Chandra's comment, and on my follow up comment. The problem is indeed solvable in polynomial time. More general versions of it are also solvable in polynomial time: $\Theta$ ...
Sasho Nikolov's user avatar
5 votes

Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

Theorem. The problem in the post is NP-hard, by reduction from Subset-Sum. Of course it follows that the problem is unlikely to have a poly-time algorithm as requested by op. Here is the intuition. ...
Neal Young's user avatar
  • 10.8k
5 votes
Accepted

Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?

See Feige and Jozeph's paper on separation between estimation and approximation.
Chandra Chekuri's user avatar
5 votes
Accepted

Is there a high level (functional) language compiling to Mixed Integer Linear Programming problems?

Here are the systems/languages I know of for representing these kinds of problems at a higher level of abstraction: The Z3 solver has higher-level constructs for words (fixed-length bit-strings), ...
D.W.'s user avatar
  • 12.1k
4 votes
Accepted

Minimum relevant variables in linear system - additive approximation

Unless $P=NP$, there does not exist a polynomial time approximation algorithm that returns solutions of value at most $\text{OPT}+d$. Suppose otherwise, and consider some fixed $d$ for which there ...
Gamow's user avatar
  • 5,772
4 votes
Accepted

Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

Edit 2: Embarrassingly, there is a two line proof of the $NP$-hardness, if one starts with the right polytope. First, recall the circulation polytope of a graph on the bottom of page 4 of Generating ...
Elle Najt's user avatar
  • 1,469
4 votes
Accepted

Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length

Introduce variables $y_{hi}$ together with constraints $y_{hi}=\sum_j (a_{hij} x_j + b_{hj})$ for all $h$ and $i$. Introduce variables $z_h$ together with constraints $z_h\ge y_{hi}$ for all $h$ and ...
Gamow's user avatar
  • 5,772
4 votes
Accepted

Minimum non-zero variable in the optimal solution of linear programming

No, it is not always possible. The illustration below shows an example in which the smallest non-zero value must be $1/2^{\Omega(n)}$. The example is shown in the top of the illustration. Round ...
Neal Young's user avatar
  • 10.8k
4 votes
Accepted

Solving linear programs with special structure

Assuming none of the $w_{ij}$ variables are constrained to be non-negative, your problem can be recast as a particular min-cost flow problem, and via that solved by solving just one all-pairs shortest-...
Neal Young's user avatar
  • 10.8k
4 votes

Complexity of simplex method

It could be that the variants refer to two different forms of Linear Programs. Simplex only works with problems in Standard Equality Form (SEF) which is of the form $$\min c^T x\,\,\,\,\text{s.t.}\,\,\...
NaturalLogZ's user avatar
4 votes
Accepted

Can you fix integral LP variables for a non-integral polytope without affecting the existence of integral optima?

It is false. Consider the following (2 variable) LP: \begin{align} \max&& 3x+2y & \\ && 2x+y &\leq 2 \\ && 0 \leq x &\leq 1 \\ && 0 \leq y &\leq 1 \end{...
NaturalLogZ's user avatar
3 votes
Accepted

What is wrong with this procedure to convert quadratic programming to convex quadratic programming?

The constraint $x_i x_j = y_{ij}$ isn't convex. Indeed, even the simpler constraint $ab = 8$ isn't convex. Let $C = \{(a,b) : ab = 8\}$. Then $(4,2),(2,4) \in C$ but $(3,3) \notin C$.
Yuval Filmus's user avatar
  • 14.5k
3 votes
Accepted

Are there specific examples of integral polyhedra that are neither Totally Unimodular nor Total Dual Integral?

I'm only going to talk about the constraint matrix part of the problem, I don't know much about the linear system (TDI) part. Call a matrix $A$ good if $\{x|Ax\leq b,x\geq 0\}$ is a integral polytope ...
Chao Xu's user avatar
  • 4,479

Only top scored, non community-wiki answers of a minimum length are eligible