12 citations · 31 across the 12 of their papers we have counts for
14 papers
PPSZ is better than you think
Dominik Scheder
PPSZ, for long time the fastest known algorithm for -SAT, works by going through the variables of the input formula in random order; each variable is then set randomly to or…
Impatient PPSZ -- a Faster algorithm for CSP
Shibo Li, Dominik Scheder
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…
Tighter Hard Instances for PPSZ
Pavel Pudlák, Dominik Scheder, Navid Talebanfard
We construct uniquely satisfiable -CNF formulas that are hard for the algorithm PPSZ. Firstly, we construct graph-instances on which "weak PPSZ" has savings of at most $(2 + ε)…
In Defense of Bureaucracy in the Metric Facility Location Problem
Nick Gravin, Dominik Scheder
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 Tennenh…
A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application
Gregory Gutin, Mark Jones, Dominik Scheder +1
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…
PPZ For More Than Two Truth Values - An Algorithm for Constraint Satisfaction Problems
Dominik Scheder
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 i…