enter search term and/or author name
A logarithmic approximation for unsplittable flow on line graphs
Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour
Article No.: 1
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...
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...
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
Article No.: 4
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...