New answers tagged

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$ ...
  • 149k
0 votes

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