Document Open Access Logo

Packing Cars into Narrow Roads: PTASs for Limited Supply Highway

Authors Fabrizio Grandoni , Andreas Wiese

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.54.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Fabrizio Grandoni
  • IDSIA, USI-SUPSI, Switzerland
Andreas Wiese
  • Department of Industrial Engineering and Center for Mathematical Modeling, Universidad de Chile, Chile

Funding

  • Grandoni, Fabrizio: Partially supported by the SNSF Excellence Grant 200020B_182865/1.
  • Wiese, Andreas: Partially supported by the Fondecyt Regular grant 1170223.

Cite As Get BibTex

Fabrizio Grandoni and Andreas Wiese. Packing Cars into Narrow Roads: PTASs for Limited Supply Highway. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.54

Abstract

In the Highway problem, we are given a path with n edges (the highway), and a set of m drivers, each one characterized by a subpath and a budget. For a given assignment of edge prices (the tolls), the highway owner collects from each driver the total price of the associated path when it does not exceed drivers’s budget, and zero otherwise. The goal is to choose the prices to maximize the total profit. A PTAS is known for this (strongly NP-hard) problem [Grandoni,Rothvoss-SODA'11, SICOMP'16].
In this paper we study the limited supply generalization of Highway, that incorporates capacity constraints. Here the input also includes a capacity u_e >= 0 for each edge e; we need to select, among drivers that can afford the required price, a subset such that the number of drivers that use each edge e is at most u_e (and we get profit only from selected drivers). To the best of our knowledge, the only approximation algorithm known for this problem is a folklore O(log m) approximation based on a reduction to the related Unsplittable Flow on a Path problem (UFP). The main result of this paper is a PTAS for limited supply highway.
As a second contribution, we study a natural generalization of the problem where each driver i demands a different amount d_i of capacity. Using known techniques, it is not hard to derive a QPTAS for this problem. Here we present a PTAS for the case that drivers have uniform budgets. Finding a PTAS for non-uniform-demand limited supply highway is left as a challenging open problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • approximation algorithms
  • pricing problems
  • highway problem
  • unsplittable flow on a path

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese. Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path. In International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 25-36, 2013. Google Scholar
  2. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese. A Mazing 2+ε Approximation for Unsplittable Flow on a Path. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 26-41, 2014. Google Scholar
  3. Maria-Florina Balcan and Avrim Blum. Approximation algorithms and online mechanisms for item pricing. In ACM Conference on Electronic Commerce, pages 29-35, 2006. Google Scholar
  4. N. Bansal, Z. Friggstad, R. Khandekar, and R. Salavatipour. A logarithmic approximation for unsplittable flow on line graphs. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 702-709, 2009. Google Scholar
  5. Nikhil Bansal, Amit Chakrabarti, Amir Epstein, and Baruch Schieber. A quasi-PTAS for unsplittable flow on line graphs. In ACM Symposium on Theory of computing (STOC), pages 721-729, 2006. Google Scholar
  6. Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber. A unified approach to approximating resource allocation and scheduling. Journal of the ACM, 48(5):1069-1090, 2001. Google Scholar
  7. Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, and Andreas Wiese. New Approximation Schemes for Unsplittable Flow on a Path. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 47-58, 2015. Google Scholar
  8. P. Bonsma, J. Schulz, and A. Wiese. A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 47-56, 2011. Google Scholar
  9. Patrick Briest and Piotr Krysta. Single-minded unlimited supply pricing on sparse instances. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1093-1102, 2006. Google Scholar
  10. Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, and Yuval Rabani. Improved Approximation Algorithms for Resource Allocation. In International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 401-414, 2002. Google Scholar
  11. Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, and Amit Kumar. Approximation Algorithms for the Unsplittable Flow Problem. Algorithmica, 47(1):53-78, 2007. Google Scholar
  12. Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan, and Sanjeev Khanna. Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply. In International Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM), pages 73-84, 2012. Google Scholar
  13. Parinya Chalermsook, Bundit Laekhanukit, and Danupon Nanongkai. Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 370-379, 2013. Google Scholar
  14. C. Chekuri, A. Ene, and N. Korula. Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs. In International Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM), pages 42-55, 2009. Google Scholar
  15. Chandra Chekuri, Marcelo Mydlarz, and F. Bruce Shepherd. Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms, 3(3), 2007. Google Scholar
  16. Chandra Chekuri, Marcelo Mydlarz, and F Bruce Shepherd. Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms (TALG), 3(3):27, 2007. Google Scholar
  17. Maurice Cheung and Chaitanya Swamy. Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 35-44, 2008. Google Scholar
  18. Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk, and Piotr Sankowski. A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees. In European Symposium on Algorithms (ESA), pages 349-360, 2012. Google Scholar
  19. Khaled M. Elbassioni, Mahmoud Fouz, and Chaitanya Swamy. Approximation Algorithms for Non-single-minded Profit-Maximization Problems with Limited Supply. In Internet and Network Economics - 6th International Workshop, WINE 2010, Stanford, CA, USA, December 13-17, 2010. Proceedings, pages 462-472, 2010. Google Scholar
  20. Khaled M. Elbassioni, Rajiv Raman, Saurabh Ray, and René Sitters. On Profit-Maximizing Pricing for the Highway and Tollbooth Problems. In International Symposium on Algorithmic Game Theory (SAGT), pages 275-286, 2009. Google Scholar
  21. Khaled M. Elbassioni, René Sitters, and Yan Zhang. A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs. In European Symposium on Algorithms (ESA), pages 451-462, 2007. Google Scholar
  22. Iftah Gamzu and Danny Segev. A Sublogarithmic Approximation for Highway and Tollbooth Pricing. In International Colloquium on Automata, Languages and Programming (ICALP), pages 582-593, 2010. Google Scholar
  23. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2411-2422, 2017. Google Scholar
  24. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes. In ACM Symposium on Theory of Computing (STOC), pages 607-619, 2018. Google Scholar
  25. Fabrizio Grandoni and Thomas Rothvoß. Pricing on Paths: A PTAS for the Highway Problem. SIAM J. Comput., 45(2):216-231, 2016. Google Scholar
  26. Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, and Frank McSherry. On profit-maximizing envy-free pricing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1164-1173, 2005. Google Scholar
  27. Cynthia A. Phillips, R. N. Uma, and Joel Wein. Off-line admission control for general scheduling problems. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 879-888, 2000. Google Scholar
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