The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
2answers
50 views

What is the appropriate algorithm for bipartite matching with constraints?

I have a problem that is a bit complex, and I don't know what method/model I should use to express it (much less solve it). Let's say we have a lot of employees and a few jobs to be done. Each ...
0
votes
1answer
30 views

What makes an MILP problem solvable?

Knapsack problems, Assignment problems can all be expressed as (MILP) mixed integer linear programs. MILP is NP-complete. But Knapsack problem is solvable in pseudo-polynomial time using dynamic ...
0
votes
0answers
25 views

Assignment Algorithm according to Habr ā€“ an alternative for the Hungarian Algorithm?

I've implemented the Hungarian Algorithm (aka Kuhn-Munkres-Algorithm) for a project, according to this Wikipedia article. It works fine, but has O(n3) time complexity. I use the method to generate a ...
0
votes
0answers
35 views

Utility Maximizing Challenging Assignment Problem

There is a grid of size MxN. M~20000 and N~10. So M is very huge. So one way is to look at this is N grid blocks of size M placed side by side. Next assume that there are K number of users who each ...
1
vote
1answer
56 views

Matching a set of paths to an incrementally generated graph

I am working on an approximate matching problem, where I have a set of paths in an unknown graph (A) and a partial graph (B), where B is generated incrementally during the matching process (and can be ...
2
votes
2answers
52 views

$k$-gifts problem

Consider the following problem: Suppose you have $k$ nephews and $d$ dollars in your pocket all of which you need to spend. Given a set of $n$ toys with different prices, find whether there exists ...
0
votes
2answers
77 views

How many combination of ā€œnā€ bits are there in terms of n?

How many combination of "n" bits are there in terms of n? And if this is derived, Given 4 bits for representing negative and positive numbers, what is the largest positive number that can be ...
-3
votes
1answer
79 views

Hates Pepole Nice Algorithm [closed]

Some people in n groups, hates from each others. the hates relation are symmetric. (a hates b, b hates a, also). suppose we know list of all people that hates from ...
-1
votes
2answers
112 views

Show this is a tautology without using a truth table

I am doing a homework assignment and I've been stuck on this question for a long time now. The question says to prove this equation is a tautology without using a truth table. I assume we have to use ...
0
votes
0answers
57 views

Stable Marriage or Assignment Problem?

I have a question pertaining to committee selection. Let $C = c_{1}, c_{2}, \ldots, c_{n}$ be n Committees and $S = s_{1}, s_{2}, \ldots, s_{m}$ be m Students. Each $c_{i}$ in C ranks their ...
1
vote
0answers
25 views

What needs to be done after deleting an item in a hash table built under opening addressing with linear probing

In some textbook problems, the problem asks me to insert a bunch of elements and remove a bunch of elements. Insertion is done using linear probing, i.e. h = XmodR + I, when there is a collision, I ...
0
votes
2answers
124 views

How can I solve this constrained assignment problem?

The assignment problem is defined as follows: There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on ...
1
vote
1answer
97 views

Hungarian Assignment Algorithm Implementation

I want to implement the "vertex similarity" algorithm described in the paper Graph Isomorphism Detection Using Vertex Similarity Measure. The algorithm is as follows: ...
2
votes
1answer
268 views

Stable marriage problem with only one side having preferences [duplicate]

I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and ...
2
votes
1answer
58 views

Choice of algorithm for hierarchical clustering for minimizing network communication costs

Suppose I have a large distributed task running on a cluster system where part of the workload is compute bound and part depends on network performance. Data transfer is not completely homogeneous ...
0
votes
1answer
66 views

Stable marriage problem preferential to asking side

Watching this youtube video: https://www.youtube.com/watch?v=w1leqkpDaRw it described the problem with the stable marriage problem, that the asking side get a better deal then the asked site. Meaning ...
0
votes
1answer
40 views

Algorithm for distributing members over activites (with individual preferences)

So in my school we have a day where everybody participates in different activities. Each projects can have like 10 members. The whole day is divided in 2 or 3 different blocks, in which the pupils ...
-4
votes
1answer
75 views

I don't understand a lot of things about computer scince [closed]

I'm not sure that this is the proper place to ask those question but I will do it anyway. So the first question will be is there really a need of CS in the market(a lot of people say that in eastern ...
2
votes
1answer
303 views

A variant of job assignment (scheduling) problem with variable time span

The problem is a scheduling problem with n jobs and k machines. Each job i can be started at any time, but its duration is not exactly known except a time span interval. For example, a job may take ...
0
votes
0answers
249 views

Algorithm to solve job assignment problem

Can someone suggest an algorithm to solve job assignment problem with condition? With condition means that some jobs cannot be done by some workers. For example table as shown below: In this table ...
2
votes
0answers
179 views

Job assignment problem

I want to solve job assignment problem using Hungarian algorithm of Kuhn and Munkres in case when matrix is not square. Namely we have more jobs than workers. In this case adding additional row is ...
3
votes
1answer
287 views

Assignment problem with no cost

I have a problem that I was able to conceptualize as following: Problem We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination ...
6
votes
4answers
333 views

XOR-like behavior in flow networks

XOR is not the correct name, but I am looking for some kind of exclusive behavior. I am currently solving a set of different (assignment) problems by modeling flow networks and running a ...
9
votes
1answer
507 views

Assignment problem for multiple days

I have a problem that can be reduced to an assignment problem. (In a previous question i found out how to do that.) Which means we have a set $A$ of agents and a set $T$ of tasks as well as a cost ...
6
votes
2answers
377 views

A variant of the Assignment Problem

In my variant of the assignment problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task ...
3
votes
1answer
434 views

Simple Task-Assignment Problem

I have this simple 'assignment' problem: We have a set of agents $A = \{a_1, a_2, \dotso, a_n\}$ and set of tasks $T= \{t_1, 1_2, \dotso, t_m\}$. Note that $m$ is not necessarily equal to $n$. Unlike ...