w/in this Title
ACM Transactions on Algorithms
1-10 of 30 reviews
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
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
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
Dec 5 2011
To fill or not to fill: the gas station problem
Khuller S., Malekian A., Mestre J. ACM Transactions on Algorithms 7(3): 1-16, 2011. Type: Article
The traveling salesperson problem (TSP) is a well-known optimization problem; many variations of it are routinely studied. Although sometimes considered to be a theoretical rather than a practical problem, variants of the TSP appear frequently in ...
Oct 10 2011
Reproduction in whole or in part without permission is prohibited. Copyright © 2000-2017 ThinkLoud, Inc.