United States Department of Transportation
i
Redesigning Mass Transit Systems to Better Integrate With Mobility-on-Demand Systems or Redesigning Mass Transit Systems to Better Integrate With Mobility-on-Demand Systems via the Batched Set Cover Problem
-
2018-10-05
[PDF-530.15 KB]
Details:
-
Alternative Title:The Batched Set Cover Problem
-
Creators:
-
Corporate Creators:
-
Corporate Contributors:
-
Subject/TRT Terms:
-
Resource Type:
-
Geographical Coverage:
-
Edition:Final Report,11/30/2016 – 8/31/2018
-
Corporate Publisher:
-
Abstract:The authors introduce the batched set cover problem, which is a generalization of the online set cover problem. In this problem, the elements of the ground set that need to be covered arrive in batches. the authors' main technical contribution is a tight Ω(H sub m−2 supra z+1) lower bound on the competitive ratio of any algorithm given an adversary that is required to produce batches of Vapnik Chervonenkis (VC)-dimension at least z, for some z ∈ N°. This restriction on the adversary is motivated by the fact that, in some real world applications, decisions are made after collecting batches of datßßa of high VC-dimension. In particular, ridesharing systems rely on the batch assignment of trip requests to vehicles, and some related problems such as that of optimal congregation points for passenger pickups and dropoffs can be modeled as a batched set cover problem with VC-dimension typically greater than one. The authors note that while any online algorithm may be used to solve the batched set cover problem by artificially sequencing the elements in a batch, this procedure may neglect the rich information encoded in the complex interactions between the elements of a batch and the sets that contain them. Therefore, the authors propose a minor modification to an online algorithm found in [Ref. 8 - Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primaldual approach. Foundations and Trends in Theoretical Computer Science 3(2-3), 93–263 (2009). https://doi.org/10.1561/0400000024 ] to obtain an algorithm that attempts to exploit such information. Unfortunately, the authors are unable to improve its analysis in a way that reflects this intuition. However, the authors present computational experiments that provide empirical evidence of a constant factor improvement in the competitive ratio. To the best of their knowledge, the authors are the first to use the VC-dimension in the context of online (batched) covering problems.
-
Format:
-
Funding:
-
Collection(s):
-
Main Document Checksum:
-
Download URL:
-
File Type:
