New answers tagged optimization
0
votes
Ordered open-end knapsack problem optimised for minimum weight range
This can be solved with dynamic programming. Let $W[1,\dots,n]$ denote the weights of the items. Fix a value of $\ell$. Define the array $A[\cdot,\cdot]$ as
$A[i,j] = $ the smallest value of $h$ ...
D.W.♦
- 149k
0
votes
Accepted
Algorithm for a modified worker-task assignment problem with groups of tasks and substitutability between tasks within groups
You can solve this problem as follows. Build a bipartite graph with one vertex per worker and one vertex per group of tasks (one vertex for the entire group; not one vertex per task). The cost of ...
D.W.♦
- 149k
1
vote
What data structure/s can I use for fastest lookup of a permutation between two arrays of pairs (preserving order)?
If I understand correctly, we can reformulate your problem as following:
We have a database that contains a set of sets $S_1,\dots,S_n$. You are given an input set $I$. The goal is to determine ...
D.W.♦
- 149k
0
votes
For what applications of the traveling salesman problem, does visiting each city at most once truely matter?
Imagine in real life an area full of mountains. Every village has a short connection to a central point X, but all other connections between villages are very, very long, due to the mountains. The ...
- 26.8k
2
votes
A kind of generalised assignment problem where we minimise error relative to a goal "weight"/"value" - how to solve it?
The problem you describe is strongly NP-hard since it generalizes the 3-PARTITION problem. Hence you can expect no efficient algorithm for it, unless P = NP.
To see that it generalizes the 3-PARTITION ...
- 3,212
1
vote
Minimal Number of Transactions to Settle Outstanding Poker Game
This problem is strongly NP-hard.
A set of transactions can be regarded as a directed graph. Let $A$ be the set of vertices corresponding to players with positive losses and let $B$ be the set of ...
- 2,080
Top 50 recent answers are included