Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 9 Issue 1, December 2012

Approximating minimum-cost connectivity problems via uncrossable bifamilies
Zeev Nutov
Article No.: 1
DOI: 10.1145/2390176.2390177

We give approximation algorithms for the Survivable Network problem. The input consists of a graph G = (V,E) with edge/node-costs, a node subset SV, and connectivity requirements {r(s,t):s,t...

Prize-collecting steiner network problems
Mohammadtaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Zeev Nutov
Article No.: 2
DOI: 10.1145/2390176.2390178

In the Steiner Network problem, we are given a graph G with edge-costs and connectivity requirements ruv between node pairs u,v. The goal is to find a minimum-cost subgraph H of G that contains...

Distributed algorithms for multicommodity flow problems via approximate steepest descent framework
Baruch Awerbuch, Rohit Khandekar, Satish Rao
Article No.: 3
DOI: 10.1145/2390176.2390179

We consider solutions for distributed multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We show first distributed solutions that allow (1 + ε) approximation and whose...

A compact routing scheme and approximate distance oracle for power-law graphs
Wei Chen, Christian Sommer, Shang-Hua Teng, Yajun Wang
Article No.: 4
DOI: 10.1145/2390176.2390180

Compact routing addresses the tradeoff between table sizes and stretch, which is the worst-case ratio between the length of the path a packet is routed through by the scheme and the length of an actual shortest path from source to destination. We...

Online scheduling of packets with agreeable deadlines
Łukasz Jeż, Fei Li, Jay Sethuraman, Clifford Stein
Article No.: 5
DOI: 10.1145/2390176.2390181

This article concerns an online packet scheduling problem that arises as a natural model for buffer management at a network router. Packets arrive at a router at integer time steps, and are buffered upon arrival. Packets have non-negative weights...

Algorithms and complexity for periodic real-time scheduling
Vincenzo Bonifaci, Ho-Leung Chan, Alberto Marchetti-Spaccamela, Nicole Megow
Article No.: 6
DOI: 10.1145/2390176.2390182

We investigate the preemptive scheduling of periodic tasks with hard deadlines. We show that, even in the uniprocessor case, no pseudopolynomial-time algorithm can test the feasibility of a task system within a constant speedup bound, unless P =...

Wireless scheduling with power control
Magnús M. Halldórsson
Article No.: 7
DOI: 10.1145/2390176.2390183

We consider the scheduling of arbitrary wireless links in the physical model of interference to minimize the time for satisfying all requests. We study here the combined problem of scheduling and power control, where we seek both an assignment of...

Combinatiorial algorithms for wireless information flow
Javad B. Ebrahimi, Christina Fragouli
Article No.: 8
DOI: 10.1145/2390176.2390184

A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently...

On the set multicover problem in geometric settings
Chandra Chekuri, Kenneth L. Clarkson, Sariel Har-Peled
Article No.: 9
DOI: 10.1145/2390176.2390185

We consider the set multicover problem in geometric settings. Given a set of points P and a collection of geometric shapes (or sets) F, we wish to find a minimum cardinality subset of F such that each point p ∈ P is covered by...

Approximating parameterized convex optimization problems
Joachim Giesen, Martin Jaggi, Sören Laue
Article No.: 10
DOI: 10.1145/2390176.2390186

We consider parameterized convex optimization problems over the unit simplex, that depend on one parameter. We provide a simple and efficient scheme for maintaining an ε-approximate solution (and a corresponding ε-coreset) along the...

Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
Geevarghese Philip, Venkatesh Raman, Somnath Sikdar
Article No.: 11
DOI: 10.1145/2390176.2390187

We show that for every fixed ji ≥ 1, the k-Dominating Set problem restricted to graphs that do not have Kij (the complete bipartite graph on (i + j) vertices,...

On exact algorithms for treewidth
Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thilikos
Article No.: 12
DOI: 10.1145/2390176.2390188

We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential-time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic...

Cycle detection and correction
Amihood Amir, Estrella Eisenberg, Avivit Levy, Ely Porat, Natalie Shapira
Article No.: 13
DOI: 10.1145/2390176.2390189

Assume that a natural cyclic phenomenon has been measured, but the data is corrupted by errors. The type of corruption is application-dependent and may be caused by measurements errors, or natural features of the phenomenon. We assume that an...