Approximation Algorithms for the Class Cover Problem Adam Cannon and Lenore Cowen Department of Mathematical Sciences Johns Hopkins University Baltimore, MD 21218

First Page		Document Content
Date: 2012-10-31 09:54:20 Computational complexity theory Mathematics Theory of computation NP-complete problems Operations research Set cover problem Approximation algorithm Facility location problem Dominating set Combinatorial optimization Reduction Algorithm		Approximation Algorithms for the Class Cover Problem Adam Cannon and Lenore Cowen Department of Mathematical Sciences Johns Hopkins University Baltimore, MD 21218 Add to Reading List Source URL: www.cs.tufts.edu Download Document from Source Website File Size: 187,22 KB Share Document on Facebook

	Approximation algorithms An algorithm has approximation ratio r if it outputs solutions with cost such that c/c* ≤ r and c/c ≤ r where c is the optimal cost. DocID: 1vcdB - View Document
	A Quadratically Convergent Algorithm for Structured Low-Rank Approximation ´ Eric Schost1 and Pierre-Jean Spaenlehauer2 1 DocID: 1uPNr - View Document
	A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem (Extended Abstract) Ola Svensson* Jakub Tarnawski† DocID: 1ut6L - View Document
	Approximating the Diameter of Planar Graphs in Near Linear Time OREN WEIMANN and RAPHAEL YUSTER, University of Haifa We present a (1 + ε)-approximation algorithm running in O( f (ε) · n log4 n) time for finding the di DocID: 1usZh - View Document
	A 1.8 Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2 GUY EVEN Tel-Aviv University JON FELDMAN Google, NY DocID: 1u559 - View Document