8
votes
Accepted
Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable
The answer to the second question is no. Here is an example when the integer-output optimization problem is polynomial-time solvable, yet its fractional relaxation is NP-complete:
In complements of ...
- 11.3k
7
votes
What is this graph problem, and how hard is it?
In "Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem" [Comput. Oper. Res. 51, 2014, pp. 123–129] the authors Abraham Duarte, Manuel Laguna, Rafael ...
- 50.8k
4
votes
Accepted
What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?
Regarding the title of the question:
What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?
and in particular the statement in the body:
There is an ever [...
- 1,063
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-...
- 9,595
3
votes
Accepted
A bound that follows from submodularity
The following lemma implies the inequality in question.
Lemma 1. $E[f_{R\setminus \{a\}}(a)] \le E[f_{R\setminus\{a\}}(a) \,|\, a \in R]$
Proof. Consider the following experiment:
Let $R$ be ...
- 9,595
2
votes
Accepted
Can the ellipsoid method be used with a randomized separation oracle?
Yes, given your conditions the probability of a correct result is at least $(1-\epsilon)^T$.
This seems to follow from standard calculations, so maybe I am missing something. Here are the ...
- 9,595
1
vote
Accepted
Linear Programming Sensitivity to Matrix
Okay I think I have figured this out! I am going to assume we have primal and dual problems:
\begin{array}?
(P) &&\max& c^Tx &&& (D) &&\min& b^Ty \\
&&\text{...
- 206
1
vote
Linear Programming Sensitivity to Matrix
Let $u$ and $v$ be vectors of slack variables for the primal and dual, respectively. Thus $A x^* + u = b$ and $A^T y^* - v = c$. Then we can see that
\begin{equation}
\nu = c^T x^* = (Ay^*-v)^Tx^* = {...
- 206
1
vote
Solving Grouped Weighted Job Scheduling with Release Times and Deadlines on a Single Machine with Multiple Availability Intervals
Your problem can be formulated as an instance of the weighted interval scheduling problem (WISP), which is a well-studied problem in the literature. In WISP, we are given a set of jobs with release ...
- 14k
1
vote
An inequality about median of points in higher dimensions
Yes. By the triangle inequality, $\|x-z\| \le \|x-m\| + \|m -z\|$, which implies the desired inequality (with $K=1$) for any $m$ and $z$.
- 9,595
1
vote
Is that edge orientation optimization problem NP-hard?
Note that the related problem pointed in the motivation of the original post is NP-hard. The proof is available in the Annex B of this paper: https://arxiv.org/pdf/2203.04774.pdf
- 121
1
vote
Is this node permutation optimization NP-Hard?
The proof that this problem is actually NP-hard is available in the Annex B of this paper (thanks to Louis' work).
- 121
Only top scored, non community-wiki answers of a minimum length are eligible