ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 8 Issue 3, July 2012

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;(nmlog 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 s1, …, sn 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...