Katarzyna Paluch


About me

PhD in 2005 from University of Wroclaw. Currently assistant professor at Institute of Computer Science, University of Wroclaw.

Papers

  1. Rectangle Tiling Co-author: Krzysztof Lorys. APPROX 2000, 206-213
  2. New approximation algorithm for RTILE problem. . Co-author: Krzysztof Lorys Theor. Comput. Sci. 2-3(303): 517-537 (2003)
  3. Rank-maximal matchings. Co-authors: Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail SODA 2004: 68-75
  4. Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem. Co-authors: Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail. STACS 2004: 222-233
  5. A Faster Algorithm for Minimum Cycle Basis of Graphs. Co-authors: Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail. ICALP 2004: 846-857
  6. A 17/8-Approximation Algorithm for Rectangle Tiling. ICALP 2004: 1054-1065
  7. A New Approximation Algorithm for Multidimensional Rectangle Tiling. ISAAC 2006: 712-721
  8. Rank-maximal matchings. Co-authors: Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail ACM Transactions on Algorithms 2(4): 602-610 (2006)
  9. Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem. Co-authors: Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail. ACM Transactions on Algorithms 3(2): (2007)
  10. An O(m^{2}n) Algorithm for Minimum Cycle Basis of Graphs. Co-authors: Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail. Algorithmica 52(3): 333-349 (2008)
  11. A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem. Co-authors: Marcin Mucha, Aleksander Madry CoRR abs/0812.5101: (2008), APPROX-RANDOM 2009: 298-311
  12. Faster and simpler approximation of stable matchings. CoRR abs/0911.5660, WAOA 2011, Algorithms
  13. Popular and clan-popular b-matchings. ISAAC 2012, Theoretical Computer Science
  14. Capacitated Rank-maximal Matchings. CIAC 2013
  15. A combinatorial algorithm for two matchings: fair and maximum rank-maximal. Manuscript.
  16. Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem. Co-authors: Khaled Elbassioni, Anke van Zuylen. STACS 2012
  17. Better Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring. arXiv:1401.3670 [arXiv]
  18. Maximum ATSP with Weights Zero and One via Half-Edges. arXiv:1408.1431 [arXiv] WAOA 2015
  19. Balanced matchings, unbalanced ones and related problems. CTW 2015
  20. Characterisation of Strongly Stable Matchings. Co-authors: Adam Kunysz, Pratik Ghosal arXiv:1506.00677 [arXiv] SODA 2016
  21. A 4/5-Approximation Algorithm for the Maximum Traveling Salesman Problem. Co-authors: Szymon Dudycz, Jan Marcinkowski, Bartosz Rybicki arXiv: [arXiv] IPCO 2017
  22. The Dynamics of Rank-Maximal and Popular Matchings. Co-authors: Pratik Ghosal, Adam Kunysz arXiv: [arXiv]
  23. Optimal General Matchings. Co-author: Szymon Dudycz arXiv: [arXiv]
PhD thesis [ps] 

Research interests

  • approximation algorithms
  • graphs
  • combinatorial optimisation

Scientific involvements


Teaching (in Polish)

  • Konsultacje i wpisy do indeksow beda mozliwe od 03.07.

    Office hours

  • W czasie sesji terminy konsultacji prosze uzgadniac indywidualnie.

    Addresses and telephones

    Institute of Computer Science
    University of Wroclaw
    ul. Joliot-Curie 15, room 304
    50–383 Wroc³aw
    phone: (+48)71-37-57-821
    email:
    abraka at cs dot uni dot wroc dot pl