Concept
Algorithme hongrois
Publications associées (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 Informatik2022Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
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 Informatik2021How 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 Engineers2015Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
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 Machinery2014Population Sensing Using Mobile Devices
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 ...
EPFL2014Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back
We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) runni ...
IEEE2013Sponsored 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 ...
2010Some coloring and walking problems in graphs
Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the following ones: graph coloring and the Hamiltonian circuit ...
EPFL2008