Combinatorial optimization through the lens of the traveling salesman route and matchings
2018/29/B/ST6/02633
Keywords
Descriptors
- ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
Panel
ST6 – Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems
Host institution
Uniwersytet Wrocławski, Wydział Matematyki i Informatyki
Voivodeship: dolnośląskie
Principal investigator (from the host institution)
Number of co-investigators in the project: 5
Call
OPUS 15 – announced on 2018-03-15
- Amount awarded
- 588 000 PLN
- Project start date
- 2019-01-31
- Project end date
- 2024-09-29
- Project duration
- 68 months (the same as in the proposal)
- Project status
- Project settled
Project description
Download the project description in a pdf file
Note — project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.
Information in the final report
Publication in academic press/journals (2)
-
A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs - via half-edges
- Authors:
- Katarzyna Paluch and Mateusz Wasylkiewicz
- Academic press:
- Information Processing Letters (year: 2021, volume: 171, pages: 106146), Publisher: Elsevier
- Status:
- Published
- DOI:
- 10.1016/j.ipl.2021.106146 – link to the publication
-
The Dynamics of Rank-Maximal and Popular Matchings
- Authors:
- Pratik Ghosal and Adam Kunysz and Katarzyna Paluch
- Academic press:
- Theoretical Computer Science (year: 2023, volume: 972, pages: 114083), Publisher: Elsevier
- Status:
- Published
- DOI:
- 10.1016/j.tcs.2023.114083 – link to the publication
Articles in post-conference publications (6)
-
A Faster Algorithm for the Strongly Stable b-Matching Problem
- Authors:
- Adam Kunysz
- Conference:
- CIAC'2019 Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings. Lecture Notes in Computer Science 11485, Springer 2019, ISBN 978-3-030-17401-9 (year: 2019, pages: 12), Publisher: Springer
- Date:
- conference 27-29.05.2019
- Status:
- Published
-
Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems
- Authors:
- Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski
- Conference:
- Approximation and Online Algorithms - 19th International Workshop, WAOA 2021 (year: 2021, pages: 48-64), Publisher: Springer
- Date:
- conference 6-10.09.2021
- Status:
- Published
-
Rectangle Tiling Binary Arrays
- Authors:
- Pratik Ghosal, Syed Mohammad Meesum, Katarzyna Paluch
- Conference:
- International Conference on Approximation Algorithms for Combinatorial Optimization Problems. APPROX 2024 (year: 2024, pages: 28:1-28:17), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
- Date:
- conference 28-30.08.2024
- Status:
- Published
-
Finding Perfect Matchings in Bridgeless Cubic Multigraphs Without Dynamic (2-)connectivity
- Authors:
- Paweł Gawrychowski and Mateusz Wasylkiewicz
- Conference:
- 32nd Annual European Symposium on Algorithms, {ESA} 2024, September 6-8, 2021, Lisbon, Portugal (year: 2024, pages: 59:1-59:14), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
- Date:
- conference 2-4.09.2024
- Status:
- Published
-
Restricted t-Matchings via Half-Edges
- Authors:
- Katarzyna Paluch, Mateusz Wasylkiewicz
- Conference:
- 29th Annual European Symposium on Algorithms, {ESA} 2021, September 6-8, 2021, Lisbon, Portugal (year: 2021, pages: 73:1--73:17), Publisher: Schloss Dagstuhl - Leibniz-Zentrum f{{u}}r Informatik
- Date:
- conference 6-8.09.2021
- Status:
- Published
-
Tight Approximation for Proportional Approval Voting
- Authors:
- Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, Krzysztof Sornat
- Conference:
- IJCAI-PRICAI 2020 (year: 2020, pages: 276-282), Publisher: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020. ijcai.org 2020
- Date:
- conference 11-17.07.2020
- Status:
- Published
- DOI:
- link to the publication