Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Efficient algorithms for finding optiml tours of a traveling salesman and related problems

2013/11/B/ST6/01748

Keywords:

traveling salesman problem approximation algorithms combinatorial optimization

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST1_14: Discrete mathematics and combinatorics

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

woj. dolnośląskie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr Katarzyna Paluch 

Number of co-investigators in the project: 2

Call: OPUS 6 - announced on 2013-09-16

Amount awarded: 207 240 PLN

Project start date (Y-m-d): 2014-08-12

Project end date (Y-m-d): 2018-08-11

Project duration:: 48 months (the same as in the proposal)

Project status: Project settled

Equipment purchased [PL]

  1. Komputer typu laptop z wyposażeniem (6 000 PLN)

Information in the final report

  • Publication in academic press/journals (1)
  • Articles in post-conference publications (9)
  1. Maximum ATSP with Weights Zero and One via Half-Edges
    Authors:
    Katarzyna Paluch
    Academic press:
    Theory of Computing Systems (rok: 2018, tom: 62(2), strony: 319-336), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00224-017-9818-1 - link to the publication
  1. Maximum ATSP with Weights Zero and One via Half-Edges
    Authors:
    Katarzyna Paluch
    Conference:
    Approximation and Online Algorithms - 13th International Workshop, WAOA 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 17-18.09.2015
    Status:
    Published
    DOI:
    link to the publication
  2. New approximation algorithms for (1,2)-TSP
    Authors:
    Anna Adamaszek, Matthias Mnich, Katarzyna E. Paluch
    Conference:
    ICALP 2018 (rok: 2018, ), Wydawca: DROPS
    Data:
    konferencja 9-13.07.2018
    Status:
    Published
    DOI:
    link to the publication
  3. Manipulation Strategies for the Rank-Maximal Matching Problem
    Authors:
    Pratik Ghosal and Katarzyna Paluch
    Conference:
    COCOON 2018 (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 2-4.07.2018
    Status:
    Published
    DOI:
    link to the publication
  4. Optimal General Matchings
    Authors:
    Szymon Dudycz and Katarzyna Paluch
    Conference:
    WG 2018 (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 27-29.06.2018
    Status:
    Published
    DOI:
    link to the publication
  5. 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 (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 26-28.06.2017
    Status:
    Published
    DOI:
    link to the publication
  6. Characterisation of Strongly Stable Matchings
    Authors:
    Adam Kunysz, Katarzyna Paluch, Pratik Ghosal
    Conference:
    Symposium on Discrete Algorithms, SODA 2016 (rok: 2016, ), Wydawca: SIAM
    Data:
    konferencja 10-12.01.2016
    Status:
    Published
    DOI:
    link to the publication
  7. Tight Approximation Ratio for Minimum Maximal Matching
    Authors:
    Szymon Dudycz, Mateusz Lewandowski, Jan Marcinkowski
    Conference:
    IPCO 2019 (rok: 2019, ), Wydawca: Springer
    Data:
    konferencja 22-24.05.2019
    Status:
    Published
    DOI:
    link to the publication
  8. The Strongly Stable Roommates Problem
    Authors:
    Adam Kunysz
    Conference:
    European Symposium on Algorithms: ESA 2016 (rok: 2016, ), Wydawca: DROPS
    Data:
    konferencja 22-24.08.2016
    Status:
    Published
    DOI:
    link to the publication
  9. An Algorithm for the Maximum Weight Strongly Stable Matching Problem
    Authors:
    Adam Kunysz
    Conference:
    ISAAC 2018 (rok: 2018, ), Wydawca: DROPS
    Data:
    konferencja 16-19.12.2018
    Status:
    Published
    DOI:
    link to the publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy