Search ACM DL

Search Issue

enter search term and/or author name

**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 *S* ⊆ *V*, 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 *r _{uv}* between node pairs

**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 *j* ≥ *i* ≥ 1, the *k*-D*K _{ij}* (the complete bipartite graph on (

**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...