# Tag Info

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

### 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 ...
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 [...
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-...
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 ...
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 ...
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{...
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^* = {...
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 ...
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$.
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
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).

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