Zobrazeno 1 - 6
of 6
pro vyhledávání: '"Balázs F. Mezei"'
Publikováno v:
SIAM Journal on Discrete Mathematics. 36:1306-1342
The Ising antiferromagnet is an important statistical physics model with close connections to the {\sc Max Cut} problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry brea
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1335076b7e66654def5b5b0bf155a92d
https://doi.org/10.1137/20m137999x
https://doi.org/10.1137/20m137999x
Publikováno v:
LICS
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Logic in Computer Science
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Logic in Computer Science
We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes. Baker's approach gives a PTAS on planar graphs, excluded-minor classe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5d49dd27463fb6719fb7a53e478c7dce
https://doi.org/10.1145/3569956
https://doi.org/10.1145/3569956
Publikováno v:
Random Structures & Algorithms. 57:1205-1247
Consider a complete graph $K_n$ with edge weights drawn independently from a uniform distribution $U(0,1)$. The weight of the shortest (minimum-weight) path $P_1$ between two given vertices is known to be $\ln n / n$, asymptotically. Define a second-
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b234968e274a919738972fb98dccfe55
https://doi.org/10.1002/rsa.20962
https://doi.org/10.1002/rsa.20962
Autor:
ROMERO, MIGUEL1 mgromero@uc.cl, WROCHNA, MARCIN2 m.wrochna@mimuw.edu.pl, ŽIVNÝ, STANISLAV3 standa.zivny@cs.ox.ac.uk
Publikováno v:
Journal of the ACM. Dec2023, Vol. 70 Issue 6, p1-43. 43p.
Publikováno v:
ACM Transactions on Algorithms; Apr2023, Vol. 19 Issue 2, p1-31, 31p
Publikováno v:
Random Structures & Algorithms; Dec2020, Vol. 57 Issue 4, p1205-1247, 43p