Search
w/in this Title
for Titles
All Reviews
Journal of the ACM
ACM Press
Options:
Date Reviewed
Title
Author
Publisher
Published Date
Descending Order
Ascending Order
1-10 of 407 reviews
Date Reviewed
Minimizing convex functions with rational minimizers
Jiang H. Journal of the ACM 70(1): 1-27, 2022. Type: Article
For minimizing a general convex function with access to a separation oracle, it is generally impossible to design a strongly polynomial-time algorithm. However, the situation improves when the convex function has an integer minimizer. This paper a...
Jun 30 2023
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 [analys...
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 th...
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
S
could be contracted to a point, and suggested a computationally expensive method. Dehn...
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...
Oct 19 2020
The salesman’s improved paths through forests
Sebő 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 ea...
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 si...
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 par...
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 [1] 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, i...
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 ...
Feb 16 2018
Display
5
10
15
25
50
100
per column
Reproduction in whole or in part without permission is prohibited. Copyright 1999-2024 ThinkLoud
®
Terms of Use
|
Privacy Policy