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: ...
Andras Farago's user avatar
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'|$. ...
Yury's user avatar
  • 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 ...
usul's user avatar
  • 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 ...
Emil Jeřábek's user avatar
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 ...
saisandeep's user avatar
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

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 ...
Andras Farago's user avatar
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

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 ...
David Eppstein's user avatar
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....
Clement C.'s user avatar
  • 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. ...
Chao Xu's user avatar
  • 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, ...
Neal Young's user avatar
  • 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
Kristoffer Arnsfelt Hansen's user avatar
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
  • 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 ...
Sasho Nikolov's user avatar
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. ...
Aryeh's user avatar
  • 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 ...
Neal Young's user avatar
  • 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.
Chandra Chekuri's user avatar
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....
Edward Kirton's user avatar
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 ...
Andrew Morgan's user avatar
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 $...
usul's user avatar
  • 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 ...
Gamow's user avatar
  • 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 ...
Gamow's user avatar
  • 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 ...
Avi Tal's user avatar
  • 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/
Hermann Gruber's user avatar
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 ...
Louis's user avatar
  • 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 ...
Louis's user avatar
  • 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 ...
Highheath's user avatar
  • 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$. ...
Neal Young's user avatar
  • 9,595

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