Share Your Experience: Take the 2024 Developer Survey

# Tag Info

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

### What is the fastest static comparison sort? What is the proper term for "static"?

The answer by Display name explains why the model trivializes. However, let me add some pointers to established terminology: A query-based algorithm is called nonadaptive if all the oracle queries ...
• 17.7k
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,615
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 ...
• 17.7k
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

• 10.8k

### 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.2k
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.6k

### 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 ...
• 10.8k
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,999
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
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
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

### 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,606

### 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/
• 6,515
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

### 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
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
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$. ...
• 10.8k
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-...