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 31 reviews Date Reviewed 
  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
  The optimality of the online greedy algorithm in carpool and chairman assignment problems
Coppersmith D., Nowicki T., Paleologo G., Tresser C., Wu C.  ACM Transactions on Algorithms 7(3): 1-22, 2011. Type: Article

The chairman assignment problem is stated thus: “Suppose k states form a union and every year a union chairman has to be selected in such a way that at any time the accumulated number of chairmen from each state is proport...

Dec 28 2011
  Improved approximations for the hotlink assignment problem
Laber E., Molinaro M.  ACM Transactions on Algorithms 7(3): 1-34, 2011. Type: Article

Laber and Molinaro study the hotlink assignment problem, in which direct links between pages are added to an existing Web site to minimize the time users spend searching for information. A Web site is represented by a graph G, w...

Dec 5 2011
Display per column
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2018 ThinkLoud, Inc.
Terms of Use
| Privacy Policy