skip to main content


Search for: All records

Creators/Authors contains: "Arndt, Stephen"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Motivated by demand-responsive parking pricing systems, we consider posted-price algorithms for the online metric matching prob- lem. We give an O(log n)-competitive posted-price randomized algorithm in the case that the metric space is a line. In particular, in this setting we show how to implement the ubiquitous guess-and-double technique using prices. 
    more » « less
  2. We consider the online transportation problem set in a metric space containing parking garages of various capacities. Cars arrive over time, and must be assigned to an unfull parking garage upon their arrival. The objective is to minimize the aggregate distance that cars have to travel to their assigned parking garage. We show that the natural greedy algorithm, augmented with garages of k ≥ 3 times the capacity, is (1 + 2/k-2)-competitive. 
    more » « less