16
votes
Easy to optimize but hard to evaluate
Here is an example, where one can produce a solution in polynomial time, but evaluating a given solution is NP-hard.
Input: Positive integers $n,k$ (in unary encoding), with $k\leq n$.
Task: ...
- 11.3k
14
votes
Accepted
Is the following graph optimization problem approximable within a constant factor?
The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. ...
- 3,899
10
votes
Accepted
Find research partner (profession and beginner)
I don't know of such a page. Most researchers have specific problems that they are interested in working on, and would only want to collaborate on those. If you pick a particular area and focus on ...
- 7,525
9
votes
Accepted
Positivstellensatz and sum of squares method
As already noted in the comments, the question is based on a misunderstanding; the actual Positivstellensatz is a stronger statement than Artin’s theorem on nonnegative polynomials, and the real ...
- 16.5k
9
votes
Accepted
Minimum weight matching in general graphs with additional input specifying the number of matched edges
Add $n-2k$ extra vertices, each connected to all the original vertices with zero-weight edges, and add a large enough number $W$ to each of the original edges to make their weights all positive. Then ...
- 50.8k
9
votes
Accepted
Proof that the graph optimization problem is NP-hard
This problem is in P, it can be reduced to the Minimum cut problem.
The graph construction is as follows - Add a source and a sink vertex. For each vertex $i$, add an edge with cost $w(i)$ from ...
- 126
8
votes
Accepted
Quantum annealing vs adiabatic quantum computation
Adiabatic quantum computing (AQC) is a computational model (as Peter said in the comments). Compare AQC with other models of computation such as:
circuit-based quantum computing (CBQC)
Adleman-...
- 541
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, ...
- 2,758
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
Accepted
Finding the two shortest paths while minimizing the number of nearby/common edges
If the cost is $|P_1|+|P_2|+|P_1∩P_2|$, then a simple reduction to the shortest pair edge disjoint paths gives us a polynomial time solution. For each edge $e=(u,v)$ add two edges $(u,uv)$ and $(uv,v)$...
- 3,440
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 ...
- 24.2k
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
6
votes
Accepted
Minimizing a submodular function given noisy oracle access
A FOCS'15 paper by Lee, Sidford, and Wong [LSW15] can be leveraged to obtain such minimization guarantees -- cf. Section 5 (specifically, Corollary 5.4) in our recent paper ([BCELR16]).
Corollary 5....
- 4,441
6
votes
Accepted
What do you call the join of two optimization problems?
I think this falls in the category of multi-objective function optimization problems.
To be specific, it's a linear scalarization of an optimization problem with two objective functions.
I don't ...
- 24.2k
6
votes
Accepted
Modifying Edmonds' Blossom Algorithm
You just have to solve the following problem: Find a matching of size exactly $k$ with minimum weight.
It can be solved by reducing to min weight perfect matching. See the paper by Ján Plesnı́k. ...
- 4,367
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, ...
- 9,595
6
votes
Accepted
Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries
NP-hardness is proved by Roth and Viswanathan in the paper On the hardness of decoding the gale-berlekamp code
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+\...
- 9,595
5
votes
Is the complexity of this covering problem known?
The problem is known as the propagation problem. Aazami has proved in his PhD thesis that the weighted version is NP-complete even when the graph is planar and the node weights are in $\{0,1\}$. The ...
- 1,026
5
votes
Centroid in $\ell_2$ distance
This is the geometric median problem. There is a nearly linear time algorithm based on interior point methods due to Cohen et al.: to find a $(1+\varepsilon)$-approximation their algorithm runs in ...
- 18.1k
5
votes
Accepted
Understanding the No Free Lunch Theorem
You're asking about optimization and universal search, BUT machine-learning is tagged and you're wondering about "a uniform distribution on an infinite" discrete set so perhaps this will be helpful. ...
- 10.2k
5
votes
Is that edge orientation optimization problem NP-hard?
Summary
OP's problem has a polynomial-time algorithm via reduction to min-cost bipartite matching. (Lemma 1, below.)
Alternatively, one can strengthen OP's relaxation QP directly, by modeling the ...
- 9,595
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.
- 6,979
4
votes
Good algorithms to solve ATSP
You can also transform the ATSP to TSP; the process requires doubling number of nodes (adding dummy cities).
http://www.sciencedirect.com/science/article/pii/0167637783900482
http://www.sciencedirect....
4
votes
Accepted
Maximizing a monotone supermodular function s.t. cardinality
I think this is an example showing no kind of approximation is possible except with exponential$(k)$ value queries.
Let $f(S) = 0$ if $|S| \leq k$, otherwise $f(S) = |S| - k$. Now pick a special set $...
- 7,525
4
votes
Accepted
Solution/Hardness of the following (integer) budgeted problem?
Solving this exactly this ends up being $\mathsf{NP}$-hard.
The reduction I have doesn't pay much attention to the representation of the $f_i$'s. That said, the values of $f_i$ I end up giving can be ...
- 1,419
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 ...
- 5,762
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 ...
- 5,762
4
votes
Sum From A List Of Numbers (Algorithm)
The problem is NP-Complete even for integer values. You can look up the "knapsack problem" to see why.
A pseudo-polynomial algorithm exists if you can map your N values to integers (if the number of ...
- 1,596
Only top scored, non community-wiki answers of a minimum length are eligible