Approximability and inapproximability of fundamental problems
Tid: Fr 2025-09-12 kl 15.15
Plats: D3, Lindstedtvägen 5
Språk: Engelska
Ämnesområde: Matematik
Licentiand: Björn Martinsson , Algebra, kombinatorik och topologi
Granskare: Assistant Professor Jakub Opršal, University of Birmingham
Huvudhandledare: Johan Håstad, Matematik (Avd.); Per Austrin, Teoretisk datalogi, TCS
QC 2025-08-21
Abstract
Denna avhandling innehåller tre artiklar om approximationsalgoritmer och resultat om icke-approximabilitet. Artikel A innehåller NP-svårhetsresultat om icke-approximabilitet för Max-2Lin(2), där 2Lin(2) syftar på ett linjärt ekvationssystem modulo 2 med två variabler per ekvation. Artikel B innehåller en approximationsalgoritm för linjärt ordnad hypergraf-färgning. Rekordet innan Artikel B var en approximationsalgoritm som klarade av att färlägga en $2$-färgbar $3$-uniform hypergraf med $n$ noder med $O(\sqrt[5]n)$ färger. Men vår approximationsalgoritm använder endast $\log_2(n)$ färger, vilket slår $n^{O(1)}$-barriären. Artikel C introducerar två helt nya begrepp, kallade ``promise useful'' och ``promise useless'', för så kallade Promise Constraint Satisfaction Problems (PCSPer). Artikeln innehåller också en undersökning över viktiga resultat relaterade till dessa två begrepp. Förhoppningen är att begreppen kommer att leda till nya forskningsinriktningar för PCSPer.