Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 64 Issue 1, March 2017

Section: Computational Geometry

A Temporal Logic Approach to Binding-Time Analysis
Rowan Davies
Article No.: 1
DOI: 10.1145/3011069

This article demonstrates that there is a fundamental relationship between temporal logic and languages that involve multiple stages, such as those used to analyze binding times in the context of partial evaluation. This relationship is based on...

Section: Computational Geometry

Upward Max-Min Fairness
Emilie Danna, Avinatan Hassidim, Haim Kaplan, Alok Kumar, Yishay Mansour, Danny Raz, Michal Segalov
Article No.: 2
DOI: 10.1145/3011282

Often one would like to allocate shared resources in a fair way. A common and well-studied notion of fairness is Max-Min Fairness, where we first maximize the smallest allocation, and subject to that the second smallest, and so on. We...

Section: Computational Geometry

Instance-Optimal Geometric Algorithms
Peyman Afshani, Jérémy Barbay, Timothy M. Chan
Article No.: 3
DOI: 10.1145/3046673

We prove the existence of an algorithm A for computing 2D or 3D convex hulls that is optimal for every point set in the following sense: for every sequence σ of n points and for every algorithm A′ in a...

Section: Computational Geometry

Coloring 3-Colorable Graphs with Less than n1/5 Colors
Ken-Ichi Kawarabayashi, Mikkel Thorup
Article No.: 4
DOI: 10.1145/3001582

We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. We first present a new combinatorial algorithm using Õ(n4/11) colors. This is the first combinatorial...

Section: Computational Geometry

Amplifiers for the Moran Process
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby
Article No.: 5
DOI: 10.1145/3019609

The Moran process, as studied by Lieberman, Hauert, and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one...

Section: Computational Geometry

Invited Article Foreword
Eva Tardos
Article No.: 6
DOI: 10.1145/3055358

Section: Computational Geometry

Property-Directed Inference of Universal Invariants or Proving Their Absence
Aleksandr Karbyshev, Nikolaj Bjørner, Shachar Itzhaky, Noam Rinetzky, Sharon Shoham
Article No.: 7
DOI: 10.1145/3022187

We present Universal Property Directed Reachability (PDR), a property-directed semi-algorithm for automatic inference of invariants in a universal fragment of first-order logic. PDR is an extension of...