4 citations · 7 across the 8 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2019
Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm
Gabriel Istrate, Cosmin Bonchis, Mircea Marin
We analyze the expected running time of WalkSAT, a well-known local search procedure for satisfiability solving, on satisfiable instances of the k-XOR SAT problem. We obtain estima…
cs.DS2012
Improved approximation algorithms for low-density instances of the Minimum Entropy Set Cover Problem
Cosmin Bonchis, Gabriel Istrate
We study the approximability of instances of the minimum entropy set cover problem, parameterized by the average frequency of a random element in the covering sets. We analyze an a…