Zobrazeno 1 - 3
of 3
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