Set Partitioning via Inclusion-Exclusion

By Andreas Björklund, Thore Husfeldt, Mikko Koivisto. SIAM journal on computing (Print), 2009

423 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Non-uniform ACC Circuit Lower Bounds (2011, background): “Another somewhat small class known to not have unrestricted polynomial size circuits is MAEXP [Buhrman et al. 1998]. Later it was shown that the MAEXP lower bound can be improved to half-exponential size functions f which satisfy f(f(n)) ≥ 2 [Miltersen et al. 1999]. Kabanets and Impagliazzo [2004] p”
Lower bounds based on the Exponential Time Hypothesis (2011, neutral): “A variant of ETH, called the Strong Exponential Time Hypothesis (SETH) can be used to give even more refined lower bounds saying, e.g., that a parameterized problem cannot be solved in time (2 ")knO(1) for any " > 1.”
Collective spatial keyword querying (2011, methodology): “[3] propose an exact algorithm for the unweighted set cover problem using the inclusion-exclusion principle, which is not directly applicable to the WSC problem.”