Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Programowanie dynamiczne z gwarancjami

2018/28/T/ST6/00084

Keywords:

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • 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 Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Other projects carried out by the institution 

Principal investigator (from the host institution):

Karol Węgrzycki 

Number of co-investigators in the project: 2

Call: ETIUDA 6 - announced on 2017-12-15

Amount awarded: 113 322 PLN

Project start date (Y-m-d): 2018-10-01

Project end date (Y-m-d): 2019-09-30

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

Information in the final report

  • Articles in post-conference publications (5)
  1. Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max
    Authors:
    Karl Bringmann, Marvin Künnemann, Karol Węgrzycki
    Conference:
    STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computin (rok: 2019, ), Wydawca: ACM
    Data:
    konferencja 23-26.06.2019
    Status:
    Published
  2. A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
    Authors:
    Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis and Karol Węgrzycki
    Conference:
    Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) (rok: 2021, ), Wydawca: SIAM
    Data:
    konferencja 10-13.01.2021
    Status:
    Published
    DOI:
    link to the publication
  3. Equal-Subset-Sum Faster Than the Meet-in-the-Middle
    Authors:
    Mucha, Marcin ; Nederlof, Jesper ; Pawlewicz, Jakub ; Wegrzycki, Karol
    Conference:
    27th Annual European Symposium on Algorithms (ESA 2019) (rok: 2019, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-11.09.2019
    Status:
    Published
    DOI:
    link to the publication
  4. Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors
    Authors:
    Jesper Nederlof, Karol Węgrzycki
    Conference:
    STOC 2021: 53rd Annual ACM Symposium on Theory of Computing (rok: 2021, ), Wydawca: ACM
    Data:
    konferencja 21-25.06.2021
    Status:
    Published
  5. Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
    Authors:
    Jesper Nederlof, Michal Pilipczuk, Celine M. F. Swennenhuis, Karol Wegrzycki
    Conference:
    Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020 (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 24-26.06.2020
    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