4 citations · 9 across the 13 of their papers we have counts for
Showing cs.DSShow all
3 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.DS2014★ 1 cited
Minimum Entropy Submodular Optimization (and Fairness in Cooperative Games)
Cosmin Bonchiş, Gabriel Istrate
We study minimum entropy submodular optimization, a common generalization of the minimum entropy set cover problem, studied earlier by Cardinal et al., and the submodular set cover…
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…