The 2024 Developer Survey results are live! See the results

# Tag Info

### 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: "...
• 5,469
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 ...
• 1,807

### 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,...
• 162k

### 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 ...
• 162k
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 ...
• 5,961
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 ...
• 1,131
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 ...
• 1,788

### 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 ...
• 162k
Accepted

### An algorithm to find the maximum profitable assignment

Your problem is known as the assignment problem.
• 278k

### 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 ...
• 162k
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 ...
• 162k

### 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 ...
• 1,189
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 ...
• 277
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.
• 13.8k

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

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

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

### 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$ ...
• 553
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 ...
• 9,847
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 ...
• 162k
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 ...
• 3,397
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 ...
• 1,788

### 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). ...
• 162k

### 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 ...
• 91
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$, ...
• 162k
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 ...
• 162k
Accepted

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 ...
• 2,817

### 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 ...
• 2,521
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 ...
• 3,397
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 \$...