Search Results

Documents authored by Yuen, David

Found 2 Possible Name Variants:

Yuen, David

Document
Short Paper
DOI: 10.4230/OASIcs.ATMOS.2024.8
New Bounds on the Performance of SBP for the Dial-a-Ride Problem with Revenues (Short Paper)

Authors: Barbara M. Anthony, Christine Chung, Ananya Das, and David Yuen

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract
We revisit the Segmented Best Path (sbp) algorithm for online DARP in an offline setting with revenues and a time limit. The goal is to find a subset of the inputted ride requests that can be served within the time limit while maximizing the total revenue earned. sbp divides the time into segments and greedily chooses the highest-revenue path of requests to serve within each time segment. We show that sbp’s performance has an upper bound of 5. Further, while sbp is a tight 4-approximation in the uniform-revenue case, we find that with non-uniform revenues, the approximation ratio of sbp has a lower bound strictly greater than 4; in particular, we provide a lower bound of (√e + 1)/(√e - 1) ≈ 4.08299, which we show can be generalized to instances with ratio greater than 4.278.
Cite as

Barbara M. Anthony, Christine Chung, Ananya Das, and David Yuen. New Bounds on the Performance of SBP for the Dial-a-Ride Problem with Revenues (Short Paper). In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 8:1-8:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{anthony_et_al:OASIcs.ATMOS.2024.8,
  author =	{Anthony, Barbara M. and Chung, Christine and Das, Ananya and Yuen, David},
  title =	{{New Bounds on the Performance of SBP for the Dial-a-Ride Problem with Revenues}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{8:1--8:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.8},
  URN =		{urn:nbn:de:0030-drops-211964},
  doi =		{10.4230/OASIcs.ATMOS.2024.8},
  annote =	{Keywords: Dial-a-Ride problems, Lower bounds, Vehicle routing}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.11
Maximizing the Number of Rides Served for Dial-a-Ride

Authors: Barbara M. Anthony, Ricky Birnbaum, Sara Boyd, Ananya Christman, Christine Chung, Patrick Davis, Jigar Dhimar, and David Yuen

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
We study a variation of offline Dial-a-Ride, where each request has not only a source and destination, but also a revenue that is earned for serving the request. We investigate this problem for the uniform metric space with uniform revenues. While we present a study on a simplified setting of the problem that has limited practical applications, this work provides the theoretical foundation for analyzing the more general forms of the problem. Since revenues are uniform the problem is equivalent to maximizing the number of served requests. We show that the problem is NP-hard and present a 2/3 approximation algorithm. We also show that a natural generalization of this algorithm has an approximation ratio at most 7/9.
Cite as

Barbara M. Anthony, Sara Boyd, Ricky Birnbaum, Ananya Christman, Christine Chung, Patrick Davis, Jigar Dhimar, and David Yuen. Maximizing the Number of Rides Served for Dial-a-Ride. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{anthony_et_al:OASIcs.ATMOS.2019.11,
  author =	{Anthony, Barbara M. and Birnbaum, Ricky and Boyd, Sara and Christman, Ananya and Chung, Christine and Davis, Patrick and Dhimar, Jigar and Yuen, David},
  title =	{{Maximizing the Number of Rides Served for Dial-a-Ride}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{11:1--11:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.11},
  URN =		{urn:nbn:de:0030-drops-114237},
  doi =		{10.4230/OASIcs.ATMOS.2019.11},
  annote =	{Keywords: dial-a-ride, revenue maximization, approximation algorithm, vehicle routing}
}

Yuen, David C. K.

Document
DOI: 10.4230/DagSemProc.06461.18
Optimal Bidding Strategies for Simultaneous Vickrey Auctions with Perfect Substitutes

Authors: Enrico H. Gerding, Rajdeep K. Dash, David C. K. Yuen, and Nicholas R. Jennings

Published in: Dagstuhl Seminar Proceedings, Volume 6461, Negotiation and Market Engineering (2007)

Abstract
We derive optimal bidding strategies for a global bidder who participates in multiple, simultaneous second-price auctions with perfect substitutes. We prove that, if everyone else bids locally in a single auction, the global bidder should always place non-zero bids in all available auctions, provided there are no budget constraints. With a budget, however, the optimal strategy is to bid locally if this budget is equal or less than the valuation. Furthermore, for a wide range of valuation distributions, we prove that the problem of finding the optimal bids reduces to two dimensions if all auctions are identical. Moreoever, we address markets with both sequential and simultaneous auctions, non-identical auctions, and the allocative efficiency of the market. Finally, by combining analystical and simulation results, we analyse equilibrium strategies in case of several global bidders. However, a stable solution is then only found if there are local bidders as well.
Cite as

Enrico H. Gerding, Rajdeep K. Dash, David C. K. Yuen, and Nicholas R. Jennings. Optimal Bidding Strategies for Simultaneous Vickrey Auctions with Perfect Substitutes. In Negotiation and Market Engineering. Dagstuhl Seminar Proceedings, Volume 6461, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{gerding_et_al:DagSemProc.06461.18,
  author =	{Gerding, Enrico H. and Dash, Rajdeep K. and Yuen, David C. K. and Jennings, Nicholas R.},
  title =	{{Optimal Bidding Strategies for Simultaneous Vickrey Auctions with Perfect Substitutes}},
  booktitle =	{Negotiation and Market Engineering},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6461},
  editor =	{Nick Jennings and Gregory Kersten and Axel Ockenfels and Christof Weinhardt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06461.18},
  URN =		{urn:nbn:de:0030-drops-9934},
  doi =		{10.4230/DagSemProc.06461.18},
  annote =	{Keywords: Bidding strategies, Vickrey Auctions, Perfect Substitutes, Simultaneous Auctions, Budget Constraint, Global Bidder}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact