w/in this Title
Journal of the ACM
1-10 of 406 reviews
Near optimal online algorithms and fast approximation algorithms for resource allocation problems
Devanur N., Jain K., Sivan B., Wilkens C. Journal of the ACM 66(1): 1-41, 2019. Type: Article
The resource allocation problem is an age-old problem with a rich history. This paper revisits the resource allocation problem, albeit in a different setting, finding “a middle ground between worst-case and stochastic [analyses]”: the ...
Sep 21 2021
Exact algorithms via monotone local search
Fomin F., Gaspers S., Lokshtanov D., Saurabh S. Journal of the ACM 66(2): 1-23, 2019. Type: Article
Many important problems are NP-complete; this means that, unless P = NP, we cannot have a polynomial-time (feasible) algorithm for solving all instances of this problem. For each such problem, there is an exhaustive search algorithm that requires ...
Apr 26 2021
Computing the geometric intersection number of curves
Despré V., Lazarus F. Journal of the ACM 66(6): 1-49, 2019. Type: Article
More than a century ago, Poincaré asked for a procedure to determine if a closed curve γ on a compact surface
could be contracted to a point, and suggested a computationally expensive method. Dehn proposed a simpler ...
Jan 1 2021
Nonhomogeneous place-dependent Markov chains, unsynchronised AIMD, and optimisation
Wirth F., Stüdli S., Yu J., Corless M., Shorten R. Journal of the ACM 66(4): 1-37, 2019. Type: Article
The transmission control protocol (TCP) that underpins most Internet traffic has a simple yet intuitively beautiful algorithm for congestion control. Every connection will gradually ramp up the bandwidth it uses until congestion occurs, at which p...
Oct 19 2020
The salesman’s improved paths through forests
A., Zuylen A. Journal of the ACM 66(4): 1-16, 2019. Type: Article
Given a set of cities and a function that gives the cost of traveling from one city to another, the traveling salesman problem (TSP) determines a circuit of minimal cost that 1) starts and ends in the same city and 2) passes through each city only...
Sep 19 2019
The PCL theorem: transactions cannot be parallel, consistent, and live
Bushkov V., Dziuma D., Fatourou P., Guerraoui R. Journal of the ACM 66(1): 1-66, 2019. Type: Article
Transactional memory is one approach to making highly parallel programming manageable. In such approaches, parallel memory accesses are treated somewhat similarly to transactions in a database system, ideally guaranteeing properties similar to the...
Apr 15 2019
Computing the homology of basic semialgebraic sets in weak exponential time
Bürgisser P., Cucker F., Lairez P. Journal of the ACM 66(1): 1-30, 2019. Type: Article
A semialgebraic set is a subset of a finite-dimensional Euclidean space defined by a finite list of polynomial equalities and inequalities. These sets can be weird, so it desirable to be able to describe their topological shape, in particular, to ...
Mar 26 2019
Circuit complexity, proof complexity, and polynomial identity testing: the ideal proof system
Grochow J., Pitassi T. Journal of the ACM 65(6): 1-59, 2018. Type: Article
Cook and Reckhow  proved that NP ≠ coNP if and only if in every propositional proof system there is a tautology whose proof size has a super-polynomial lower bound (in terms of the size of the proved formula). Currently, it is not known w...
Feb 13 2019
Plane formation by synchronous mobile robots in the three-dimensional Euclidean space
Yamauchi Y., Uehara T., Kijima S., Yamashita M. Journal of the ACM 64(3): 1-43, 2017. Type: Article
This is an interesting and thorough investigation of the plane formation problem. This problem addresses how a large group of robots moving in 3D Euclidean space--that can see but have no identification, no access to a common coordinate syste...
Feb 16 2018
Improved algorithms for constructing consensus trees
Jansson J., Shen C., Sung W. Journal of the ACM 63(3): 1-24, 2016. Type: Article
A phylogenetic tree is a popular structure used by both biologists and computer scientists to infer evolutionary relationships among various species. In spite of its popularity, different methods, datasets, heuristics and so on used to generate th...
Feb 8 2017
Reproduction in whole or in part without permission is prohibited. Copyright © 2000-2021 ThinkLoud, Inc.