Assignment Problem (Weighted Bipartite Matching)

No algorithm description given

The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching in a weighted bipartite graph. In its most general form, the problem is 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 the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the total cost of the assignment is minimized. If the numbers of agents and tasks are equal and the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called the linear assignment problem. Commonly, when speaking of the assignment problem without any additional qualification, then the linear assignment problem is meant. This API is based on this Hungarian Algorithm implementation . The complexity is N ^3 . Example Say you have three workers: Jim, Steve, and Alan. You need to have one of them clean the bathroom, another sweep the floors, and the third wash the windows. What’s the best (minimum-cost) way to assign the jobs? First we need a matrix of the costs of the workers doing the jobs: Clean bathroom Sweep floors Wash windows Jim $3 $3 $3 Steve $3 $2 $3 Alan $3 $3 $2 When applied to the above table, the algorithm gives the minimum cost it can be done with: Jim washes the windows , Steve sweeps the floors, and Alan cleans the bathroom . Input A weighted graph in the form Map<String, Map<String, Double>>, in which each key is a node name, and its value is a map that links each neighbour to the weight (which may be positive, negative, or zero) of the edge connecting the two. If node B does not appear in the map corresponding to node A, the weight of the edge connecting them is assumed to be zero. Note: in the list you can include all the nodes (like in the example), or only those in one group of the bipartite graph (in the example this'd mean that it's enough to specify the Jim, Steve and Alan keys). Output An object with two keys: assignment : this is a Map<String, String>, in which each key is a node and its value is the name of the node it is assigned to weight : the total weight of the matches

Tags
(no tags)

Cost Breakdown

0 cr
royalty per call
1 cr
usage per second
avg duration

Cost Calculator

API call duration (sec)
×
API calls
=
Estimated cost
per calls
for large volume discounts
For additional details on how pricing works, see Algorithmia pricing.

Internet access

This algorithm has Internet access. This is necessary for algorithms that rely on external services, however it also implies that this algorithm is able to send your input data outside of the Algorithmia platform.


To understand more about how algorithm permissions work, see the permissions documentation.

1. Type your input

2. See the result

Running algorithm...

3. Use this algorithm

curl -X POST -d '{{input | formatInput:"curl"}}' -H 'Content-Type: application/json' -H 'Authorization: Simple YOUR_API_KEY' https://api.algorithmia.com/v1/algo/Aluxian/AssignmentProblemWeightedBipartiteMatching/0.1.0
View cURL Docs
algo auth
# Enter API Key: YOUR_API_KEY
algo run algo://Aluxian/AssignmentProblemWeightedBipartiteMatching/0.1.0 -d '{{input | formatInput:"cli"}}'
View CLI Docs
import com.algorithmia.*;
import com.algorithmia.algo.*;

String input = "{{input | formatInput:"java"}}";
AlgorithmiaClient client = Algorithmia.client("YOUR_API_KEY");
Algorithm algo = client.algo("algo://Aluxian/AssignmentProblemWeightedBipartiteMatching/0.1.0");
AlgoResponse result = algo.pipeJson(input);
System.out.println(result.asJsonString());
View Java Docs
import com.algorithmia._
import com.algorithmia.algo._

val input = {{input | formatInput:"scala"}}
val client = Algorithmia.client("YOUR_API_KEY")
val algo = client.algo("algo://Aluxian/AssignmentProblemWeightedBipartiteMatching/0.1.0")
val result = algo.pipeJson(input)
System.out.println(result.asJsonString)
View Scala Docs
var input = {{input | formatInput:"javascript"}};
Algorithmia.client("YOUR_API_KEY")
           .algo("algo://Aluxian/AssignmentProblemWeightedBipartiteMatching/0.1.0")
           .pipe(input)
           .then(function(output) {
             console.log(output);
           });
View Javascript Docs
var input = {{input | formatInput:"javascript"}};
Algorithmia.client("YOUR_API_KEY")
           .algo("algo://Aluxian/AssignmentProblemWeightedBipartiteMatching/0.1.0")
           .pipe(input)
           .then(function(response) {
             console.log(response.get());
           });
View NodeJS Docs
import Algorithmia

input = {{input | formatInput:"python"}}
client = Algorithmia.client('YOUR_API_KEY')
algo = client.algo('Aluxian/AssignmentProblemWeightedBipartiteMatching/0.1.0')
print algo.pipe(input)
View Python Docs
library(algorithmia)

input <- {{input | formatInput:"r"}}
client <- getAlgorithmiaClient("YOUR_API_KEY")
algo <- client$algo("Aluxian/AssignmentProblemWeightedBipartiteMatching/0.1.0")
result <- algo$pipe(input)$result
print(result)
View R Docs
require 'algorithmia'

input = {{input | formatInput:"ruby"}}
client = Algorithmia.client('YOUR_API_KEY')
algo = client.algo('Aluxian/AssignmentProblemWeightedBipartiteMatching/0.1.0')
puts algo.pipe(input).result
View Ruby Docs
use algorithmia::*;

let input = {{input | formatInput:"rust"}};
let client = Algorithmia::client("YOUR_API_KEY");
let algo = client.algo('Aluxian/AssignmentProblemWeightedBipartiteMatching/0.1.0');
let response = algo.pipe(input);
View Rust Docs
Discussion
  • {{comment.username}}