w/in this Title
ACM Transactions on Algorithms
1-10 of 26 reviews
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...
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...
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...
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...
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
Shortest paths in directed planar graphs with negative lengths: a linear-space
Klein P., Mozes S., Weimann O. ACM Transactions on Algorithms 6(2): 1-18, 2010. Type: Article
Finding the shortest paths in weighted graphs is an interesting problem in combinatorial optimization. Dijkstra’s classic algorithm is applicable for computing the shortest paths to all nodes from a single source, when there are no negative ...
Mar 18 2011
Clustering for metric and nonmetric distance measures
Ackermann M., Blömer J., Sohler C. ACM Transactions on Algorithms 6(4): 1-26, 2010. Type: Article
-median problem can be simply stated as follows: Given a set of locations and a maximum number of facilities, decide at which locations facilities should be placed, in order to minimize the total cost, computed as the...
Dec 3 2010
Hausdorff distance under translation for points and balls
Agarwal P., Har-Peled S., Sharir M., Wang Y. ACM Transactions on Algorithms 6(4): 1-26, 2010. Type: Article
In the protein docking problem, pairs of molecules modeled as unions of balls are shape-matched by finding close but noncolliding positionings of the molecules. This provides one motivation for this work, which develops algorithms for four...
Nov 18 2010
Fast asynchronous Byzantine agreement and leader election with full information
Kapron B., Kempe D., King V., Saia J., Sanwalani V. ACM Transactions on Algorithms 6(4): 1-28, 2010. Type: Article
This substantial monograph addresses two open problems in the field of distributed computing: the Byzantine agreement problem and the leader election problem. The context is a model that is asynchronous with full information and involves...
Nov 11 2010
Reproduction in whole or in part without permission is prohibited. Copyright © 2000-2013 ThinkLoud, Inc.