Publications related to Hungarian algorithm

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 Informatik2022

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Adam Teodor Polak

One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Asymptotically Optimal Matching of Multiple Sequences to Source Distributions and Training Sequences

Jayakrishnan Unnikrishnan

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 Engineers2015

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

Yuri Faenza, Gautier Stauffer

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(vertical bar V vertical bar (vertical bar E vertical bar+vertical bar V vertical bar log vertical bar V vertical bar))-time, drastically improvin ...

Assoc Computing Machinery2014

Population Sensing Using Mobile Devices : a Statistical Opportunity or a Privacy Nightmare?

Farid Movahedi Naini

In our daily lives, our mobile phones sense our movements and interactions via a rich set of embedded sensors such as a GPS, Bluetooth, accelerometers, and microphones. This enables us to use mobile phones as agents for collecting spatio-temporal data. The ...

EPFL2014

Hungarian algorithm

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Asymptotically Optimal Matching of Multiple Sequences to Source Distributions and Training Sequences

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

Population Sensing Using Mobile Devices : a Statistical Opportunity or a Privacy Nightmare?

Sponsored Search, Market Equilibria, and the Hungarian Method

Graph Chatbot

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Asymptotically Optimal Matching of Multiple Sequences to Source Distributions and Training Sequences

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

Population Sensing Using Mobile Devices : a Statistical Opportunity or a Privacy Nightmare?

Sponsored Search, Market Equilibria, and the Hungarian Method