# Tag Info

### 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: ...
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'|$. ...
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 ...
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 ...
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 ...

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

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

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