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
Related Tags
optimization × 1698algorithms × 849
graphs × 238
complexity-theory × 130
linear-programming × 105
dynamic-programming × 103
combinatorics × 96
np-hard × 78
scheduling × 78
approximation × 70
np-complete × 66
time-complexity × 65
machine-learning × 62
computational-geometry × 60
integer-programming × 60
greedy-algorithms × 59
reference-request × 58
knapsack-problems × 53
heuristics × 49
genetic-algorithms × 44
search-algorithms × 40
traveling-salesman × 40
sets × 39
data-structures × 37
network-flow × 35