Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Application of modern algorithmic methods for solving NP-hard clustering problems.

2015/17/N/ST6/03684

Keywords:

algorithms approximation fixed-parameter tractable clustering computational complexity

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST6_7: Artificial intelligence, intelligent systems, multi-agent systems
  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms

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):

Krzysztof Sornat 

Number of co-investigators in the project: 2

Call: PRELUDIUM 9 - announced on 2015-03-16

Amount awarded: 150 000 PLN

Project start date (Y-m-d): 2016-03-11

Project end date (Y-m-d): 2019-03-10

Project duration:: 36 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.

Equipment purchased [PL]

  1. Notebook (6 000 PLN)

Information in the final report

  • Publication in academic press/journals (2)
  • Articles in post-conference publications (6)
  1. Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results
    Authors:
    Georgios Amanatidis, Peter Fulla, Evangelos Markakis, Krzysztof Sornat
    Academic press:
    Algorithmica , Wydawca: Springer
    Status:
    Submitted
    DOI:
    brak - link to the publication
  2. Approximation and Parameterized Complexity of Minimax Approval Voting
    Authors:
    Marek Cygan, Łukasz Kowalik, Arkadiusz Socała, Krzysztof Sornat
    Academic press:
    Journal of Artificial Intelligence Research (rok: 2018, tom: 63, strony: 495-513), Wydawca: AAAI Press
    Status:
    Published
    DOI:
    10.1613/jair.1.11253 - link to the publication
  1. Constant-Factor Approximation for Ordered k-Median
    Authors:
    Jarosław Byrka, Krzysztof Sornat, Joachim Spoerhase
    Conference:
    The 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018 (rok: 2018, ), Wydawca: ACM
    Data:
    konferencja 25-29 czerwca
    Status:
    Published
  2. Approximation and Parameterized Complexity of Minimax Approval Voting
    Authors:
    Marek Cygan, Łukasz Kowalik, Arkadiusz Socała, Krzysztof Sornat
    Conference:
    The 31st AAAI Conference on Artificial Intelligence, AAAI 2017 (rok: 2017, ), Wydawca: AAAI Press
    Data:
    konferencja 4-9 lutego
    Status:
    Published
    DOI:
    link to the publication
  3. Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results
    Authors:
    Georgios Amanatidis, Evangelos Markakis, Krzysztof Sornat
    Conference:
    41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 22-26 sierpnia
    Status:
    Published
    DOI:
    link to the publication
  4. On the Cycle Augmentation Problem: Hardness and Approximation Algorithms
    Authors:
    Waldo Galvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Krzysztof Sornat
    Conference:
    The 27th Annual European Symposium on Algorithms, ESA 2019 (rok: 2019, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-11 września
    Status:
    Submitted
  5. Proportional Approval Voting, Harmonic k-Median, and Negative Association
    Authors:
    Jarosław Byrka, Piotr Skowron, Krzysztof Sornat
    Conference:
    The 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 (rok: 2018, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-13 lipca
    Status:
    Published
    DOI:
    link to the publication
  6. Approximation and Hardness of Shift-Bribery
    Authors:
    Piotr Faliszewski, Pasin Manurangsi, Krzysztof Sornat
    Conference:
    The 33rd AAAI Conference on Artificial Intelligence, AAAI 2019 (rok: 2019, ), Wydawca: AAAI Press
    Data:
    konferencja 27 stycznia - 1 lutego
    Status:
    Accepted for publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy