Efficient algorithms for finding optiml tours of a traveling salesman and related problems
2013/11/B/ST6/01748
Keywords
Descriptors
- ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
- ST1_14: Kombinatoryka
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: 2
Call
OPUS 6 – announced on 2013-09-16
- Amount awarded
- 207 240 PLN
- Project start date
- 2014-08-12
- Project end date
- 2018-08-11
- Project duration
- 48 months (the same as in the proposal)
- Project status
- Project settled
Equipment purchased [PL]
- Komputer typu laptop z wyposażeniem. Cost: 6 000 PLN
Information in the final report
Publication in academic press/journals (1)
-
Maximum ATSP with Weights Zero and One via Half-Edges
- Authors:
- Katarzyna Paluch
- Academic press:
- Theory of Computing Systems (year: 2018, volume: 62(2), pages: 319-336), Publisher: Springer
- Status:
- Published
- DOI:
- 10.1007/s00224-017-9818-1 – link to the publication
Articles in post-conference publications (9)
-
Maximum ATSP with Weights Zero and One via Half-Edges
- Authors:
- Katarzyna Paluch
- Conference:
- Approximation and Online Algorithms - 13th International Workshop, WAOA 2015 (year: 2015, pages: 25-34), Publisher: Springer
- Date:
- conference 17-18.09.2015
- Status:
- Published
- DOI:
- link to the publication
-
Tight Approximation Ratio for Minimum Maximal Matching
- Authors:
- Szymon Dudycz, Mateusz Lewandowski, Jan Marcinkowski
- Conference:
- IPCO 2019 (year: 2019, pages: 181-193), Publisher: Springer
- Date:
- conference 22-24.05.2019
- Status:
- Published
-
A 4/5 - Approximation Algorithm for the Maximum Traveling Salesman Problem
- Authors:
- Szymon Dudycz, Jan Marcinkowski, Katarzyna E. Paluch, Bartosz Rybicki
- Conference:
- The 19th Conference on Integer Programming and Combinatorial Optimization: IPCO 2017 (year: 2017, pages: 173-185), Publisher: Springer
- Date:
- conference 26-28.06.2017
- Status:
- Published
- DOI:
- link to the publication
-
Manipulation Strategies for the Rank-Maximal Matching Problem
- Authors:
- Pratik Ghosal and Katarzyna Paluch
- Conference:
- COCOON 2018 (year: 2018, pages: 316--327), Publisher: Springer
- Date:
- conference 2-4.07.2018
- Status:
- Published
-
New approximation algorithms for (1,2)-TSP
- Authors:
- Anna Adamaszek, Matthias Mnich, Katarzyna E. Paluch
- Conference:
- ICALP 2018 (year: 2018, pages: 9:1-14), Publisher: DROPS
- Date:
- conference 9-13.07.2018
- Status:
- Published
- DOI:
- link to the publication
-
Optimal General Matchings
- Authors:
- Szymon Dudycz and Katarzyna Paluch
- Conference:
- WG 2018 (year: 2018, pages: 176-189), Publisher: Springer
- Date:
- conference 27-29.06.2018
- Status:
- Published
-
Characterisation of Strongly Stable Matchings
- Authors:
- Adam Kunysz, Katarzyna Paluch, Pratik Ghosal
- Conference:
- Symposium on Discrete Algorithms, SODA 2016 (year: 2016, pages: 107-119), Publisher: SIAM
- Date:
- conference 10-12.01.2016
- Status:
- Published
- DOI:
- link to the publication
-
The Strongly Stable Roommates Problem
- Authors:
- Adam Kunysz
- Conference:
- European Symposium on Algorithms: ESA 2016 (year: 2016, pages: 60:1-60:15), Publisher: DROPS
- Date:
- conference 22-24.08.2016
- Status:
- Published
- DOI:
- link to the publication
-
An Algorithm for the Maximum Weight Strongly Stable Matching Problem
- Authors:
- Adam Kunysz
- Conference:
- ISAAC 2018 (year: 2018, pages: 42:1-13), Publisher: DROPS
- Date:
- conference 16-19.12.2018
- Status:
- Published
- DOI:
- link to the publication