5 votes
Accepted

Stable marriage problem with only one side having preferences

The answer to your first question is: yes, there is a simple augmentation. It is described in the standard literature on the stable marriage problem. See the Wikipedia article for references in the ...
user avatar
  • 141k
5 votes

How can I solve this constrained assignment problem?

This can be formulated as an instance of minimum-cost flow problem. Have a graph with one vertex per agent, one vertex per task, and one vertex per category. Now add edges: Add an edge from the ...
user avatar
  • 141k
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 ...
user avatar
  • 1,777
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: "...
user avatar
4 votes

Seating arrangement problem

Assuming that you are trying to maximize the seating preferences, this problem is NP-Hard =(. NP-Hardness Specifically, consider the decision version of this problem: Given a matrix of preferences, ...
user avatar
  • 205
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,...
user avatar
  • 141k
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 ...
user avatar
  • 141k
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 ...
user avatar
  • 5,900
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 ...
user avatar
  • 141k
3 votes
Accepted

An algorithm to find the maximum profitable assignment

Your problem is known as the assignment problem.
user avatar
3 votes

Minimizing the overall cost over groups

You are probably looking for a solution to the following optimization problem. Weighted maximum biparite matching. Given a weighted bipartite graph $G=(U\cup V, E)$ with weights $w\colon U\times V \...
user avatar
3 votes
Accepted

What makes an MILP problem solvable?

You may be interested in reading about total unimodularity. An ILP is solvable in polynomial time if the associated matrix is totally unimodular (sufficient but not necessary condition). This explains ...
user avatar
3 votes

Hungarian Assignment Algorithm Implementation

The article you linked assumes that the reader knows how to apply the Hungarian algorithm on a similarity matrix because they have note in the introduction to Section 3 that Zager et. al. used the ...
user avatar
  • 254
3 votes

How many combination of “n” bits are there in terms of n?

Each bit can be either 0 or 1, so you have two choices per bit. That gives you 2^n combinations. E.g. n=1 implies 2^1=2 states, n=2 implies 2^2=4 states. You could arrive at this by 1) making a ...
user avatar
  • 131
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 ...
user avatar
  • 141k
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 ...
user avatar
  • 141k
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 ...
user avatar
  • 1,730
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 ...
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 ...
user avatar
  • 242
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.
user avatar
  • 12.3k
2 votes
Accepted

Choice of algorithm for hierarchical clustering for minimizing network communication costs

This is a form of assignment problem; in particular, it is an instance of quadratic assignment problem. There are some known techniques available for solving this sort of problem. Using integer ...
user avatar
  • 141k
2 votes
Accepted

Stable marriage problem preferential to asking side

One place to look at is the classic book The stable marriage problem. The link provides a relevant excerpt, showing that the matching produced by the standard Gale–Shapley algorithm is male optimal ...
user avatar
2 votes

How many combination of “n” bits are there in terms of n?

These are two separate questions. How many possible combinations of "n" bits are there? Well, bit 1 can take any of the two values (so there's 2 possibilities for bit 1); for any of them, bit 2 can ...
user avatar
  • 2,209
2 votes

$k$-gifts problem

Here's a hint for $k=2$. Let $P = \{p_i : i\in [n]\}$ be the set of prices. In any solution $\{p_i,p_j\}$ with $p_i \le p_j$, you have $p_i \le d/2$ and $p_j\ge d/2$. Split $P$ into $A = \{ a\in P : ...
user avatar
  • 2,886
2 votes
Accepted

$k$-gifts problem

Get the naive approach out of the way: We have a set of $n$ candidate toys, out of which we need to select $k$ such that the total cost is equal to $d$. Lets consider the most naive approach to check ...
user avatar
  • 506
2 votes

Algorithm to solve job assignment problem

Instead of putting x, put some very high cost values in those cells. Then the Hungarian algorithm avoids selecting those cells automatically (if that's possible).
user avatar
  • 121
2 votes
Accepted

Algorithm for a list of best solutions to the Assignment problem

Here's one technique to enumerate the best $n$ assignments, for any instance of the assignment problem. I suspect my approach isn't optimal, but it does run in polynomial time: it uses $O(nm)$ ...
user avatar
  • 141k
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$ ...
user avatar
  • 521
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 ...
user avatar
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 ...
user avatar
  • 280

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