w/in this Title
ACM Transactions on Algorithms
1-10 of 33 reviews
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
-adic assignment problem.” Fix a number
=2), and suppose we are given, for some number
, a 2
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. . 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
Reproduction in whole or in part without permission is prohibited. Copyright © 2000-2022 ThinkLoud, Inc.