Zobrazeno 1 - 10
of 272
pro vyhledávání: '"Unique games conjecture"'
Publikováno v:
FOCS
We prove that pseudorandom sets in the Grassmann graph have near-perfect expansion. This completes the last missing piece of the proof of the 2-to-2-Games Conjecture (albeit with imperfect completeness). The Grassmann graph has induced subgraphs that
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::17783c10b29ccdb0d210e3946e6e7d5e
https://doi.org/10.4007/annals.2023.198.1.1
https://doi.org/10.4007/annals.2023.198.1.1
Autor:
Stankovic, Aleksa
This thesis studies how the approximability of some fundamental computational problems is affected by some additional requirements on the structure of the inputs. The problems studied in this thesis belong or are closely related to constraint satisfa
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=od_______260::41508a1d1cd800af63007763fa1630d4
http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-326609
http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-326609
Publikováno v:
Mathematical Programming. 195:243-281
Semidefinite programming (SDP) with diagonal constraints arise in many optimization problems, such as Max-Cut, community detection and group synchronization. Although SDPs can be solved to arbitrary precision in polynomial time, generic convex solver
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7f11ca875daaddbfd1fc8fc2d803460c
https://doi.org/10.1007/s10107-021-01686-3
https://doi.org/10.1007/s10107-021-01686-3
Autor:
Saket Saurabh, Pranabendu Misra, Joydeep Mukherjee, Geevarghese Philip, Daniel Lokshtanov, Fahad Panolan
Publikováno v:
ACM Transactions on Algorithms. 17:1-14
A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T − S is acyclic. We consider the Feedback Vertex Set problem in tournaments. Here, the input is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2d09687e1443a359296656bd3a8fedc1
https://doi.org/10.1145/3446969
https://doi.org/10.1145/3446969
Publikováno v:
Theoretical Computer Science. 845:136-143
For a given b ∈ N n and a hypergraph H = ( V , E ) with maximum degree Δ, the b-set multicover problem which we are concerned with in this paper may be stated as follows: find a minimum cardinality subset C ⊆ E such that no vertex v i ∈ V is c
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::06ee9dd4b6875c69a024fffc7c01f477
https://doi.org/10.1016/j.tcs.2020.09.009
https://doi.org/10.1016/j.tcs.2020.09.009
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
Theory of Computing. 16:1-30
We continue the study of covering complexity of constraint satisfaction problems (CSPs) initiated by Guruswami, Hastad and Sudan [SIAM J. Computing, 31(6):1663--1686, 2002] and Dinur and Kol [In Proc. $28$th IEEE Conference on Computational Complexit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9103d2cfb2ac3058a0fb3f78a2ac10ed
https://doi.org/10.4086/toc.2020.v016a016
https://doi.org/10.4086/toc.2020.v016a016
Autor:
Stanković, Aleksa
We study the Minimum Sum Vertex Cover problem, which asks for an ordering of vertices in a graph that minimizes the total cover time of edges. In particular, n vertices of the graph are visited according to an ordering, and for each edge this induces
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0fdc933c921ae7e833b889298e670053
Autor:
Eldan, Ronen, Moshkovitz, Dana
We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap 1-�� vs. 1-C��, for any C > 1, and sufficiently small �� > 0) to the problem of proving a PCP Theorem for a certain non-unique game. In a previous work, Khot a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::999d5f38a26021a3881e429d23888112
Publikováno v:
Mathematical Programming. 184:411-443
We investigate the approximability of the linear 3-cut problem in directed graphs. The input here is a directed graph $$D=(V,E)$$ with node weights and three specified terminal nodes $$s,r,t\in V$$ , and the goal is to find a minimum weight subset of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::299b7e99512eb43ddf71ee18908a113f
https://doi.org/10.1007/s10107-019-01417-9
https://doi.org/10.1007/s10107-019-01417-9