Kombinatoriikka Graph Pakkaukset ja Online Binary Search Trees

Projektin yksityiskohdat

Tiivistelmä

Reaalimaailman optimointiongelmat tuottavat useita haasteita algoritmitutkimukselle. Esimerkiksi (i) monien tärkeiden ongelmien uskotaan olevan laskennallisesti työläitä ja (ii) data-aineistojen koon kasvaessa modernit sovellukset vaativat usein päätöksentekoa epätäydellisiä ja dynaamisesti muuttuvien lähtötietojen perusteella. Useiden vuosikymmenten tutkimuksen jälkeenkin monet alueen perustavimmista ongelmista ovat huonosti ymmärrettyjä. Olemassa olevat algoritmitekniikat joko ovat saavuttaneet suorituskykynsä rajat tai ne on räätälöity toimimaan hyvin suppeissa erityistapauksissa. Tämä projekti pyrkii selventämään tutkimuksen nykytilaa ja tuomaan yhteen algoritmitutkimuksen eri osa-alueita kuten approksimointialgoritmeja, online-algoritmeja, kiintoparametrialgoritmeja, matala-asteisia eksponenttiaikaisia algoritmeja ja tehokkaita tietorakenteita. Keskitymme pitkäaikaisiin avoimiin ongelmiin, jotka tuovat yhteen tutkimushaasteita monilta suunnilta.
LyhytotsikkoChalermsook Parinya AT-palkka
TilaPäättynyt
Todellinen alku/loppupvm01/09/2017 → 31/08/2022

Yhteistyöpartnerit

Sormenjälki

Tutustu tutkimuksen aiheisiin, joita tämä projekti koskee. Nämä merkinnät luodaan taustalla olevien stipendien/apurahojen perusteella. Yhdessä ne muodostavat ainutlaatuisen sormenjäljen.
Näytä koko sormenjälki
  • 2 Conference contribution

  • Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

    Chalermsook, P., Huang, C. C., Nanongkai, D., Saranurak, T., Sukprasert, P. & Yingchareonthawornchai, S., 1 heinäk. 2022, 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022. Bojanczyk, M., Merelli, E. & Woodruff, D. P. (toim.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, s. 1-20 20 Sivumäärä 37. (Leibniz International Proceedings in Informatics, LIPIcs; Vuosikerta 229).

    Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

    Open access
    Tiedosto
    1 Sitaatiot (Scopus)
    10 Lataukset (Pure)

  • Vertex sparsification for edge connectivity

    Chalermsook, P., Das, S., Kook, Y., Laekhanukit, B., Liu, Y. P., Peng, R., Sellke, M. & Vaz, D., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (toim.). ACM, s. 1206-1225 20 Sivumäärä (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

    Open access
    12 Sitaatiot (Scopus)