Zobrazeno 1 - 10
of 58
pro vyhledávání: '"Scheder, Dominik"'
Autor:
Scheder, Dominik
Publikováno v:
TheoretiCS, Volume 3 (March 13, 2024) theoretics:9832
PPSZ, for long time the fastest known algorithm for $k$-SAT, works by going through the variables of the input formula in random order; each variable is then set randomly to $0$ or $1$, unless the correct value can be inferred by an efficiently imple
Externí odkaz:
http://arxiv.org/abs/2207.11071
Autor:
Li, Shibo, Scheder, Dominik
PPSZ is the fastest known algorithm for (d,k)-CSP problems, for most values of d and k. It goes through the variables in random order and sets each variable randomly to one of the d colors, excluding those colors that can be ruled out by looking at f
Externí odkaz:
http://arxiv.org/abs/2109.02795
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.
Autor:
Scheder, Dominik, Steinberger, John
Publikováno v:
Computational Complexity; Dec2024, Vol. 33 Issue 2, p1-48, 48p
We construct uniquely satisfiable $k$-CNF formulas that are hard for the algorithm PPSZ. Firstly, we construct graph-instances on which "weak PPSZ" has savings of at most $(2 + \epsilon) / k$; the saving of an algorithm on an input formula with $n$ v
Externí odkaz:
http://arxiv.org/abs/1611.01291
Autor:
Scheder, Dominik Alban.
Publikováno v:
Connect to online resource.
Thesis (M.S.)--University of Colorado at Boulder, 2005.
Source: Masters Abstracts International, Volume: 43-05, page: 1755. Director: Harold N. Gabow.
Source: Masters Abstracts International, Volume: 43-05, page: 1755. Director: Harold N. Gabow.
Externí odkaz:
http://wwwlib.umi.com/cr/colorado/fullcit?p1425760
Autor:
Gravin, Nick, Scheder, Dominik
Our work is devoted to the metric facility location problem and addresses the selfish behavior of the players. It contributes to the line of work initiated by Procaccia and Tennenholtz [EC09] on approximate mechanism design without money. We explore
Externí odkaz:
http://arxiv.org/abs/1202.1231
Let F be a CNF formula with n variables and m clauses. F is 3-satisfiable if for any 3 clauses in F, there is a truth assignment which satisfies all of them. Lieberherr and Specker (1982) and, later, Yannakakis (1994) proved that in each 3-satisfiabl
Externí odkaz:
http://arxiv.org/abs/1104.2818
Autor:
Scheder, Dominik
We analyze the so-called ppz algorithm for (d,k)-CSP problems for general values of d (number of values a variable can take) and k (number of literals per constraint). To analyze its success probability, we prove a correlation inequality for submodul
Externí odkaz:
http://arxiv.org/abs/1010.5717
A critical variable of a satisfiable CNF formula is a variable that has the same value in all satisfying assignments. Using a simple case distinction on the fraction of critical variables of a CNF formula, we improve the running time for 3-SAT from O
Externí odkaz:
http://arxiv.org/abs/1009.4830