The 2024 Developer Survey results are live! See the results

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

### 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 ...
• 18.2k
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,738
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.9k
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

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

### 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.9k
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.
• 7,029
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

### NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix

This problem is NP-hard. In fact, even deciding whether there exists a choice of x such that all the dot products are positive is NP-complete. I show this below by reduction from set cover. Reduction ...
• 2,873
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,782
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,782

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

### 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,625
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.9k
Accepted

### Solving linear programs with special structure

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-...
• 10.9k