Katarzyna Paluch

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 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] WAOA 2015, journal version: [TOCS]
19. Balanced matchings, unbalanced ones and related problems. CTW 2015
20. Characterisation of Strongly Stable Matchings. Co-authors: Adam Kunysz, Pratik Ghosal [arXiv] SODA 2016
21. A 4/5-Approximation Algorithm for the Maximum Traveling Salesman Problem. Co-authors: Szymon Dudycz, Jan Marcinkowski, Bartosz Rybicki [arXiv] IPCO 2017
22. The Dynamics of Rank-Maximal and Popular Matchings. Co-authors: Pratik Ghosal, Adam Kunysz [arXiv] Theoretical Computer Science (2024)
23. Optimal General Matchings. Co-author: Szymon Dudycz [arXiv] WG 2018
24. Manipulation Strategies for the Rank-Maximal Matching Problem. Co-author: Pratik Ghosal COCOON 2018
25. New approximation algorithms for (1,2)-TSP. Co-authors: Anna Adamaszek and Matthias Mnich ICALP 2018
26. Rectangle tiling binary arrays. Co-authors: Pratik Ghosal and Syed Mohammas Meesum [arXiv] APPROX 2024
27. A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs - via half-edges. Co-author: Mateusz Wasylkiewicz [IPL], arXiv
28. New approximation algorithms for maximum asymmetric traveling salesman and shortest superstring. [arXiv] - this is a simpler but weaker version of [17], a fully detailed [17] would be significantly longer than this weaker version.
29. Restricted t-matchings via half-edges. Co-author: Mateusz Wasylkiewicz [ESA-2021]
30. Clique-free t-matchings in degree-bounded graphs. Co-author: Mateusz Wasylkiewicz SOFSEM 2026
31. Triangle-free 2-matchings. [arXiv] This is a simpler and faster alternative to Hartvigsen's algorithm.