Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 62 Issue 5, November 2015

Section: Algorithmic Economics

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

Section: Analysis of Algorithms

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

Section: Approximation Algorithms

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

Section: Computational Geometry

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

Section: Distributed Computing

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

Section: Formal Languages

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

Section: Randomized Algorithms and Probabilistic Analysis

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 Õ(log3 n...

Section: Invited Articles Section

Invited Articles Foreword
Victor Vianu
Article No.: 41
DOI: 10.1145/2831493

Section: Approximation Algorithms

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 Unique Games and Small-Set Expansion problems. Specifically, for some absolute constant c, the following two...

Section: Relational Databases, Database Query Languages, and Economics

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