Search ACM DL

Search Issue

enter search term and/or author name

**Intrinsic Robustness of the Price of Anarchy**

Tim Roughgarden

Article No.: 32

DOI: 10.1145/2806883

The price of anarchy, defined as the ratio of the worst-case objective function value of a Nash equilibrium of a game and that of an optimal outcome, quantifies the inefficiency of selfish behavior. Remarkably good bounds on this measure are known...

**LSH-Preserving Functions and Their Applications**

Flavio Chierichetti, Ravi Kumar

Article No.: 33

DOI: 10.1145/2816813

Locality sensitive hashing (LSH) is a key algorithmic tool that is widely used both in theory and practice. An important goal in the study of LSH is to understand which similarity functions admit an LSH, that is, are LSHable. In this article, we...

**Improving Christofides' Algorithm for the s-t Path TSP**

Hyung-Chan An, Robert Kleinberg, David B. Shmoys

Article No.: 34

DOI: 10.1145/2818310

We present a deterministic (1+√5/2)-approximation algorithm for the *s*-*t* path TSP for an arbitrary metric. Given a symmetric metric cost on *n* vertices including two prespecified endpoints, the problem is to find a...

**Optimal Euclidean Spanners**: Really Short, Thin, and Lanky

Michael Elkin, Shay Solomon

Article No.: 35

DOI: 10.1145/2819008

The degree, the (hop-)diameter, and the weight are the most basic and well-studied parameters of geometric spanners. In a seminal STOC'95 paper, titled “Euclidean spanners: short, thin and lanky”, Arya et al. [1995] devised a...

**Sharp Bounds on Davenport-Schinzel Sequences of Every Order**

Seth Pettie

Article No.: 36

DOI: 10.1145/2794075

One of the longest-standing open problems in computational geometry is bounding the complexity of the lower envelope of *n* univariate functions, each pair of which crosses at most *s* times, for some fixed *s*. This problem is...

**The Topology of Wireless Communication**

Erez Kantor, Zvi Lotker, Merav Parter, David Peleg

Article No.: 37

DOI: 10.1145/2807693

This article studies the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other...

**Improved Distributed Approximate Matching**

Zvi Lotker, Boaz Patt-Shamir, Seth Pettie

Article No.: 38

DOI: 10.1145/2786753

We present distributed network algorithms to compute weighted and unweighted matchings with improved approximation ratios and running times. The computational model is a network of processors exchanging *O*(log *n*)-bit messages (the...

**Regular Languages Are Church-Rosser Congruential**

Volker Diekert, Manfred Kufleitner, Klaus Reinhardt, Tobias Walter

Article No.: 39

DOI: 10.1145/2808227

This article shows a general result about finite monoids and weight reducing string rewriting systems. As a consequence it proves a long standing conjecture in formal language theory: All regular languages are Church-Rosser congruential. The class...

**A Polylogarithmic-Competitive Algorithm for the k-Server Problem**

Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph (Seffi) Naor

Article No.: 40

DOI: 10.1145/2783434

We give the first polylogarithmic-competitive randomized online algorithm for the *k*-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of Õ(log^{3} *n*...

**Invited Articles Foreword**

Victor Vianu

Article No.: 41

DOI: 10.1145/2831493

**Subexponential Algorithms for Unique Games and Related Problems**

Sanjeev Arora, Boaz Barak, David Steurer

Article No.: 42

DOI: 10.1145/2775105

Subexponential time approximation algorithms are presented for the U*c*, the following two...

**Query-Based Data Pricing**

Paraschos Koutris, Prasang Upadhyaya, Magdalena Balazinska, Bill Howe, Dan Suciu

Article No.: 43

DOI: 10.1145/2770870

Data is increasingly being bought and sold online, and Web-based marketplace services have emerged to facilitate these activities. However, current mechanisms for pricing data are very simple: buyers can choose only from a set of explicit views,...