New answers tagged optimization
2
votes
Find Minimum Transformation Between Multisets of Lists of Cards
Update (or possible correction) to the answer of D.W..
Since we are given the move operations and not the swap operations, we can compute $\pi$ in polynomial time. The problem is known as the ...
- 5,827
5
votes
Accepted
Find Minimum Transformation Between Multisets of Lists of Cards
I think the variant with sets can be solved using bipartite matching.
Build a complete bipartite graph, with one left vertex per set in s0 and one right vertex per set in s1. Also, if there are fewer ...
D.W.♦
- 156k
0
votes
Hardness of approximation for Disjoint Group Steiner Tree
As noted in the second paragraph of section 18.2 of these lecture notes, https://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec18.pdf, one can actually assume that the groups are ...
- 471
0
votes
Accepted
Maximum reachable checkers on a checkerboard
One approach would be to express this as an instance of SAT, and use an off-the-shelf SAT solver. See Boolean constraints for a connected component of a graph for a technique for encoding ...
D.W.♦
- 156k
0
votes
Optimizing Delivery Routes in a Graph-Based Network to Minimize Maximum Delivery Time
The problem is unlikely to admit any efficient solution since it is NP-Hard even when there is only one delivery person and, for all edges $(u,v)$ in the graph, the distance between $u$ and $v$ is $1$....
- 28.4k
3
votes
Accepted
Optimal torch placement in voxel games
No, assuming $\mathsf{P} \neq \mathsf{NP}$ there is no efficient algorithm for optimal torch placement, even if the world is just a 2D grid.
This can be shown by providing a reduction from the vertex ...
- 28.4k
Top 50 recent answers are included