Chrobak, Marek Kenyon, Claire Noga, John Young, Neal E.
Published in
Algorithmica

In the k-median problem we are given sets of facilities and customers, and distances between them. For a given set F of facilities, the cost of serving a customer u is the minimum distance between u and a facility in F. The goal is to find a set F of k facilities that minimizes the sum, over all customers, of their service costs. Following the work...

Mnich, Matthias Schlotter, Ildikó
Published in
Algorithmica

Stable matching problems with lower quotas are fundamental in academic hiring and ensuring operability of rural hospitals. Only few tractable (polynomial-time solvable) cases of stable matching with lower quotas have been identified; most such problems are \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts}...

Boissonnat, Jean-Daniel Maria, Clément
Published in
Algorithmica

This paper introduces a new data structure, called simplex tree, to represent abstract simplicial complexes of any dimension. All faces of the simplicial complex are explicitly stored in a trie whose nodes are in bijection with the faces of the complex. This data structure allows to efficiently implement a large range of basic operations on simplic...

Aziz, Haris Biró, Péter Gaspers, Serge de Haan, Ronald Mattei, Nicholas Rastegari, Baharak
Published in
Algorithmica

We consider the two-sided stable matching setting in which there may be uncertainty about the agents’ preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model—for each agent, there is a probability distribution over linear preferences, (2) compact indifference model—for each agent, a weak p...

Heuberger, Clemens Krenn, Daniel
Published in
Algorithmica

In this article, q -regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor. Each of these terms corresponds to an eigenvalue of the sum of matrices of a l...

Bonnet, Édouard Rzążewski, Paweł
Published in
Algorithmica

Planar graphs are known to allow subexponential algorithms running in time 2O(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{O(\sqrt{n})}$$\end{document} or 2O(nl...

Berg, Mark de Bodlaender, Hans L. Kisfaludi-Bak, Sándor
Published in
Algorithmica

Let P be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let s∈P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s\in P$$\e...

Garnero, Valentin Paul, Christophe Sau, Ignasi Thilikos, Dimitrios M.
Published in
Algorithmica

During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the existence of linear kernels on sparse graphs for problems satisfying some generic conditions. The drawback of such general results is that it is usually not clear how to derive fr...

Kones, Ishai Levin, Asaf
Published in
Algorithmica

We consider a general load balancing problem on parallel machines. Our machine environment in particular generalizes the standard models of identical machines, and the model of uniformly related machines, as well as machines with a constant number of types, and machines with activation costs. The objective functions that we consider contain in part...

Künnemann, Marvin Moeller, Daniel Paturi, Ramamohan Schneider, Stefan
Published in
Algorithmica

We consider the stable matching problem when the preference lists are not given explicitly but are represented in a succinct way and ask whether the problem becomes computationally easier and investigate other implications. We give subquadratic algorithms for finding a stable matching in special cases of natural succinct representations of the prob...