Projekty finansowane przez NCN


Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Efektywne algorytmy aproksymacyjne dla znajdowania optymalnej trasy komiwojażera i problemów pokrewnych

2013/11/B/ST6/01748

Słowa kluczowe:

problem komiwojażera algorytmy aproksymacyjne optymalizcja kombinatoryczna

Deskryptory:

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST1_14: Kombinatoryka

Panel:

ST6 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne

Jednostka realizująca:

Uniwersytet Wrocławski, Wydział Matematyki i Informatyki

woj. dolnośląskie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

dr Katarzyna Paluch 

Liczba wykonawców projektu: 2

Konkurs: OPUS 6 - ogłoszony 2013-09-16

Przyznana kwota: 207 240 PLN

Rozpoczęcie projektu: 2014-08-12

Zakończenie projektu: 2018-08-11

Planowany czas trwania projektu: 36 miesięcy (z wniosku)

Status projektu: Projekt rozliczony

Zakupiona aparatura

  1. Komputer typu laptop z wyposażeniem. Za kwotę 6 000 PLN

Dane z raportu końcowego

  • Publikacje w czasopismach (1)
  • Teksty w publikacjach pokonferencyjnych (9)
  1. Maximum ATSP with Weights Zero and One via Half-Edges IF: 0,645
    Autorzy:
    Katarzyna Paluch
    Czasopismo:
    Theory of Computing Systems (rok: 2018, tom: 62(2), strony: 319-336), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00224-017-9818-1 - link do publikacji
  1. Maximum ATSP with Weights Zero and One via Half-Edges
    Autorzy:
    Katarzyna Paluch
    Konferencja:
    Approximation and Online Algorithms - 13th International Workshop, WAOA 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 17-18.09.2015
    Status:
    Opublikowana
  2. Characterisation of Strongly Stable Matchings
    Autorzy:
    Adam Kunysz, Katarzyna Paluch, Pratik Ghosal
    Konferencja:
    Symposium on Discrete Algorithms, SODA 2016 (rok: 2016, ), Wydawca: SIAM
    Data:
    konferencja 10-12.01.2016
    Status:
    Opublikowana
  3. Manipulation Strategies for the Rank-Maximal Matching Problem
    Autorzy:
    Pratik Ghosal and Katarzyna Paluch
    Konferencja:
    COCOON 2018 (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 2-4.07.2018
    Status:
    Opublikowana
  4. A 4/5 - Approximation Algorithm for the Maximum Traveling Salesman Problem
    Autorzy:
    Szymon Dudycz, Jan Marcinkowski, Katarzyna E. Paluch, Bartosz Rybicki
    Konferencja:
    The 19th Conference on Integer Programming and Combinatorial Optimization: IPCO 2017 (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 26-28.06.2017
    Status:
    Opublikowana
  5. Tight Approximation Ratio for Minimum Maximal Matching
    Autorzy:
    Szymon Dudycz, Mateusz Lewandowski, Jan Marcinkowski
    Konferencja:
    IPCO 2019 (rok: 2019, ), Wydawca: Springer
    Data:
    konferencja 22-24.05.2019
    Status:
    Opublikowana
  6. New approximation algorithms for (1,2)-TSP
    Autorzy:
    Anna Adamaszek, Matthias Mnich, Katarzyna E. Paluch
    Konferencja:
    ICALP 2018 (rok: 2018, ), Wydawca: DROPS
    Data:
    konferencja 9-13.07.2018
    Status:
    Opublikowana
  7. An Algorithm for the Maximum Weight Strongly Stable Matching Problem
    Autorzy:
    Adam Kunysz
    Konferencja:
    ISAAC 2018 (rok: 2018, ), Wydawca: DROPS
    Data:
    konferencja 16-19.12.2018
    Status:
    Opublikowana
  8. The Strongly Stable Roommates Problem
    Autorzy:
    Adam Kunysz
    Konferencja:
    European Symposium on Algorithms: ESA 2016 (rok: 2016, ), Wydawca: DROPS
    Data:
    konferencja 22-24.08.2016
    Status:
    Opublikowana
  9. Optimal General Matchings
    Autorzy:
    Szymon Dudycz and Katarzyna Paluch
    Konferencja:
    WG 2018 (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 27-29.06.2018
    Status:
    Opublikowana