Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Browse by topic Browse by titles Authors Reviewers Browse by issue Browse Help
ACM Transactions on Algorithms
ACM Press
  1-10 of 33 reviews Date Reviewed 
  Recognizing weak embeddings of graphs
Akitaya H., Fulek R., Tóth C.  ACM Transactions on Algorithms 15(4): 1-27, 2019. Type: Article

The paper begins:...

Mar 12 2021
  Maximizing polynomials subject to assignment constraints
Makarychev K., Sviridenko M.  ACM Transactions on Algorithms 13(4): 1-15, 2017. Type: Article

This paper considers “the q-adic assignment problem.” Fix a number q (originally q=2), and suppose we are given, for some number n, a 2q-dim...

Jul 13 2018
  Toward optimal self-adjusting heaps
Elmasry A.  ACM Transactions on Algorithms 13(4): 1-14, 2017. Type: Article

A self-adjusting heap is a heap data structure “that does not [need to] explicitly maintain structural information”; instead, during each access or update operation, the heap is adjusted in a uniform way. Why is a self-adjusting heap, ...

Mar 19 2018
  Computing the distance between piecewise-linear bivariate functions
Moroz G., Aronov B.  ACM Transactions on Algorithms 12(1): 1-13, 2016. Type: Article

To map a terrain, we measure elevations at different spatial locations and then interpolate the resulting values. Usually, the measurement locations are used to triangulate the area. Then, on each of the resulting triangles, we perform linear inte...

Mar 4 2016
  Sorting and selection with imprecise comparisons
Ajtai M., Feldman V., Hassidim A., Nelson J.  ACM Transactions on Algorithms 12(2): 1-19, 2015. Type: Article

Sorting and selection with imprecise comparisons has long been the focus of extensive research attention among theoreticians. There have been a number of models and frameworks of imprecision considered in the literature. In this paper, the authors...

Feb 1 2016
  An almost optimal unrestricted fast Johnson-Lindenstrauss transform
Ailon N., Liberty E.  ACM Transactions on Algorithms 9(3): 1-12, 2013. Type: Article

This paper deals with the randomized construction of efficiently computable Johnson-Lindenstrauss transforms. The paper greatly improves previous results in the literature by establishing an almost optimal result in terms of the dimension reduced ...

Oct 15 2013
  Approximation algorithms for a minimization variant of the order-preserving submatrices and for biclustering problems
Hochbaum D., Levin A.  ACM Transactions on Algorithms 9(2): 1-12, 2013. Type: Article

This well-written paper proposes two approximation algorithms for the MinOPSM problem, which is the complement of the order-preserving submatrix (OPSM) problem by Ben-Dor et al. [1]. The authors provide a 5-approximation algorithm for MinOPSM , an...

Jun 17 2013
  An FPTAS for the minimum total weighted tardiness problem with a fixed number of distinct due dates
Karakostas G., Kolliopoulos S., Wang J.  ACM Transactions on Algorithms 8(4): 1-16, 2012. Type: Article

Imagine a single machine and several jobs to be completed sequentially on it, each job having a characteristic weight, processing time, and a prescribed due date of completion. Then, the tardiness of a job is defined as the time taken beyond its d...

Dec 4 2012
  On the query complexity of testing orientations for being Eulerian
Fischer E., Lachish O., Matsliah A., Newman I., Yahalom O.  ACM Transactions on Algorithms 8(2): 1-41, 2012. Type: Article

Since Leonhard Euler created graph theory, in 1736, while studying the seven bridges problem in Königsberg, testing graphs for being Eulerian has been an old and challenging problem. Graphs can be either undirected (the edges have no orientat...

Jun 15 2012
  An improved approximation algorithm for resource allocation
Calinescu G., Chakrabarti A., Karloff H., Rabani Y.  ACM Transactions on Algorithms 7(4): 1-7, 2011. Type: Article

The resource allocation problem finds the most profitable subset of tasks for a given limited resource. It is also known as the bandwidth allocation problem, resource constrained scheduling, or call admission control, and is nondeterministic polyn...

Jan 18 2012
Display per column
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2022 ThinkLoud, Inc.
Terms of Use
| Privacy Policy