Instytut Informatyki
Menu
research

Papers

  • Combinatorial Optimization Group's Publications for 2019

    1. M. Adamczyk, J. Byrka, J. Marcinkowski, S. M. Meesum, M. Włodarczyk, Constant-factor FPT approximation for capacitated k-median, W: 27th Annual European Symposium on Algorithms (ESA 2019) / Michael A. Bender, Ola Svensson, Grzegorz Herman (ed.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 1:1-1:14. - (https://doi.org/10.4230/LIPIcs.ESA.2019.1).
    2. S. A. Amiri, S. Dudycz, M. Parham, S. Schmid, S. Wiederrecht, On polynomial-time congestion-free software-defined network updates, W: 2019 IFIP Networking Conference (IFIP Networking). - Piscataway : IEEE Computer Society, 2019. - s. 199-207. - (https://doi.org/10.23919/IFIPNetworking.2019.8816833).
    3. N. Bansal, M. Eliás, Ł. Jeż, G. Koumoutsos, The (h,k)-server problem on bounded depth trees, W: ACM Transactions on Algorithms. - Vol. 15, iss. 2 (2019), nr art. 28, s. 1-26. - (https://doi.org/10.1145/3301314).
    4. M. Böhm, M. Chrobak, Ł. Jeż, F. Li, J. Sgall, P. Veselý, Online packet scheduling with bounded delay and lookahead, W: Theoretical Computer Science. - Vol. 776 (2019), s. 95-113. - (https://doi.org/10.1016/j.tcs.2019.01.013).
    5. M. Bieńkowski, J. Byrka, M. Chrobak, C. Coester, Ł. Jeż, E. Koutsoupias, Better bounds for online line chasing, W: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) / Peter Rossmanith, Pinar Heggernes, Joost-Pieter Katoen (ed.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 8:1-8:13. - (https://doi.org/10.4230/LIPIcs.MFCS.2019.8).
    6. M. Bieńkowski, J. Byrka, M. Mucha, Dynamic beats fixed : on phase-based algorithms for file migration, W: ACM Transactions on Algorithms. - Vol. 15, iss. 4 (2019), nr art. 46, s. 1-21. - (https://doi.org/10.1145/3340296).
    7. M. Bieńkowski, Ł. Jeż, P. Schmidt, Slaying hydrae: Improved bounds for generalized k-server in uniform metrics, W: 30th International Symposium on Algorithms and Computation (ISAAC 2019) / editors: Pinyan Lu, Guochuan Zhang. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - (LIPIcs ; vol. 149). - s. 14:1-14:14. - (https://doi.org/10.4230/LIPIcs.ISAAC.2019.14).
    8. M. Bieńkowski, H.-H. Liu, An improved online algorithm for the traveling repairperson problem on a line, W: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) / Peter Rossmanith, Pinar Heggernes, Joost-Pieter Katoen (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 6:1-6:12. - (https://doi.org/10.4230/LIPIcs.MFCS.2019.6).
    9. I. R. Cohen, A. Eden, A. Fiat, Ł. Jeż, Dynamic pricing of servers on trees, W: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) / edited by Dimitris Achlioptas, László A. Végh. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 10:1-10:22. - (https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.10).
    10. S. Dudycz, M. Lewandowski, J. Marcinkowski, Tight Approximation Ratio for Minimum Maximal Matching, W: 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings / Andrea Lodi, Viswanath Nagarajan (eds.). - Cham : Springer, 2019. - (Lecture Notes in Computer Science ; vol. 11480). - s. 181-193. - (https://doi.org/10.1007/978-3-030-17953-3_14).
    11. T. Erlebach, F.-H. Liu, H.-H. Liu, M. Shalom, P. W. H. Wong, S. Zaks, Complexity and online algorithms for minimum skyline coloring of intervals, W: Theoretical Computer Science. - Vol. 788 (2019), s. 66-78. - (https://doi.org/10.1016/j.tcs.2019.05.007).
    12. P. Faliszewski, P. Manurangsi, K. Sornat, Approximation and Hardness of Shift-Bribery, W: The Thirty-Third AAAI Conference on Artificial Intelligence, the Thirty-First Innovative Applications of Artificial Intelligence Conference, the Ninth AAAI Symposium on Educational Advances in Artificial Intelligence : Honolulu, Hawaii USA - January 27-February 1, 2019. - Palo Alto : AAAI Press, 2019. - s. 1901-1908. - (http://dx.doi.org/10.1609/aaai.v33i01.33011901).
    13. K.-T. Foerster, M. Pacut, S. Schmid, On the complexity of non-segregated routing in reconfigurable data center architectures, W: ACM SIGCOMM Computer Communication Review. - Vol. 49, iss. 2 (2019), s. 2-8. - (https://doi.org/10.1145/3336937.3336939).
    14. P. Ghosal, M. Nasre, P. Nimbhorkar, Rank-maximal matchings - structure and algorithms, W: Theoretical Computer Science. - Vol. 767 (2019), s. 73-82. - (https://doi.org/10.1016/j.tcs.2018.09.033).
    15. A. Kunysz, A faster algorithm for the strongly stable b-matching problem, W: Algorithms and complexity ; 11th international conference, CIAC 2019, Rome, Italy, May 27-29, 2019 : proceedings / Pinar Heggernes (ed.). - Cham : Springer, 2019. - (LNCS ; vol. 11485). - s. 299-310.
    16. S. M. Meesum, F. Panolan, S. Saurabh, M. Zehavi, Rank vertex cover as a natural problem for algebraic compression, W: SIAM Journal on Discrete Mathematics. - Vol. 33, iss. 3 (2019), s. 1277-1296. - (https://doi.org/10.1137/17M1154370).
    17. P. Veselý, M. Chrobak, Ł. Jeż, J. Sgall, A Φ-Competitive Algorithm for Scheduling Packets with Deadlines, W: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms / Timothy M. Chan (Ed.). - Philadelphia : Society for Industrial and Applied Mathematics (SIAM), 2019. - s. 123-142. - (https://doi.org/10.1137/1.9781611975482.9).

  • Combinatorial Optimization Group's Publications for 2018

    1. A. Adamaszek, M. Mnich, K. Paluch, New approximation algorithms for (1,2)-TSP, W: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) / Editors Ioanis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald T. Sannella. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs ; 107). - S. 9:1-9:14 (https://doi.org/10.4230/LIPIcs.ICALP.2018.9).
    2. S. Amiri, S. Dudycz, S. Schmid, S. Wiederrecht, Congestion-free rerouting of flows on DAGs, W: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) / Editors Ioanis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald T Sannella. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs ; 107). - S. 143:1-143:13 (https://doi.org/10.4230/LIPIcs.ICALP.2018.143).
    3. N. Bansal, M. Eliás, Ł. Jeż, G. Koumoutsos, K. Pruhs, Tight bounds for double coverage against weak adversaries, W: Theory of Computing Systems. - Vol. 62, iss. 2 (2018), s. 349-365 (https://doi.org/10.1007/s00224-016-9703-3).
    4. A. Basta, A. Blenk, S. Dudycz, A. Ludwig, S. Schmid, Efficient loop-free rerouting of multiple SDN flows, W: IEEE-ACM Transactions on Networking. - Vol. 26, iss. 2 (2018), s. 948-961 (https://doi.org/10.1109/TNET.2018.2810640).
    5. M. Bienkowski, M. Böhm, Ł. Jeż, P. Laskoś-Grabowski, J. Marcinkowski, J. Sgall, A. Spyra, P. Veselý, Logarithmic price of buffer downscaling on line metrics, W: Theoretical Computer Science . - Vol. 707 (2018), s. 89-93 : rys. (https://doi.org/10.1016/j.tcs.2017.10.008).
    6. M. Bieńkowski, T. Jurdziński, M. Korzeniowski, D. Kowalski, Distributed online and stochastic queueing on a multiple access channel, W: ACM Transactions on Algorithms. - Vol. 14, nr 2 (2018), s. 21:1-21:22 (https://doi.org/10.1145/3182396).
    7. M. Bieńkowski, A. Kraska, H. Liu, P. Schmidt, A primal-dual online deterministic algorithm for matching with delays, W: Approximation and Online Algorithms : 16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers / Editors Leah Epstein, Thomas Erlebach. - Cham : Springer, 2018. - (LNCS : 11312). - S. 51-68 (https://doi.org/10.1007/978-3-030-04693-4_4).
    8. M. Bieńkowski, A. Kraska, P. Schmidt, A match in time saves nine: deterministic online matching with delays, W: Approximation and Online Algorithms : 15th International Workshop, WAOA 2017, Vienna, Austria, September 7-8, 2017, Revised Selected Papers / Editors: Roberto Solis-Oba, Rudolf Fleischer. - Cham : Springer, 2018. - (Lecture Notes in Computer Science; 10787). - S. 132-146 (https://doi.org/10.1007/978-3-319-89441-6_11).
    9. M. Bieńkowski, A. Kraska, P. Schmidt, Online service with delay on a line, W: Structural Information and Communication Complexity : 25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers / Editors Zvi Lotker, Boaz Patt-Shamir. - Cham : Springer, 2018. - S. 237-248 (https://doi.org/10.1007/978-3-030-01325-7_22).
    10. M. Bieńkowski, N. Sarrar, S. Schmid, S. Uhlig, Online aggregation of the forwarding information base : accounting for locality and churn, W: IEEE/ACM Transactions on Networking. - Vol. 26, Iss.1 (2018), s. 591-604 (https://doi.org/10.1109/TNET.2017.2787419).
    11. J. Byrka, M. Lewandowski, J. Spoerhase, Approximating node-weighted k-MST on planar graphs, W: Approximation and Online Algorithms : 16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers / Editors Leah Epstein, Thomas Erlebach. - Cham : Springer, 2018. - (LNCS : 11312). - S. 87-101 (https://doi.org/10.1007/978-3-030-04693-4_6).
    12. J. Byrka, T. Pensyl, B. Rybicki, J. Spoerhase, A. Srinivasan, K. Trinh, An improved approximation algorithm for knapsack median using sparsification, W: Algorithmica. - Vol. 80, iss. 4 (2018), s. 1093-1114 (https://doi.org/10.1007/s00453-017-0294-4).
    13. J. Byrka, P. Skowron, K. Sornat, Proportional approval voting, harmonic k-median, and negative association, W: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) / editors: Ioanis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald T Sannella. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - S. 26:1-26:14 (https://doi.org/10.4230/LIPIcs.ICALP.2018.26).
    14. J. Byrka, K. Sornat, J. Spoerhase, Constant-factor approximation for ordered k-median, W: STOC'18 : Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing : June 25-29, 2018, Los Angeles, CA, USA / editors: Ilias Diakonikolas, David Kempe, Monika Henzinger. - New York : ACM, 2018. - S. 620-631 (https://doi.org/10.1145/3188745.3188930).
    15. J. Byrka, A. Srinivasan, Approximation algorithms for stochastic and risk-averse optimization, W: SIAM Journal on Discrete Mathematics. - Vol. 32, iss. 1 (2018), s. 44-63 (https://doi.org/10.1137/15M1043790).
    16. M. Böhm, Ł. Jeż, J. Sgall, P. Vesel~''y, On packet scheduling with adversarial jamming and speedup, W: Approximation and Online Algorithms : 15th International Workshop, WAOA 2017, Vienna, Austria, September 7-8, 2017, Revised Selected Papers / Roberto Solis-Oba, Rudolf Fleischer (eds.). - Cham : Springer, 2018. - (LNCS ; vol. 10787). - S. 190-206.
    17. S. Chaplick, M. De, A. Ravsky, J. Spoerhase, Approximation schemes for geometric coverage problems, W: 26th Annual European Symposium on Algorithms (ESA 2018) / Editors: Yossi Azar, Hannah Bast, Grzegorz Herman. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - S. 17:1-17:15 (https://doi.org/10.4230/LIPIcs.ESA.2018.17).
    18. S. Chaplick, M. De, A. Ravsky, J. Spoerhase, Brief announcement : approximation schemes for geometric coverage problems, W: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) / Edotrs: Ioanis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald T Sannella. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - S. 107:1-107:4 (https://doi.org/10.4230/LIPIcs.ICALP.2018.107).
    19. M. Cygan, Ł. Kowalik, A. Socała, K. Sornat, Approximation and parameterized complexity of minimax approval voting, W: Journal of Artificial Intelligence Research. - Vol. 63 (2018), s. 495-513 (https://doi.org/10.1613/jair.1.11253).
    20. S. Dudycz, K. Paluch, Optimal general matchings, W: Graph-Theoretic Concepts in Computer Science : 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018 : proceedings / editors Andreas Brandstädt, Ekkehard Köhler, Klaus Meer. - Cham : Springer, 2018. - (LNCS ; 11159). - S. 176-189 (https://doi.org/10.1007/978-3-030-00256-5_15).
    21. K. Foerster, A. Ludwig, J. Marcinkowski, S. Schmid, Loop-free route updates for software-defined networks, W: IEEE/ACM Transactions on Networking. - Vol. 26, iss. 1 (2018), s. 328-341 (https://doi.org/10.1109/TNET.2017.2778426).
    22. P. Ghosal, K. Paluch, Manipulation strategies for the rank-maximal matching problem, W: Computing and Combinatorics : 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018. Proceedings / Editors Lusheng Wang, Daming Zhu. - Cham : Springer, 2018. - S. 316-327 (https://doi.org/10.1007/978-3-319-94776-1_27).
    23. M. Karpiński, K. Piecuch, On vertex coloring without monochromatic triangles, W: Computer Science - Theory and Applications : 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018 : Proceedings / Fedor V. Fomin, Vladimir V. Podolskii (eds.). - Cham : Springer International Publishing , 2018. - (Lecture Notes in Computer Science ; 10846). - S. 220-231. - Bibliogr. - Streszcz. w jęz. ang. (https://doi.org/10.1007/978-3-319-90530-3_19).
    24. J. Kowalski, R. Miernik, P. Pytlik, M. Pawlikowski, K. Piecuch, J. Sękowski, Strategic features and terrain generation for balanced Heroes of Might and Magic III Maps, W: CIG 2018 : proceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG'18) : Department of Data Science and Knowledge Engineering, Maastricht University, Maastricht, The Netherlands, 14-17 August, 2018 / editor Mark H.M. Winands. - Piscataway : IEEE, 2018. - S. 86-93 (https://doi.org/10.1109/CIG.2018.8490430).
    25. A. Kunysz, An algorithm for the maximum weight strongly stable matching problem, W: 29th International Symposium on Algorithms and Computation (ISAAC 2018) / Editors Wen-Lian Hsu, Der-Tsai Lee, Chung-Shou Liao. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs : 123). - S. 42:1-42:13 (https://doi.org/10.4230/LIPIcs.ISAAC.2018.42).
    26. A. Ludwig, S. Dudycz, M. Rost, S. Schmid, Transiently policy-compliant network updates, W: IEEE-ACM Transactions on Networking. - Vol. 26, iss. 6 (2018), s. 2569 - 2582 (https://doi.org/10.1109/TNET.2018.2871023).
    27. K. Paluch, Maximum ATSP with weights zero and one via half-edges, W: Theory of Computing Systems. - Vol. 62, iss. 2 (2018), s. 319-336 (https://doi.org/10.1007/s00224-017-9818-1).

  • Combinatorial Optimization Group's Publications for 2017

    1. N. Bansal, M. Eliáš, Ł. Jeż, G. Koumoutsos, The (h, k)-server problem on bounded depth trees, // W: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) / Philip N. Klein (ed.). - New York : ACM, 2017. - S. 1022-1037. (http://dx.doi.org/10.1137/1.9781611974782.65)
    2. M. Bieńkowski, A. Kraska, P. Schmidt, A deterministic algorithm for online Steiner tree leasing // W: Algorithms and Data Structures : 15th International Symposium, WADS 2017, St. John's, NL Canada, July 31- August 2, 2017, Proceedings / Ellen Faith, Antonina Kolokolova, Jörg-Rüdiger Sack (eds.). - Cham : Springer International Publishing - Springer, 2017. - (Lecture Notes in Computer Science ; 10389).- S. 169-180. (https://doi.org/10.1007/978-3-319-62127-2_15)
    3. M. Bieńkowski, J. Byrka, M. Mucha, Dynamic beats fixed: on phase-based algorithms for file migration, // W: 44th International Colloquium on Automata, Languages, and Programming : ICALP 2017, Warsaw, Poland, July 10-14, 2017 / Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, Anca Muscholl (eds.). - Saarbrücken/Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. - (Leibniz International Proceedings in Informatics (LIPIcs) ; 80).- S. 13-1-13-14. (https://doi.org/10.4230/LIPIcs.ICALP.2017.13)
    4. M. Bieńkowski, J. Marcinkowski, M. Pacut, S. Schmid, A. Spyra, Online tree caching, // W: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, Washington, DC, USA, July 24 - 26, 2017 / Christian Scheideler (General Chairs). - New York : ACM, 2017.- S. 329-338. (https://doi.org/10.1145/3087556.3087558)
    5. T. Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, M. Shalom, P.W.H. Wong, S. Zaks, Complexity and online algorithms for minimum skyline coloring of intervals, // W: Combinatorial Optimization and Applications : 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II / Xiaofeng Gao, Hongwei Du, Meng Han (eds.). - Cham : Springer International Publishing - Springer, 2017. - (Lecture Notes in Computer Science ; 10628).- S. 317-332. (https://doi.org/10.1007/978-3-319-71147-8_22)
    6. C. Fuerst, Maciej Pacut, S. Schmid, Data locality and replica aware virtual cluster embeddings, Theoretical Computer Science. - Vol. 697 (2017), s. 37-57. (https://doi.org/10.1016/j.tcs.2017.06.025)
    7. S. Dudycz, J. Marcinkowski, K. Paluch, B. Rybicki, A 4/5 - approximation algorithm for the maximum traveling salesman problem, // W: Integer Programming and Combinatorial Optimization : 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings / Friedrich Eisenbrand, Jochen Koenemann (eds.). - Cham : Springer International Publishing - Springer, 2017. - (Lecture Notes in Computer Science ; 10328).- S. 173-185. (https://doi.org/10.1007/978-3-319-59250-3_15)
    8. M. Cygan, Ł. Kowalik, A. Socała, K. Sornat, Approximation and parameterized complexity of minimax approval voting, // W: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, Twenty-Ninth Innovative Applications of Artificial Intelligence Conference, Seventh Symposium on Educational Advances in Artificial Intelligence : 4-9 February 2017, San Francisco, California, USA / AAAI-17 San Francisco, Vol.1 / Satinder P. Singh, Shaul Markovitch: (eds.). - Palo Alto : AAAI Press, 2017.- S. 459-465. (https://tinyurl.com/y6wj7kg3)
    9. J. Byrka, T. Pensyl, B. Rybicki, A. Srinivasan, K. Trinh, An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization, ACM Transactions on Algorithms 13(2): 23:1-23:31 (2017). (https://doi.org/10.1145/2981561)
    10. C. Dürr, Ł. Jeż, Ó.C. Vásquez, Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling, Theoretical Computer Science 695: 28-41 (2017). (https://dx.doi/10.1016/j.tcs.2017.07.020)
    11. Ł. Jeż, Y. Mansour, B. Patt-Shamir, Scheduling multipacket frames with frame deadlines, Journal of Scheduling 20(6): 623-634 (2017). (https://doi.org/10.1007/s10951-017-0522-4)

  • Combinatorial Optimization Group's Publications for 2016

    1. Ł. Jeż, Y. Azar, A. Epstein, A. Vardi, Make-to-order integrated scheduling and distribution, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms / Robert Krauthgamer (ed.). - New York : Society for Industrial and Applied Mathematics, 2016. - (Proceedings).- S. 140-154. (http://epubs.siam.org/doi/pdf/10.1137/1.9781611974331.ch11)
    2. Ł. Jeż, M. Cygan, J. Sgall, Online knapsack revisited, Theory of Computing Systems. - Vol. 58, iss. 1 (2016), s. 153-190. (http://dx.doi.org/10.1007/s00224-014-9566-4)
    3. Ł. Jeż, L. Epstein, J. Sgall, R. van Stee, Online scheduling of jobs with fixed start times on related machines, Algorithmica. - Vol. 74, iss. 1 (2016), s. 156-176. (http://dx.doi.org/10.1007/s00453-014-9940-2)
    4. M. Bieńkowski, L. Gąsieniec, M. Klonowski, M. Korzeniowski, B. Mans, S. Schmid, R. Wattenhofer, Distributed alarming in the on-duty and off-duty models, IEEE/ACM Transactions on Networking. - Vol. 24, iss. 1 (2016), s. 218-230. (http://dx.doi.org/10.1109/TNET.2014.2359684)
    5. J. Byrka, B. Rybicki, S. Uniyal, An approximation algorithm for uniform capacitated k-median problem with 1+ε capacity violation, W: Integer Programming and Combinatorial Optimization : 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings / Quentin Louveaux, Martin Skutella (eds.). - Cham : Springer International Publishing, 2016. - (Lecture Notes in Computer Science ; 9682). - S. 262-274. (http://dx.doi.org/10.1007/978-3-319-33461-5_22)
    6. J. Byrka, M. Lewandowski, C. Moldenhauer, Approximation algorithms for node-weighted prize-collecting steiner tree problems on planar graphs, W: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) / Rasmus Pagh (ed.). - Wadern : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2016. - ((LIPIcs - Leibniz International Proceedings in Informatics ; 53).- S. 2:1-2:14. (http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.2)
    7. J. Byrka, L. Shanfei, B. Rybicki, Improved approximation algorithm for k-level uncapacitated facility location problem (with penalties), Theory of Computing Systems. - Vol. 58, nr 1 (2016), s. 19-44. (http://dx.doi.org/10.1007/s00224-014-9575-3)
    8. C. Fuerst, M. Pacut, P. Costa, S. Schmid, How hard can it be?: understanding the complexity of replica aware virtual cluster embeddings, W: 2015 IEEE 23rd International Conference on Network Protocols (ICNP 2015) : San Francisco, CA, USA, 10-13 November 2015 : proceedings / Srikanth V. Krishnamurthy, Prasant Mohapatra (General Chairs) . - Los Alamitos : IEEE Computer Society, 2016.- S. 11-21. (http://dx.doi.org/10.1109/ICNP.2015.30)
    9. A. Kunysz, K. Paluch, P. Ghosal, Characterisation of strongly stable matchings, W: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms / Robert Krauthgamer (ed.). - New York : Society for Industrial and Applied Mathematics, 2016. - (Proceedings).- S. 107-119. (http://dx.doi.org/10.1137/1.9781611974331.ch8)
    10. M. Bieńkowski, M. Böhm, J. Byrka, M. Chrobak, C. Dürr, L. Folwarczný, Ł. Jeż, J. Sgall, N. K. Thang, P. Veselý, Online algorithms for multi-level aggregation, W: 24th Annual European Symposium on Algorithms (ESA 2016) / Piotr Sankowski, Christos Zaroliagis (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. - (LIPIcs - Leibniz International Porceedings in Informatics ; 57).- S. 12:1-12:17.(http://dx.doi.org/10.4230/LIPIcs.ESA.2016.12)
    11. M. Bieńkowski, M. Klonowski, M. Korzeniowski, D. R. Kowalski, Randomized mutual exclusion on a multiple access channel, Distributed Computing. - Vol. 29, iss. 5 (2016), s. 341-359. (http://dx.doi.org/10.1007/s00446-016-0265-z)
    12. M. Böhm, M. Chrobak, Ł. Jeż, F. Li, J. Sgall, P. Veselý, Online packet scheduling with bounded delay and lookahead, W: 27th International Symposium on Algorithms and Computation (ISAAC 2016), December 12-14, 2016 - Sydney, Australia / ed. Seok-Hee Hong. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. - (LIPIcs - Leibniz International Proceedings in Informatics ; 64).- S. 21:1-21:13. (http://dx.doi.org/10.4230/LIPIcs.ISAAC.2016.21)
    13. A. Kunysz, The strongly stable roommates problem, W: 24th Annual European Symposium on Algorithms (ESA 2016) / Piotr Sankowski and Christos Zaroliagis (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. - (LIPIcs - Leibniz International Porceedings in Informatics ; 57).- S. 60:1-60:15. (http://dx.doi.org/10.4230/LIPIcs.ESA.2016.60)
    14. C. Avin, A. Loukas, M. Pacut, S. Schmid, Online balanced repartitioning, W: Distributed computing : 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016 : proceedings / Cyril Gavoille, David Ilcinkas (eds.). - Berlin ; Heidelberg : Springer, 2016. - (Lecture Notes in Computer Science ; 9888).- S. 243-256. (http://dx.doi.org/10.1007/978-3-662-53426-7_18)
    15. G. Amanatidis, E. Markakis, K. Sornat, Inequity aversion pricing over social networks: : approximation algorithms and hardness results, W: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) / Piotr Faliszewski, Anca Muscholl, Rolf Niedermeier (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. - (Leibniz International Proceedings in Informatics (LIPIcs) ; 58).- S. 9:1-9:13. (http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.9)

  • Combinatorial Optimization Group's Publications for 2015

    1. M. Bieńkowski, J. Byrka, T. Jurdziński, K.Chrobak, D. R. Kowalski, Provable fairness for TDMA scheduling, IEEE Conference on Computer Communications, INFOCOM 2015, Kowloon, Hong Kong, April 26 - May 1, 2015, Proceedings. - Piscataway : IEEE, 2015.- S. 1320-1327. (http://dx.doi.org/10.1109/INFOCOM.2015.7218508).
    2. J. Byrka, B. Rybicki, T. Pensyl, J. Spoerhase, A. Srinivasan, K. Trinh, An improved approximation algorithm for knapsack median using sparsification, Algorithms - ESA 2015 : 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings / Nikhil Bansal, Irene Finocchi (eds.). - Berlin : Springer Berlin, 2015. - (Lecture Notes in Computer Science ; 9294). - S. 275-287. (http://dx.doi.org/10.1007/978-3-662-48350-3_24).
    3. J. Byrka, B. Rybicki, T. Pensyl, A. Srinivasan, K. Trinh, An improved approximation for k-median, and positive correlation in budgeted optimization, SODA '15 Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms : [San Diego, California, USA, January 4 - 6, 2015] / [jointly sponsored by SIGACT (the ACM Special Interest Group on Algorithms and Computation Theory) and by the SIAM Activity Group on Discrete Mathematics. Program committee chair Piotr Indyk] / Piotr Indyk (ed.). - New York, Philadelphia : Association for Computing Machinery, Society for Industrial and Applied Mathematics, 2015. - S. 737-756. (http://dx.doi.org/10.1137/1.9781611973730.50).
    4. J. Byrka, B. Rybicki, K. Fleszar, J. Spoerhase, Bi-factor approximation algorithms for hard capacitated k-median problems, SODA '15 Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms : [San Diego, California, USA, January 4 - 6, 2015] / [jointly sponsored by SIGACT (the ACM Special Interest Group on Algorithms and Computation Theory) and by the SIAM Activity Group on Discrete Mathematics. Program committee chair Piotr Indyk] / Piotr Indyk (ed.). - New York, Philadelphia : Association for Computing Machinery, Society for Industrial and Applied Mathematics, 2015.- S. 722-736. (http://dx.doi.org/10.1137/1.9781611973730.49).
    5. J. Byrka, A. Karrenbauer, L. Sanita, The interval constrained 3-coloring problem, Theoretical Computer Science. - Vol. 593 (2015), s. 42-50. (http://dx.doi.org/10.1016/j.tcs.2015.04.037).
    6. M. Bieńkowski, J. Byrka, M. Chrobak, N. Dobbs, T. Nowicki, M. Sviridenko, G. Świrszcz, N. E. Young, Approximation algorithms for the joint replenishment problem with deadlines, Journal of Scheduling. - Vol.18, iss. 6 (2015), s. 545-560. (http://dx.doi.org/10.1007/s10951-014-0392-y).
    7. M. Bieńkowski, N. Sarrar, R. Wuttke, S. Schmid, S. Uhlig, Leveraging locality for FIB aggregation, 2014 IEEE Global Communications Conference (GLOBECOM 2014) : Austin, Texas, USA, 8 - 12 December 2014 / IEEE. - Piscataway : IEEE, 2015.- S. 1930-1935. (http://dx.doi.org/10.1109/GLOCOM.2014.7037090).
    8. M. Bieńkowski, A. Kraska, P. Schmidt, A randomized algorithm for online scheduling with interval conflicts, Structural Information and Communication Complexity : 22nd International Colloquium, Sirocco 2015, Montserrat, Spain, July 14-16, 2015 : Revised Selected Papers / Christian Schneideler (ed.). - Cham : Springer-Verlag, 2015. - (Lecture notes in computer science ; 9439).- S. 91-103. (http://dx.doi.org/10.1007/978-3-319-25258-2_7).
    9. I.R. Cohen, A. Eden, A. Fiat, Ł. Jeż, Pricing online decisions: beyond auctions, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms : [San Diego, California, USA, January 4 - 6, 2015] / [jointly sponsored by SIGACT (the ACM Special Interest Group on Algorithms and Computation Theory) and by the SIAM Activity Group on Discrete Mathematics / Piotr Indyk (eds.). - New York, Philadelphia : Association for Computing Machinery; Society for Industrial and Applied Mathematics, 2015. - (Proceedings in applied mathematics / SIAM ; 146).- S. 73-91. (http://dx.doi.org/10.1137/1.9781611973730.7).
    10. Ł. Jeż, Y. Mansour, B. Patt-Shamir, Scheduling multipacket frames with frame deadlines, Structural Information and Communication Complexity : 22nd International Colloquium, Sirocco 2015, Montserrat, Spain, July 14-16, 2015 : Revised Selected Papers / Christian Schneideler (ed.). - Cham : Springer-Verlag, 2015. - (Lecture Notes in Computer Science ; 9439). - S. 76-90. (http://dx.doi.org/10.1007/978-3-319-25258-2_6).
    11. Ł. Jeż, C. Dürr, O.C. Vásquez, Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption, Discrete Applied Mathematics. - Vol. 196 (2015), s. 20-27. (http://dx.doi.org/10.1016/j.dam.2014.08.001).
    12. J. Byrka, B. Rybicki, Improved approximation algorithm for fault-tolerant facility placement, Approximation and Online Algorithms : 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers / Evripidis Bampis, Ola Svensson (eds.). - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 8952).- S. 59-70. (http://dx.doi.org/10.1007/978-3-319-18263-6_6).
    13. Ł. Jeż, N. Bansal, M. Elias, G. Koumoutsos, K. Pruhs, Tight bounds for double coverage against weak adversaries, Approximation and Online Algorithms : 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers / Laura Sanita, Martin Skutella (eds.). - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 9499).- S. 47-58. (http://dx.doi.org/10.1007/978-3-319-28684-6_5).
    14. K. Paluch, Maximum ATSP with weights zero and one via half-edges, Approximation and Online Algorithms : 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers / Laura Sanita, Martin Skutella (eds.). - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 9499). - S. 25-34. (http://dx.doi.org/10.1007/978-3-319-28684-6_3).

  • Combinatorial Optimization Group's Publications for 2014

    1. P. Gawrychowski, Ł. Jeż, A. Jeż, Validating the Knuth-Morris-Pratt failure function, fast and online, Theory of Computing Systems. - Vol. 54, iss. 2 (2014), s. 337-372. (http://dx.doi.org/10.1007/s00224-013-9522-8).
    2. W. Bożejko, M. Karpiński, M. Pacut, M. Wodecki, Multi-GPU parallel memetic algorithm for capacitated vehicle routing problem, Parallel Processing and Applied Mathematics : 10th International Conference, PPAM 2013, Warsaw, Poland, September 8-11, 2013, Revised Selected Papers, Part 2 / Roman Wyrzykowski, Jack Dongarra, Konrad Karczewski, Jerzy Wasniewski (eds.). - Berlin : Springer Berlin, 2014. - (Lecture Notes in Computer Science ; 8385).- S. 207-214. (http://dx.doi.org/10.1007/978-3-642-55195-6_19).
    3. M. Bieńkowski, J. Byrka, Ł. Jeż, M. Chrobak, D. Nogneng, J. Sgall, Better Approximation Bounds for the Joint Replenishment Problem, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 42-54. (http://epubs.siam.org/doi/pdf/10.1137/1.9781611973402.4).
    4. M. Bieńkowski, N. Sarrar, S. Schmid, S. Uhlig, Competitive FIB Aggregation without Update Churn, IEEE 34th International Conference on Distributed Computing Systems, ICDCS 2014, Madrid, Spain, June 30 - July 3, 2014. IEEE 2014 strony 607-616.
    5. M. Bieńkowski, A. Feldmann, J. Grassler, G. Schaffrath, S. Schmid, The Wide-Area Virtual Service Migration Problem: A Competitive Analysis Approach, IEEE/ACM Transactions on Networking, Volume 22, Number 1, February 2014 strony 165-178.
    6. M. Bieńkowski, An Optimal Lower Bound for Buffer Management in Multi-Queue Switches, Algorithmica, Volume 68, Number 1, January 2014 strony 426-447.
    7. W. Bożejko, M. Karpiński, M. Pacut, M. Wodecki, Multi-GPU Parallel Memetic Algorithm for Capacitated Vehicle Routing Problem, Lecture Notes in Computer Science No. 8386, Springer (2014), 207-214.
    8. J. Byrka, K. Sornat, PTAS for Minimax Approval Voting, The 10th Conference on Web and Internet Economics, WINE 2014, Pekin, Chiny, Lecture Notes in Computer Science, Vol. 8877 (2014), ISBN 978-3-319-13128-3, Springer, strony 203-217. (http://link.springer.com/chapter/10.1007/978-3-319-13129-0_15).
    9. K. Paluch, Faster and Simpler Approximation of Stable Matchings, Algorithms 2014, 7(2), 189-202. (http://dx.doi.org/10.3390/a7020189).
    10. K. Paluch, Popular and clan-popular b-matchings, Theoretical Computer Science 544: 3-13 (2014). (http://dx.doi.org/10.1016/j.tcs.2014.04.017).

  • Combinatorial Optimization Group's Publications for 2013

    1. M. Bieńkowski, M. Chrobak, C. Dürr, M. Hurand, Ł. Jeż, A. Jeż, G. Stachowiak, Collecting Weighted Items from a Dynamic Queue, Algorithmica, January 2013, Volume 65, Issue 1, pp 60-94. (http://dx.doi.org/10.1007/s00453-011-9574-6).
    2. M. Bieńkowski, M. Chrobak, C. Dürr, M. Hurand, Ł. Jeż, G. Stachowiak, A phi-competitive algorithm for collecting items with increasing weights from a dynamic queue, Theoretical Computer Science, Volume 475, 4 March 2013, Pages 92-102. (http://dx.doi.org/10.1016/j.tcs.2012.12.046).
    3. M. Bieńkowski, J. Byrka, M. Chrobak, N. Dobbs, T. Nowicki, M. Sviridenko, G. Świrszcz, N. E. Young, Approximation algorithms for the joint replenishment problem with deadlines, Automata, languages, and programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, Part I / Fedor V. Fomin, Rusinš Freivalds, Marta Kwiatkowska, David Peleg (eds.). - Berlin, Heidelberg : Springer, 2013. - (Lecture Notes in Computer Science ; Vol. 7965).- S. 135-147. (http://dx.doi.org/10.1007/978-3-642-39206-1_12).
    4. M. Bieńkowski, J. Byrka, Ł. Jeż, M. Chrobak, J. Sgall, Online control message aggregation in chain networks, Algorithms and Data Structures : 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings / Frank Dehne, Roberto Solis-Oba, Jörg-Rüdiger Sack (eds.). - Berlin, Heidelberg : Springer, 2013. - (Lecture Notes in Computer Science ; Vol. 8037). - S. 133-145. (http://dx.doi.org/10.1007/978-3-642-40104-6_1).
    5. Ł. Jeż, C. Dürr, Ó. C. Vásquez, Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling, Web and Internet Economics : 9th International Conference, WINE 2013, Cambridge, MA, USA, December 11-14, 2013 : proceedings / Yiling Chen, Nicole Immorlica (eds.). - Berlin [u.a.] : Springer International Publishing, 2013. - (Lecture Notes in Computer Science ; Vol.8289).- S. 134-145. (http://dx.doi.org/10.1007/978-3-642-45046-4_12).
    6. M. Bieńkowski, P. Zalewski, (1, 2)-Hamiltonian completion on a matching, International Journal of Foundations of Computer Science. - Vol. 24, no 01 (2013), s. 95-108. (http://dx.doi.org/10.1142/S0129054113500019).
    7. J. Byrka, F. Grandoni, T. Rothvoss, L. Sanita, Steiner tree approximation via iterative randomized rounding, Journal of the ACM. - Vol. 60, iss. 1 (2013), nr art. 6 (33 str.). (http://dx.doi.org/10.1145/2432622.2432628).
    8. Ł. Jeż, M. Chrobak, J. Sgall, Better bounds for incremental frequency allocation in bipartite graphs, Theoretical Computer Science. - Vol.514 (2013), s. 75-83. (http://dx.doi.org/10.1016/j.tcs.2012.05.020).
    9. J. Schwartz, J. Sgall, J. Békési, Ł. Jeż, Lower bounds for online makespan minimization on a smallnumber of related machines, Journal of Scheduling. - Vol. 16, nr 5 (2013), s. 539-547. (http://dx.doi.org/10.1007/s10951-012-0288-7).
    10. Ł. Jeż, A universal randomized packet scheduling algorithm, Algorithmica. - Vol. 67, nr 4 (2013), s. 498-515. (http://dx.doi.org/10.1007/s00453-012-9700-0).
    11. M. Bieńkowski, S. Schmid, Competitive FIB Aggregation: Online Ski Rental on the Trie, 20th Int. Colloquium on Structural Information and Communication Complexity (SIROCCO), Springer 2013, (Lecture Notes in Computer Science vol. 8205), s. 583-584. (http://www.ii.uni.wroc.pl/~mbi/papers/2013-sirocco-fib-compression.pdf).
    12. M. Bieńkowski, N. Sarrar, S. Schmid, S. Uhlig, Brief Announcement: Dynamic Forwarding Table Aggregation without Update Churn: The Case of Dependent Prefixes, 27th Int. Symposium on DIStributed Computing (DISC), Springer 2013, (Lecture Notes in Computer Science vol. 8179), s. 92-103. (http://www.ii.uni.wroc.pl/~mbi/papers/2013-disc-ba-fib-aggregation.pdf).
    13. K. Paluch, Capacitated Rank-Maximal Matchings, 8th International Conference on Algorithms and Complexity CIAC 2013-Springer 2013 (Lecture Notes in Computer Science Vol. 7878) 2013, s. 324-335. (http://dx.doi.org/10.1007/978-3-642-38233-8_27).
    14. M. Cygan, Ł. Jeż, Online Knapsack Revisited, Approximation and Online Algorithms Lecture Notes in Computer Science Volume 8447, 2014, pp 144-155. (http://link.springer.com/chapter/10.1007%2F978-3-319-08001-7_13).
    15. J. Byrka, S. Li, B. Rybicki, Improved Approximation Algorithm for k-Level UFL with Penalties, a Simplistic View on Randomizing the Scaling Parameter, WAOA 2013: 85-96.