Search ACM DL

Search Issue

enter search term and/or author name

**Assignment problem in content distribution networks**: Unsplittable hard-capacitated facility location

Mohammadhossein Bateni, Mohammadtaghi Hajiaghayi

Article No.: 20

DOI: 10.1145/2229163.2229164

In a *Content Distribution Network (CDN)*, there are *m* servers storing the data; each of them has a specific bandwidth. All the requests from a particular client should be assigned to one server because of the routing protocol used....

**Expansion properties of (secure) wireless networks**

Alessandro Panconesi, Jaikumar Radhakrishnan

Article No.: 21

DOI: 10.1145/2229163.2229165

We show that some topologies arising naturally in the context of wireless networking are low-degree, expander graphs.

...
**I/O-efficient shortest path algorithms for undirected graphs with random or bounded edge lengths**

Ulrich Meyer, Norbert Zeh

Article No.: 22

DOI: 10.1145/2229163.2229166

We present I/O-efficient single-source shortest path algorithms for undirected graphs. Our main result is an algorithm with I/O complexity O(&sqrt;(*nm*log *L*)/*B*+MST(*n, m*)) on graphs with *n* vertices, *m* edges,...

**Improved algorithms for orienteering and related problems**

Chandra Chekuri, Nitish Korula, Martin Pál

Article No.: 23

DOI: 10.1145/2229163.2229167

In this article, we consider the orienteering problem in undirected and directed graphs and obtain improved approximation algorithms. The point to point-orienteering problem is the following: Given an edge-weighted graph *G*=(*V, E*)...

**Santa claus meets hypergraph matchings**

Arash Asadpour, Uriel Feige, Amin Saberi

Article No.: 24

DOI: 10.1145/2229163.2229168

We consider the restricted assignment version of the problem of max-min fair allocation of indivisible goods, also known as *the Santa Claus problem*. There are *m* items and *n* players. Every item has some nonnegative value, and...

**The speed of convergence in congestion games under best-response dynamics**

Angelo Fanelli, Michele Flammini, Luca Moscardelli

Article No.: 25

DOI: 10.1145/2229163.2229169

We investigate the speed of convergence of best response dynamics to approximately optimal solutions in congestion games with linear delay functions. In Ackermann et al. [2008] it has been shown that the convergence time of such dynamics to Nash...

**Polynomial-time algorithms for minimum energy scheduling**

Philippe Baptiste, Marek Chrobak, Christoph Dürr

Article No.: 26

DOI: 10.1145/2229163.2229170

The aim of power management policies is to reduce the amount of energy consumed by computer systems while maintaining a satisfactory level of performance. One common method for saving energy is to simply suspend the system during idle times. No...

**Tight approximation algorithms for scheduling with fixed jobs and nonavailability**

Florian Diedrich, Klaus Jansen, Lars Prädel, Ulrich M. Schwarz, Ola Svensson

Article No.: 27

DOI: 10.1145/2229163.2229171

We study two closely related problems in nonpreemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or nonavailability intervals during which the machines are not available; in both cases,...

**Scalably scheduling processes with arbitrary speedup curves**

Jeff Edmonds, Kirk Pruhs

Article No.: 28

DOI: 10.1145/2229163.2229172

We give a scalable ((1+ε)-speed *O*(1)-competitive) nonclairvoyant algorithm for scheduling jobs with sublinear nondecreasing speedup curves on multiple processors with the objective of average response time.

**Entropy, triangulation, and point location in planar subdivisions**

Sébastien Collette, Vida Dujmović, John Iacono, Stefan Langerman, Pat Morin

Article No.: 29

DOI: 10.1145/2229163.2229173

A data structure is presented for point location in connected planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a constant factor of optimal. More specifically,...

**Smoothed analysis of left-to-right maxima with applications**

Valentina Damerow, Bodo Manthey, Friedhelm Meyer Auf Der Heide, Harald Räcke, Christian Scheideler, Christian Sohler, Till Tantau

Article No.: 30

DOI: 10.1145/2229163.2229174

A left-to-right maximum in a sequence of *n* numbers *s*_{1}, …, *s _{n}* is a number that is strictly larger than all preceding numbers. In this article we present a smoothed analysis of the number of...

**Counting occurrences for a finite set of words**: Combinatorial methods

Frédérique Bassino, Julien Clément, Pierre Nicodème

Article No.: 31

DOI: 10.1145/2229163.2229175

In this article, we provide the multivariate generating function counting texts according to their length and to the number of occurrences of words from a finite set. The application of the inclusion-exclusion principle to word counting due to...

**Testing nilpotence of galois groups in polynomial time**

V. Arvind, Piyush P. Kurur

Article No.: 32

DOI: 10.1145/2229163.2229176

We give the first polynomial-time algorithm for checking whether the Galois group Gal(*f*) of an input polynomial *f*(*X*) ∈ Q[*X*] is nilpotent: the running time of our algorithm is bounded by a polynomial in the size of...