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,595
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.9k
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
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
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.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.9k
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,451
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
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.3k
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
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,429
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,595
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,772
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,772
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
4
votes
Where to find info on (polytime) approximability of various discrete optimization problems?
The following website seems to be no longer maintained, but it is still a useful resource because it covers many problems: http://www.csc.kth.se/~viggo/problemlist/
- 5,840
4
votes
Accepted
Is this edge orientation optimization problem NP-hard?
I believe that this problem is NP-hard, here is a sketch proof (don't hesitate to ask for more details if needed).
The idea is based on a reduction from the Not-all-equal 3-SAT. For $\varphi$ a 3-SAT ...
- 775
4
votes
Is that edge orientation optimization problem NP-hard?
Definition: Given an undirected graph $G$ and an edge orientation $\vec{G}$, an unstable path is a directed path that goes from a node $s$ to a node $t$, such that the out-degree of node $s$ is ...
- 775
4
votes
Accepted
TSP with "enemy" nodes
As TSP is an optimization problem, there are not many variants of it (that I know of) that add hard constraints to the formulation. But if I have understood correctly, your problem is a special case ...
- 211
4
votes
Accepted
Partition the edges of a bipartite graph into perfect $b$-matchings
Here's a counter-example for $k= 4$.
Take $G = K_{2,2}$, specifically $G=(V, E)$ where $V=\{1,2,3,4\}$ and $E=\{(1,3), (1, 4), (2,3), (2,4)\}$.
Define $b^1$ by $b^1_1 = b^1_3 = 1$ and $b^1_2=b^1_4=0$.
...
- 9,595
Only top scored, non community-wiki answers of a minimum length are eligible