Concept
Hungarian algorithm
Related publications (9)
Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
Adam Teodor Polak, Alexandra Anna Lassota
We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...
Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022How to Match in Modern Computational Settings
Buddhima Ruwanmini Gamlath Gamlath Ralalage
This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information.First, we consider two stochastic models called query-commit and price-of-information where the algori ...
EPFL2021Asymptotically Optimal Matching of Multiple Sequences to Source Distributions and Training Sequences
Consider a finite set of sources, each producing independent identically distributed observations that follow a unique probability distribution on a finite alphabet. We study the problem of matching a finite set of observed sequences to the set of sources ...
Institute of Electrical and Electronics Engineers2015Sponsored Search, Market Equilibria, and the Hungarian Method
Monika Henzinger, Ingmar Weber, Paul David Dütting
Two-sided matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market where n advertisers compete for the assignment of one of k sponsored search results, also known as "slots", for certain key ...
2010