Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Advice Complexity of Priority Algorithms

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 11312))

Included in the following conference series:

Abstract

The priority model of “greedy-like” algorithms was introduced by Borodin, Nielsen, and Rackoff in 2002. We augment this model by allowing priority algorithms to have access to advice, i.e., side information precomputed by an all-powerful oracle. Obtaining lower bounds in the priority model without advice can be challenging and may involve intricate adversary arguments. Since the priority model with advice is even more powerful, obtaining lower bounds presents additional difficulties. We sidestep these difficulties by developing a general framework of reductions which makes lower-bound proofs relatively straightforward and routine. We start by introducing the Pair Matching problem, for which we are able to prove strong lower bounds in the priority model with advice. We develop a template for constructing a reduction from Pair Matching to other problems in the priority model with advice – this part is technically challenging since the reduction needs to define a valid priority function for Pair Matching while respecting the priority function for the other problem. Finally, we apply the template to obtain lower bounds for a number of standard discrete optimization problems.

The full version of the paper is available on arXiv [6]. For the first author, research is supported by NSERC. The second and third authors were supported in part by the Independent Research Fund Denmark, Natural Sciences, grant DFF-7014-00041.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

Notes

  1. 1.

    In the adaptive priority model, the algorithm is allowed to specify a new ordering depending on previous items and decisions before a new input item is presented.

  2. 2.

    In Theorem 3 and in all of our lower bound advice results, we state the result so as to include\(\varepsilon = \frac{1}{2}\), in which case the conditions “fewer than\((1/2-\varepsilon )\)” and “fewer than\((1-H(\varepsilon ))\)” make the statements vacuously true.

  3. 3.

    There are similarities to the NP-Complete problems, Numerical Matching with Target Sums and Numerical 3-Dimensional Matching, though these problems ask if permutations of sets of inputs will lead to a complete matching.

  4. 4.

    However, both gadgets within a pair do not necessarily have the same topological structure. In Triangle Finding, they did not.

References

  1. Alekhnovich, M., Borodin, A., Buresh-Oppenheim, J., Impagliazzo, R., Magen, A., Pitassi, T.: Toward a model for backtracking and dynamic programming. Comput. Complex.20(4), 679–740 (2011)

    Article MathSciNet  Google Scholar 

  2. Angelopoulos, S., Borodin, A.: On the power of priority algorithms for facility location and set cover. Algorithmica40(4), 271–291 (2004)

    Article MathSciNet  Google Scholar 

  3. Besser, B., Poloczek, M.: Greedy matching: guarantees and limitations. Algorithmica77(1), 201–234 (2017)

    Article MathSciNet  Google Scholar 

  4. Böckenhauer, H.-J., Hromkovič, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The string guessing problem as a method to prove lower bounds on the advice complexity. Theor. Comput. Sci.554, 95–108 (2014)

    Article MathSciNet  Google Scholar 

  5. Borodin, A., Boyar, J., Larsen, K.S., Mirmohammadi, N.: Priority algorithms for graph optimization problems. Theor. Comput. Sci.411(1), 239–258 (2010)

    Article MathSciNet  Google Scholar 

  6. Borodin, A., Boyar, J., Larsen, K.S., Pankratov, D.: Advice complexity of priority algorithms. ArXivarXiv:1806.06223 [cs.DS] (2018)

  7. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)

    MATH  Google Scholar 

  8. Borodin, A., Lucier, B.: On the limitations of greedy mechanism design for truthful combinatorial auctions. ACM Trans. Econ. Comput.5(1), 2:1–2:23 (2016)

    Article MathSciNet  Google Scholar 

  9. Borodin, A., Nielsen, M.N., Rackoff, C.: (Incremental) priority algorithms. Algorithmica37(4), 295–326 (2003)

    Article MathSciNet  Google Scholar 

  10. Boyar, J., Favrholdt, L.M., Kudahl, C., Larsen, K.S., Mikkelsen, J.W.: Online algorithms with advice: a survey. ACM Comput. Surv.50(2), 19:1–19:34 (2017)

    Article  Google Scholar 

  11. Boyar, J., Kamali, S., Larsen, K.S., López-Ortiz, A.: Online bin packing with advice. Algorithmica74(1), 507–527 (2016)

    Article MathSciNet  Google Scholar 

  12. Cook, S.A.: The complexity of theorem-proving procedures. In: 3rd Annual ACM Symposium on Theory of Computing (STOC), pp. 151–158. ACM (1971)

    Google Scholar 

  13. Davis, S., Impagliazzo, R.: Models of greedy algorithms for graph problems. Algorithmica54(3), 269–317 (2009)

    Article MathSciNet  Google Scholar 

  14. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103. Springer, Boston (1972).https://doi.org/10.1007/978-1-4684-2001-2_9

    Chapter  Google Scholar 

  15. Komm, D.: An Introduction to Online Computation - Determinism, Randomization, Advice. Texts in Theoretical Computer Science. An EATCS Series. Springer, Cham (2016).https://doi.org/10.1007/978-3-319-42749-2

    Book  Google Scholar 

  16. Lesh, N., Mitzenmacher, M.: Bubblesearch: a simple heuristic for improving priority-based greedy algorithms. Inf. Process. Lett.97(4), 161–169 (2006)

    Article MathSciNet  Google Scholar 

  17. McGregor, A.: Graph stream algorithms: a survey. ACM SIGMOD Rec.43(1), 9–20 (2014)

    Article MathSciNet  Google Scholar 

  18. Poloczek, M.: Bounds on greedy algorithms for MAX SAT. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 37–48. Springer, Heidelberg (2011).https://doi.org/10.1007/978-3-642-23719-5_4

    Chapter MATH  Google Scholar 

  19. Regev, O.: Priority algorithms for makespan minimization in the subset model. Inf. Process. Lett.84(3), 153–157 (2002)

    Article MathSciNet  Google Scholar 

Download references

Acknowledgments

Part of the work was done when the first author was visiting Toyota Technological Institute at Chicago. The work was initiated while the second and third authors were visiting the University of Toronto. Most of the work was done when the fourth author was a postdoc at the University of Toronto.

Author information

Authors and Affiliations

  1. University of Toronto, Toronto, Canada

    Allan Borodin

  2. University of Southern Denmark, Odense, Denmark

    Joan Boyar & Kim S. Larsen

  3. Concordia University, Montreal, Canada

    Denis Pankratov

Authors
  1. Allan Borodin

    You can also search for this author inPubMed Google Scholar

  2. Joan Boyar

    You can also search for this author inPubMed Google Scholar

  3. Kim S. Larsen

    You can also search for this author inPubMed Google Scholar

  4. Denis Pankratov

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toDenis Pankratov.

Editor information

Editors and Affiliations

  1. University of Haifa, Haifa, Israel

    Leah Epstein

  2. University of Leicester, Leicester, UK

    Thomas Erlebach

Rights and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Borodin, A., Boyar, J., Larsen, K.S., Pankratov, D. (2018). Advice Complexity of Priority Algorithms. In: Epstein, L., Erlebach, T. (eds) Approximation and Online Algorithms. WAOA 2018. Lecture Notes in Computer Science(), vol 11312. Springer, Cham. https://doi.org/10.1007/978-3-030-04693-4_5

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp