Instytut Informatyki
Menu
badania

Publikacje

  • Publikacje Zakładu Optymalizacji Kombinatorycznej w roku 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).

  • Publikacje Zakładu Optymalizacji Kombinatorycznej w roku 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).

  • Publikacje Zakładu Optymalizacji Kombinatorycznej w roku 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)

  • Publikacje Zakładu Optymalizacji Kombinatorycznej w roku 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)

  • Publikacje Zakładu Optymalizacji Kombinatorycznej w roku 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).

  • Publikacje Zakładu Optymalizacji Kombinatorycznej w roku 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).

  • Publikacje Zakładu Optymalizacji Kombinatorycznej w roku 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.
Używamy ciasteczek w celach statystycznych.Rozumiem