Menu
  • 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.