Inge Li Goertz
Substring Range Reporting.
Fri, 08/19/2011 - 15:01 — SomNambulAuthors: Philip Bille, Inge Li Goertz
Subjects: Data Structures and Algorithms
AbstractWe revisit various string indexing problems with range reporting features,
namely, position-restricted substring searching, indexing substrings with gaps,
and indexing substrings with intervals. We obtain the following main results.
{itemize} We give efficient reductions for each of the above problems to a new
problem, which we call \emph{substring range reporting}. Hence, we unify the
previous work by showing that we may restrict our attention to a single problem
rather than studying each of the above problems individually.Locating Depots for Capacitated Vehicle Routing.
Tue, 03/08/2011 - 16:01 — SomNambulAuthors: Viswanath Nagarajan, Inge Li Goertz
Subjects: Data Structures and Algorithms
AbstractWe study a location-routing problem in the context of capacitated vehicle
routing. The input is a set of demand locations in a metric space and a fleet
of k vehicles each of capacity Q. The objective is to locate k depots, one for
each vehicle, and compute routes for the vehicles so that all demands are
satisfied and the total cost is minimized. Our main result is a constant-factor
approximation algorithm for this problem. To achieve this result, we reduce to
the k-median-forest problem, which generalizes both k-median and minimum
spanning tree, and which might be of independent interest.- Read more
- 3 comments
- login or register to post comments
User login
