New answers tagged optimization
1
The new metaheuristics are pretty much genetic algorithms and local search in disguise. And this is actually a problem and hinders progress. There is a good write-up on this topic by Sörensen, Kenneth. "Metaheuristics—the metaphor exposed." International Transactions in Operational Research 22, no. 1 (2015): 3-18.
The argument is that the "new&...
0
No, you can't infer that. You seem to be assuming that the optimization process tries one element of the search space, chosen uniformly at random, and hopes that it got lucky. But that's not how real optimization algorithms work. They try multiple solutions, and they're not chosen uniformly at random; they're typically chosen in some way that we hope is ...
1
Minimizing $\|\theta\|$ is equivalent to minimizing $\|\theta\|^2/2$, in the sense that the minimum is achieved for the same value of $\theta$. Since our goal is primarily to find $\theta$, this substitution is not unreasonable.
Why was the substitution done? I don't know. Perhaps because it makes the resulting optimization easier; or just because it ...
3
I suspect that if the points in your set are expressed as $Ax \le b$ and you're considering the Euclidean distance, then you can solve the following quadratic program with the ellipsoid method:
$$
\max \sum_i (x^2_i+y^2_i-2x_i y_i) \\
Ax \le b \\
Ay \le b.
$$
Where we used the fact that optimizing $|x-y|$ is the same as optimizing $ \frac{1}{2} |x-y|^2 = \...
0
Construct a graph $G=(V,E)$ where $V$ contains two nodes $s$ and $t$, a node $u_x$ for each hospital $x \in X$, and a node $v_y$ for each home $y \in Y$.
There is an edge between $s$ and each $v_y$ of capacity 1.
There is an edge of capacity $10000$ between each $u_x$ and $t$.
Moreover, there is an edge $(v_y, u_x)$ if an only if $y$ is within $50$ miles ...
1
The problem is NP-hard. Consider the following special case: there is only one server, and its radius is infinite (or very large). Then your problem becomes the problem of finding an independent set in a planar graph. That problem is known to be NP-hard. Since a special case of your problem is NP-hard, then your problem must be at least as hard in the ...
3
Here is a proof that the problem remains hard when $k=1$. For simplicity it uses an item of size equal to the bin capacity. If you require each item to be smaller than the bin capacity you can subtract a small enough constant from this item's size.
Consider an instance of $3$-partition in which $3n$ positive integers $x_1, x_2, \dots, x_{3n}$ of total sum $...
2
If the greediness here means moving on the input based on a specified score, and computation of the input item's score is polynomial, the answer is yes. It is correct. Because moving on the input with $n$ items is linear, and if the scoring computation for each item will be polynomial, as sorting them will be polynomial as well; finally, we can solve the ...
3
As Yuval Filmus points out, this is an optimization version of the PARTITION problem. The problem is weakly NP-complete, so any polynomial time solution to your problem would immediately solve partition (simply check if the minimum difference between the sums of the two sets is $0$).
You can solve the problem in pseudo-polynomial time $O(nS)$, where $S$ the ...
1
Let's consider a configuration to be the location of all tiles, i.e., a state of the board at a particular time. To be valid a configuration must satisfy four requirements: (1) every tile (other than the starter tile) must be adjacent to at least two other tiles; (2) adjacent tiles must have the same color at the edge they share; (3) the red edges must form ...
3
Let $s_i$, $e_i$, $x_i$, be the shift start time, shift end time, and experience of the $i$-th worker.
For each worker define the following two events:
A shift-start event is a triple $(s_i, 0, i)$.
A shift-end event is a triple $(e_i, 1, i)$.
Collect all events in an array $E$ and sort it in increasing order (lexicographically). This requires $O(w \log w)$...
Top 50 recent answers are included
