Skip to main content
The 2024 Developer Survey results are live! See the results
5 votes

Maximizing the sum of selected elements in a matrix

The problem you want to solve is (a slight variation of) maximum weighted matching in general (i.e., not necessarily bipartite) graphs. There are several algorithms with various worst-case bounds: "...
j_random_hacker's user avatar
5 votes
Accepted

Heuristic algorithms for the dense assignment problem

This paper has a painfully detailed table on what you can achieve using (currently known) deterministic, randomized and $\epsilon$-approximation algorithms. To summarize, for the bipartite case (all ...
aelguindy's user avatar
  • 1,807
4 votes

Working Optimization Algorithm

The simplest solution (in terms of saving you the time of understanding the literature) is probably going to be to use integer linear programming (ILP / MILP). You can formulate it as an ILP instance,...
D.W.'s user avatar
  • 162k
4 votes

How to match two sets of points based on the closeset distance?

Your problem statement is not very clear about whether the constraints are hard or soft. Hard constraints Suppose the constraints are hard: each triangle must be assigned to one of the closest ...
D.W.'s user avatar
  • 162k
4 votes
Accepted

How to match two sets of points based on the closeset distance?

You have an instance of a bipartite matching problem. There are some variations on the problem. I think you're looking for a minimum cost bipartite matching, but maybe you're looking for a stable ...
adrianN's user avatar
  • 5,961
4 votes
Accepted

Minimizing total distance traveled by points in points cloud transformation

If the trajectories must be lines and $\epsilon$ is small enough, the problem can be solved with min-cost matching. If all coordinates are integers with absolute value bounded by $H$, then two ...
Antti Röyskö's user avatar
3 votes
Accepted

Difference between stable marriage problem and assignment problem

The main difference is the optimization goal. In classical assignement problem, there is a fitness/cost function to maximize/minimize. Each assignement possibility has a weight and you only sum up ...
Optidad's user avatar
  • 1,788
3 votes

Algorithm for arranging elements into different sized buckets

Your problem can be solved in polynomial time. You mention two possible goals and say you'd be happy with a solution to either. The first goal isn't well-defined, so I'll describe a solution to the ...
D.W.'s user avatar
  • 162k
3 votes
Accepted

An algorithm to find the maximum profitable assignment

Your problem is known as the assignment problem.
Yuval Filmus's user avatar
3 votes

Polynomial time solution for bipartite matching

This actually has nothing to do with the stable marriage problem; it's an instance of bipartite matching. (It's not related to stable marriage, becuase you don't have an ordering on the preferences ...
D.W.'s user avatar
  • 162k
3 votes
Accepted

Discrete assignment problem with penalties

Riley's answer is excellent. It is possible to improve the running time further to $O(mn)$ time, using dynamic programming. This saves a factor of $n$ in the running time. Define $T[i,j]$ to be the ...
D.W.'s user avatar
  • 162k
3 votes

Assignment Problem -- finding the $k$ agents with the best assignment

The assignment problem can be extended to solve this problem. The regular problem without the $k$ restriction can be solved by building a Minimum Cost Maximum Flow network is as follow: We have a ...
Marcelo Fornet's user avatar
3 votes
Accepted

Algorithm for assigning people to groups

This problem is equivalent to Perfect Matching We can view the input as an almost-complete graph, with L as its vertices and every two vertices connected by an edge except for those in C. We then want ...
ADdV's user avatar
  • 277
3 votes
Accepted

Expected behavior in the min max random assignment problem

See Michael Z. Spivey, "Asymptotic Moments of the Bottleneck Assignment Problem," Mathematics of Operations Research, 36 (2): 205-226, 2011.
orlp's user avatar
  • 13.8k
2 votes

Discrete assignment problem with penalties

First, you can model the task management as a directed graph. Suppose you have a source node $a$, a sink node $b$, and $mn$ nodes, one for each task. We say that $v_{ij}$ represents the $j$th task on ...
Riley's user avatar
  • 280
2 votes

Optimality in multi-agent multi-target path finding

Read the following paper on the generalization of your problem with "makespan" as the objective. The proposed algorithm should work even if $m\neq n$. H. Ma and S. Koenig. "Optimal Target Assignment ...
AI researcher's user avatar
2 votes

Is there a greedy algorithm to solve the assignment problem?

The answer of your post question (already given in Yuval comment) is that there is no greedy techniques providing you the optimal answer to an assignment problem. The commonly used solution is the ...
Seb Destercke's user avatar
2 votes

CNF form of variable assignment problem

If you only have to encode this (and don't have any other constraints on $x_i$), you can then use the following constraints: $x_1 < x_2 < \dots < x_{n-1} < x_n \leq k$ which is $n$ ...
MotiNK's user avatar
  • 553
2 votes
Accepted

Algorithm for arranging elements into different sized buckets

Your problem is very similar to the Generalized Assignment Problem which is $NP$-complete. The Generalized Assignment Problem states, using the terminology of the Knapsack Problem: given $n$ items ...
fade2black's user avatar
  • 9,847
2 votes
Accepted

affinity based static load balancing

Yes, this can be solved efficiently using standard methods for bipartite matching and the assignment problem. Let me build up to a solution, so you can see the ideas underpinning it. If you want to ...
D.W.'s user avatar
  • 162k
2 votes
Accepted

find separate pairs of points with minimal total distance

Sort the items so that $s_1 \le s_2 \le \dots \le s_{N_S}$. Then: If $N_S$ is even, assign all the odd-numbered items to $A$, all even-numbered items to $B$, and pair the first item of $A$ with the ...
Vincenzo's user avatar
  • 3,397
2 votes
Accepted

Matching schedules between users and providers

I think your problem is actually not a scheduling problem but a set cover problem. Just cut the time line in the atomic time parts of providers and assign them indices. For instance, considring only ...
Optidad's user avatar
  • 1,788
2 votes

How to solve this very complicated assignment problem

I don't see a way to solve this using standard algorithms for the assignment problem. If you want an exact solution (i.e., the optimal solution), I would recommend integer linear programming (ILP). ...
D.W.'s user avatar
  • 162k
2 votes

Reduction from an assignment problem to an independent set problem: NP-hard

If you want to show that your problem is NP hard, your reduction should go in the other direction. You have to show: $\exists L \in NPH: L \le_M yourProblem$ where $NPH$ is the Set of NP-hard ...
Tomet's user avatar
  • 91
2 votes
Accepted

Algorithm to assign producers to consumers with respect to connections

I'm not sure I understand the problem statement, but it looks like this can be modelled as a network flow problem. Here's how. First, create a new source vertex $s_0$. Then, for each producer $p$, ...
D.W.'s user avatar
  • 162k
2 votes
Accepted

Min max solution to the random assignment problem

Yes, there is an efficient algorithm to find an assignment that minimizes the largest cost. Suppose we want to check whether there is an assignment with largest cost $t$. To do that, delete all ...
D.W.'s user avatar
  • 162k
2 votes
Accepted

variant of assignment problem with overload penalties instead of constraints

The complexity depends on the penalty function. When the penalty function $f(\cdot)$ is non-decreasing and convex i.e. $0 \le f(k+1)-f(k) \le f(l+1)-f(l)$ whenever $k \le l$, then this problem can be ...
pcpthm's user avatar
  • 2,817
2 votes

Given a sequence of sets, choose one element from each to get the lowest number of changes

You can just greedily take the element of the first set that appears in the most consecutive sets (decide equals arbitrarily). That's the first element of your solution. Then do the same for the next ...
Albert Hendriks's user avatar
2 votes
Accepted

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 ...
Vincenzo's user avatar
  • 3,397
2 votes
Accepted

High-multiplicity maximum-weight matching

You can solve this using min-cost flow. Construct a graph with a source vertex $s$, one vertex per person, one vertex per job, and one sink $t$. Add edges as follows: Add an edge of capacity 1 from $...
D.W.'s user avatar
  • 162k

Only top scored, non community-wiki answers of a minimum length are eligible