Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Combinatorial optimization through the lens of the traveling salesman route and matchings

2018/29/B/ST6/02633

Keywords:

combinatorial optimization the traveling salesman problem matchings algorithms approximation algorithms graph algorithms

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory

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 hab. Katarzyna Paluch 

Number of co-investigators in the project: 5

Call: OPUS 15 - announced on 2018-03-15

Amount awarded: 588 000 PLN

Project start date (Y-m-d): 2019-01-31

Project end date (Y-m-d): 2024-09-29

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

Project status: Project completed

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 (3)
  • Articles in post-conference publications (4)
  1. The Dynamics of Rank-Maximal and Popular Matchings
    Authors:
    Pratik Ghosal and Adam Kunysz and Katarzyna Paluch
    Academic press:
    Theoretical Computer Science (rok: 2023, tom: 972, strony: 114083), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2023.114083 - link to the publication
  2. Rectangle Tiling Binary Arrays
    Authors:
    Pratik Ghosal, Syed Mohammad Meesum, Katarzyna Paluch
    Academic press:
    Discrete and Computational Geometry , Wydawca: Springer
    Status:
    Submitted
    DOI:
    brak - link to the publication
  3. 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 (rok: 2021, tom: 171, strony: 106146), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ipl.2021.106146 - link to the publication
  1. Tight Approximation for Proportional Approval Voting
    Authors:
    Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, Krzysztof Sornat
    Conference:
    IJCAI-PRICAI 2020 (rok: 2020, ), Wydawca: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020. ijcai.org 2020
    Data:
    konferencja 11-17.07.2020
    Status:
    Published
    DOI:
    link to the publication
  2. 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 (rok: 2021, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum f{"{u}}r Informatik
    Data:
    konferencja 6-8.09.2021
    Status:
    Published
  3. 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 (rok: 2019, ), Wydawca: Springer
    Data:
    konferencja 27-29.05.2019
    Status:
    Published
  4. 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 (rok: 2021, ), Wydawca: Springer
    Data:
    konferencja 6-10.09.2021
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy