Approximating Independent Set in Semi-Random Graphs Bodo Manthey a Kai Plociennik b a University of Twente, Department of Applied Mathematics

First Page		Document Content
Date: 2011-08-28 15:19:04 NP-complete problems Analysis of algorithms Approximation algorithms Time complexity Independent set Ε-net Property testing Theoretical computer science Mathematics Computational complexity theory		Approximating Independent Set in Semi-Random Graphs Bodo Manthey a Kai Plociennik b a University of Twente, Department of Applied Mathematics Add to Reading List Source URL: doc.utwente.nl Download Document from Source Website File Size: 242,73 KB Share Document on Facebook

	Range Counting Coresets for Uncertain Data ∗ Amirali Abdullah, Samira Daruki, and Jeff M. Phillips School of Computing, University of Utah DocID: 1gdXC - View Document
	A Note about Weak ε-nets for Axis-Parallel Boxes in d-space∗ Esther Ezra† Abstract We show the existence of weak ε-nets of size O (1/ε log log (1/ε)) for point sets and axisparallel boxes in Rd , for d ≥ 4. Our DocID: 1gbOJ - View Document
	Improved Bound for the Union of Fat Triangles∗ Esther Ezra† Boris Aronov‡ Abstract DocID: 1gbka - View Document
	ε-Samples for Kernels Jeff M. Phillips University of Utah April 3, 2012 DocID: 1g3fG - View Document
	A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension∗ Esther Ezra† Abstract Let (X, S) be a set system on an n-point set X. The discrepancy of S is defined as the minimum of the DocID: 1fQIz - View Document