# Tag Info

5

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 literature where this is described. It is also described here: The stable marriage algorithm with asymmetric arrays. See also https://cs.stackexchange.com/a/...

5

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 assuming integer weights bounded by $N$): Deterministic time $O(n^2 \sqrt n \log N)$. Randomized $O(n^{2.373} N)$. $(1 - \epsilon)$-approximation in $O(n^2 \... 5 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: "Data structures for weighted matching and nearest common ancestors with linking" (Gabow 1990) is the best "in theory" with$O(nm + n^2\log n)$time complexity. "... 4 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 source to each agent, with capacity 1 and cost 0. Add an edge from each agent to each task, with capacity 1 and cost according to the cost of that assignment. Add ... 4 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, is there some way to assign people to seats such that the total score (sum of resulting preferences of professors to their nearby neighbors) obtained is at or ... 4 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, then apply an off-the-shelf ILP solver. Introduce zero-or-one variables$x_{i,j}$, with the goal that$x_{i,j}=1$means that the$i$th person is assigned to$...

4

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 circles (there might be multiple possibilities, in case of a tie), and vice versa. For example triangle 1 can only be matched to circle 1 or 2; triangle 2 can only ...

4

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

3

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 of which box each item is matched to; you just have a list of what's allowed or disallowed.) There are efficient algorithms: use the Hungarian algorithm, or any ...

3

Your problem is known as the assignment problem.

3

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 \rightarrow \mathbb{N}$, find a set of edges $A\subseteq U\times V$ such that all edges in $A$ are disjoint (that is, no two edges are adjacent, that is, no group ...

3

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 the tractability of assignment and maximum flow problems. I'm not aware of any "reason" why knapsack is pseudopolynomial time solvable.

3

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 Hungarian algorithm for this purpose in the paper here. Furthermore, there is no requirement in the Hungarian algorithm that necessitates integral entries; ...

3

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 lexicographic list of all the combinations or 2) using a formula from combinatorics. Your second question seems to address representing integers with binary numbers. ...

3

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 total profit of the best assignment for times $i,i+1,\dots,m$, assuming that at time $i$ the agent is assigned to task $j$. We'll compute all of the $T[i,j]$ ...

3

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 second goal. I can see two possible approaches: (a) use integer linear programming (ILP), (b) use network flow. The former will be simple to implement, and ...

3

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 all these weights to get the best global result. Only the overall result matters even if it means some individual assignements have a very bad fitness/cost. In ...

3

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 source $S$ a sink $T$ and the corresponding bipartite graph in the middle. Note that each edge has two values $f/c$ which denote maximum flow allowed through this ...

3

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 to find a set of edges that uses every vertex exactly once. This is the perfect matching problem. To solve this problem, you can use any algorithm for finding ...

3

See Michael Z. Spivey, "Asymptotic Moments of the Bottleneck Assignment Problem," Mathematics of Operations Research, 36 (2): 205-226, 2011.

2

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 linear programming One approach is to use integer linear programming. Let $d_{p,q}$ denote the amount of data communicated between processes $p$ and $q$, for each ...

2

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 and female pessimal: any man gets the best possible partner (in his view) he can get in any perfect matching, and any woman gets the worst possible partner (in ...

2

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 take any of the two values (so there's 2*2 possibilities for bits 1,2); for any of the combinations of bits 1 and 2, bit 3 can take any of the two values, etc. ...

2

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 : a\le d/2\}$ and $B = \{b \in P : b > d/2\}$. If $A$ and $B$ are sorted, you can find if there is an $a\in A$ and $b\in B$ with $a + b = d$ in $O(n)$ time.

2

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 if $k$ such toys: exhaustively consider all $\binom{n}{k}$ possible combinations of toys and for each such $k$-set check whether the total price is equal to $d$....

2

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

2

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)$ invocations of the Hungarian algorithm, where $m$ denotes the number of agents in the problem instance. In your example, $m=26$, so my approach requires $O(n)$ ...

2

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$ constraints. Let $m=\lceil \log_2 k\rceil$ and $x_i = b_{im}, b_{i(m-1)}, \dots, b_{i1}$, where $m$ is the high bit and $1$ is the low bit. Define $d_{ij} = b_{ij}\... 2 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 and Path Finding for Teams of Agents." http://idm-lab.org/bib/abstracts/papers/aamas16a.pdf 2 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 the$i$th time period. The edges are as follows.$\$E=\{(a,v_{11}),(a,v_{12}),\dots,(a,v_{1n})\}\cup\\\{(v_{ij},v_{(i+1)j'})\vert 1\leq i<m,1\leq j\leq n, 1\...

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