# Tag Info

6

There's a way to this in polynomial time. I'll sketch the algorithm (in reverse order ... do step 2 first and step 1 second). if we can find a set of $nk$ agent-task pairs $(i,j)$ such that each task is in exactly $k$ pairs, each agent is in exactly $k$ pairs, and no pair appears more than once, then we can find $k$ assignments that together cover these $nk$...

6

This can be formulated as an instance of min-cost (or in this case, max-profit) flow. Set up a network as follows. There will be four layers. The first layer is a single node we call the source. The next layer consists of a node for each agent. The next layer has a node for each task. The final layer is one node we call the sink. For each edge, we give a ...

5

In general, the answer is no. If we put XOR-like restrictions on the out-going edges of a vertex, we can prove that finding a min-cut-max-flow is NP-Hard. The technique is to reduce 3-SAT to it. Let's assume there are $n$ variables $x_1, x_2, ..., x_n$ in the 3-SAT and $m$ clauses $c_1, c_2, ..., c_m$. We create a graph $G(V,E)$ encoding the instance of the ...

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

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

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

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

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

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

For your first question, I do not know any general techniques or rules of thumb that you can use to model arbitrary restrictions in flow networks. Most examples I have seen are generally based on some intuition about the nature of restrictions, and often at first seem arbitrary. For your particular case, I have yet to come up with a good mapping to max-...

3

As I stated on the CSTheory post, this is solved via maximum matching. The following should give enough intuition to show that each agent $a_i$ has a $q_i$-matching iff a transformed graph $G'$ has a matching. First, construct the graph $G$. Now, for each agent $a_i$ and quota $q_i$, make a new graph $G'$ that has $q_i$ copies of $a_i$. That is to say, if ...

3

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

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

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

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]$ ...

2

To build on Paresh's answer, if all the max capacities are one (and everything else is integer), you could also split each node into two so that node (n-) has all the in edges, node (n+) has all the out edges, and (n-) and (n+) are connected with an edge of max capacity 1. Solve this new min-cost network and you are done. If the max capacities are not all ...

2

I searched for "job shop scheduling uncertain processing times" and came up with this: http://www.waset.org/journals/waset/v64/v64-190.pdf. I hope it helps. I think you will find that the best approximation algorithm is going to depend on the probability distribution of completion times. An algorithm for exponentially distributed times might be very ...

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

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

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

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

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

2

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

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