Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 10 Issue 1, January 2014

A logarithmic approximation for unsplittable flow on line graphs
Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour
Article No.: 1
DOI: 10.1145/2532645

We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time si, an end time ti, a demand di > 0, and a...

Weighted popular matchings
Juliań Mestre
Article No.: 2
DOI: 10.1145/2556951

We study the problem of assigning jobs to applicants. Each applicant has a weight and provides a preference list, which may contain ties, ranking a subset of the jobs. An applicant x may prefer one matching to another (or be...

The fréchet distance revisited and extended
Sariel Har-Peled, Benjamin Raichel
Article No.: 3
DOI: 10.1145/2532646

Given two simplicial complexes in Rd and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the weak Fréchet distance between these curves is minimized. As a...

Geometric optimization and sums of algebraic functions
Antoine Vigneron
Article No.: 4
DOI: 10.1145/2532647

We present a new optimization technique that yields the first FPTAS for several geometric problems. These problems reduce to optimizing a sum of nonnegative, constant description complexity algebraic functions. We first give an FPTAS for...