Search results for "Set Cover"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
4	Petr Slavík	A Tight Analysis of the Greedy Algorithm for Set Cover.	STOC	1996	DBLP DOI BibTeX RDF	fractional set cover, partial set cover, approximation algorithms, greedy algorithm, set cover
4	Bonnie Berger, John Rompel, Peter W. Shor	Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry	FOCS	1989	DBLP DOI BibTeX RDF	unweighted set cover problems, efficient NC algorithms, NC approximation algorithms, weighted set cover problems, set cover algorithm, finite union, finite intersection, finite VC dimension, NC hypothesis finder, linear-processor NC algorithm, computational geometry, learning theory, closure, concept class
3	Matti Åstrand, Jukka Suomela	Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks.	SPAA	2010	DBLP DOI BibTeX RDF	edge packing, distributed algorithm, local algorithm, set cover, vertex cover, anonymous network
3	Kasturi Varadarajan	Weighted geometric set cover via quasi-uniform sampling.	STOC	2010	DBLP DOI BibTeX RDF	approximation, set cover, epsilon nets
3	Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis	Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Approximation algorithms, Combinatorial optimization, Set cover
3	Yossi Azar, Iftah Gamzu, Xiaoxin Yin	Multiple intents re-ranking.	STOC	2009	DBLP DOI BibTeX RDF	min-sum set cover, minimum latency set cover, multiple intents, approximation algorithms, ranking
3	Jean Cardinal, Samuel Fiorini, Gwenaël Joret	Tight Results on Minimum Entropy Set Cover.	Algorithmica	2008	DBLP DOI BibTeX RDF	Entropy, Greedy algorithm, Hardness of approximation, Set cover
3	Tianping Shuai, Xiao-Dong Hu	Connected Set Cover Problem and Its Applications.	AAIM	2006	DBLP DOI BibTeX RDF	Approximation algorithm, Set cover, Wavelength assignment, Performance ratio
3	Refael Hassin, Asaf Levin	An Approximation Algorithm for the Minimum Latency Set Cover Problem.	ESA	2005	DBLP DOI BibTeX RDF	Minimum sum set cover, minimum latency, approximation algorithm
3	Kenneth L. Clarkson, Kasturi R. Varadarajan	Improved approximation algorithms for geometric set cover.	Symposium on Computational Geometry	2005	DBLP DOI BibTeX RDF	algorithms, approximation, set cover
3	Noga Alon, Yossi Azar, Shai Gutner	Admission control to minimize rejections and online set cover with repetitions.	SPAA	2005	DBLP DOI BibTeX RDF	admission control, competitive, set cover, on-line
3	Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram	Universal approximations for TSP, Steiner tree, and set cover.	STOC	2005	DBLP DOI BibTeX RDF	sparse partition, approximation algorithms, TSP, Steiner tree, set cover, universal approximation
3	Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor	The online set cover problem.	STOC	2003	DBLP DOI BibTeX RDF	competitive analysis, on-line algorithms, set-cover, derandomization, randomized rounding
3	Uriel Feige	A Threshold of ln n for Approximating Set Cover.	J. ACM	1998	DBLP DOI BibTeX RDF	set cover, approximation ratio
2	Chandra Chekuri, Kenneth L. Clarkson, Sariel Har-Peled	On the set multi-cover problem in geometric settings.	Symposium on Computational Geometry	2009	DBLP DOI BibTeX RDF	set cover, cuttings, LP rounding
2	Marcelo C. Couto, Pedro Jussieu de Rezende, Cid C. de Souza	An IP solution to the art gallery problem.	Symposium on Computational Geometry	2009	DBLP DOI BibTeX RDF	integer programming, visibility, set cover, art gallery
2	Kasturi R. Varadarajan	Epsilon nets and union complexity.	Symposium on Computational Geometry	2009	DBLP DOI BibTeX RDF	approximation algorithms, set cover, epsilon nets
2	Ruoming Jin, Yang Xiang, Lin Liu	Cartesian contour: a concise representation for a collection of frequent sets.	KDD	2009	DBLP DOI BibTeX RDF	concise pattern representation, frequent itemsets, set cover, cartesian product
2	Boris Aronov, Esther Ezra, Micha Sharir	Small-size epsilon-nets for axis-parallel rectangles and boxes.	STOC	2009	DBLP DOI BibTeX RDF	?-nets, geometric range spaces, randomized algorithms, set cover, hitting set
2	Yuichi Yoshida, Masaki Yamamoto, Hiro Ito	An improved constant-time approximation algorithm for maximum~matchings.	STOC	2009	DBLP DOI BibTeX RDF	constant-time approximation algorithms, minimum vertex cover, property testing, maximum matching, minimum set cover
2	Zhao Zhang, Xiaofeng Gao, Xuefei Zhang, Weili Wu, Hui Xiong	Three Approximation Algorithms for Energy-Efficient Query Dissemination in Sensor Database System.	DEXA	2009	DBLP DOI BibTeX RDF	Fault Tolerance, Set Cover, Sensor Database
2	K. Selçuk Candan, Huiping Cao, Yan Qi 0002, Maria Luisa Sapino	Table summarization with the help of domain lattices.	CIKM	2008	DBLP DOI BibTeX RDF	ranked set cover, table summarization, value clustering lattice
2	Francesco Bonchi, Carlos Castillo, Debora Donato, Aristides Gionis	Topical query decomposition.	KDD	2008	DBLP DOI BibTeX RDF	query recommendation, clustering, set cover
2	Andreas Björklund, Thore Husfeldt	Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings.	Algorithmica	2008	DBLP DOI BibTeX RDF	Exact satisfability, Number of perfect matchings, Set cover, Exact algorithms, Set partition
2	Kenneth L. Clarkson, Kasturi R. Varadarajan	Improved Approximation Algorithms for Geometric Set Cover.	Discrete & Computational Geometry	2007	DBLP DOI BibTeX RDF
2	Chengbang Huang, Faruck Morcos, Simon P. Kanaan, Stefan Wuchty, Danny Z. Chen, Jesús A. Izaguirre	Predicting Protein-Protein Interactions from Protein Domains Using a Set Cover Approach.	IEEE/ACM Trans. Comput. Biology Bioinform.	2007	DBLP DOI BibTeX RDF	graph algorithms, genetics, biology, bioinformatics (genome or protein) databases, Computations on discrete structures
2	Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis	Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs.	FCT	2007	DBLP DOI BibTeX RDF
2	Peng Cui	A Tighter Analysis of Set Cover Greedy Algorithm for Test Set.	ESCAPE	2007	DBLP DOI BibTeX RDF
2	Dorit S. Hochbaum, Asaf Levin	Covering the Edges of Bipartite Graphs Using K 2, 2 Graphs.	WAOA	2007	DBLP DOI BibTeX RDF	Approximation algorithms, network design, set cover
2	Asaf Levin	Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search.	WAOA	2006	DBLP DOI BibTeX RDF
2	Jean Cardinal, Samuel Fiorini, Gwenaël Joret	Tight Results on Minimum Entropy Set Cover.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
2	Noga Alon, Dana Moshkovitz, Shmuel Safra	Algorithmic construction of sets for k-restrictions.	ACM Transactions on Algorithms	2006	DBLP DOI BibTeX RDF	k-restriction, almost k-wise independence, generalized hashing, splitter, Set-Cover, Derandomization, group testing
2	Alexandre H. L. Porto, Valmir C. Barbosa	A Methodology for Determining Amino-Acid Substitution Matrices from Set Covers.	EvoWorkshops	2006	DBLP DOI BibTeX RDF	Substitution matrix, Residue set cover, Sequence alignment
2	Zheng Sun, Xiang-Yang Li, Weizhao Wang, Xiaowen Chu	Mechanism Design for Set Cover Games When Elements Are Agents.	AAIM	2005	DBLP DOI BibTeX RDF
2	Xiang-Yang Li, Zheng Sun, Weizhao Wang	Cost Sharing and Strategyproof Mechanisms for Set Cover Games.	STACS	2005	DBLP DOI BibTeX RDF
2	Kamesh Munagala, Shivnath Babu, Rajeev Motwani, Jennifer Widom	The Pipelined Set Cover Problem.	ICDT	2005	DBLP DOI BibTeX RDF
2	Fabian Kuhn, Pascal von Rickenbach, Roger Wattenhofer, Emo Welzl, Aaron Zollinger	Interference in Cellular Networks: The Minimum Membership Set Cover Problem.	COCOON	2005	DBLP DOI BibTeX RDF
2	Cristina Bazgan, Jérôme Monnot, Vangelis Th. Paschos, Fabrice Serrière	Greedy Differential Approximations for Min Set Cover.	SOFSEM	2005	DBLP DOI BibTeX RDF
2	Refael Hassin, Danny Segev	The Set Cover with Pairs Problem.	FSTTCS	2005	DBLP DOI BibTeX RDF
2	Toshihiro Fujito	On Combinatorial Approximation of Covering 0-1 Integer Programs and Partial Set Cover.	J. Comb. Optim.	2004	DBLP DOI BibTeX RDF	covering integer program, approximation algorithm, combinatorial optimization, partial cover
2	Uriel Feige, László Lovász, Prasad Tetali	Approximating Min Sum Set Cover.	Algorithmica	2004	DBLP DOI BibTeX RDF	Threshhold, NP-hardness, Greedy algorithm, Randomized rounding
2	Spyros Angelopoulos, Allan Borodin	The Power of Priority Algorithms for Facility Location and Set Cover.	Algorithmica	2004	DBLP DOI BibTeX RDF	Approximation lower bounds, Greedy algorithms
2	Stefan Porschen	On the Time Complexity of Rectangular Covering Problems in the Discrete Plane.	ICCSA	2004	DBLP DOI BibTeX RDF	rectangular set cover, integer lattice, NP-completeness, discrete plane
2	Nikhil R. Devanur, Milena Mihail, Vijay V. Vazirani	Strategyproof cost-sharing mechanisms for set cover and facility location games.	ACM Conference on Electronic Commerce	2003	DBLP DOI BibTeX RDF	mechanism design, facility location, set cover, cost sharing
2	Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan	An Improved Approximation Algorithm for Vertex Cover with Hard Capacities.	ICALP	2003	DBLP DOI BibTeX RDF	capacitated covering, Approximation algorithms, linear programming, set cover, vertex cover, randomized rounding
2	Spyros Angelopoulos, Allan Borodin	On the Power of Priority Algorithms for Facility Location and Set Cover.	APPROX	2002	DBLP DOI BibTeX RDF
2	Uriel Feige, László Lovász, Prasad Tetali	Approximating Min-sum Set Cover.	APPROX	2002	DBLP DOI BibTeX RDF
2	Toshihiro Fujito, Tsuyoshi Okumura	A Modified Greedy Algorithm for the Set Cover Problem with Weights 1 and 2.	ISAAC	2001	DBLP DOI BibTeX RDF
2	Rajiv Gandhi, Samir Khuller, Aravind Srinivasan	Approximation Algorithms for Partial Covering Problems.	ICALP	2001	DBLP DOI BibTeX RDF	Approximation algorithms, set cover, vertex cover, randomized rounding, primal-dual methods, partial covering
2	David Peleg	Approximation Algorithms for the Label-CoverMAX and Red-Blue Set Cover Problems.	SWAT	2000	DBLP DOI BibTeX RDF
2	Reuven Bar-Yehuda	One for the Price of Two: a Unified Approach for Approximating Covering Problems.	Algorithmica	2000	DBLP DOI BibTeX RDF	Generalized Steiner Forest, Randomized approximations, Approximation algorithm, Set Cover, Vertex Cover, Covering problems, Primal-dual, Local ratio, Feedback Vertex Set
2	Reuven Bar-Yehuda	One for the Price of Two: A Unified Approach for Approximating Covering Problems.	APPROX	1998	DBLP DOI BibTeX RDF	Generalized Steiner Forest, Randomized Approximations, Approximation Algorithm, Set Cover, Vertex Cover, Covering Problems, Local Ratio, Feedback Vertex Set
2	Alexander Wolff	The Hardness of Approximating Set Cover.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
2	Erez Buchnik, Shmuel Ur	Compacting regression-suites on-the-fly.	APSEC	1997	DBLP DOI BibTeX RDF	regression suite compaction algorithm, regression suite size minimization, online set-cover, intermediate set size, software testing, coverage, program testing, bugs, computational resources, solution quality
2	Magnús M. Halldórsson	Approximating k-Set Cover and Complementary Graph Coloring.	IPCO	1996	DBLP DOI BibTeX RDF
2	Sridhar Rajagopalan, Vijay V. Vazirani	Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs	FOCS	1993	DBLP DOI BibTeX RDF	randomized voting, primal-dual RNC approximation algorithms, covering integer programs, classical greedy sequential set cover algorithm, parallel approximation algorithms, randomization, set cover problem
2	Vangelis Th. Paschos	A Theorem on the Approximation of Set Cover and Vertex Cover.	FSTTCS	1991	DBLP DOI BibTeX RDF
1	Luciana Brugiolo Gonçalves, Simone de Lima Martins, Luiz Satoru Ochi, Anand Subramanian	Exact and heuristic approaches for the set cover with pairs problem.	Optimization Letters	2012	DBLP DOI BibTeX RDF
1	Sandeep Sen, V. N. Muralidhara	The covert set-cover problem with application to Network Discovery	CoRR	2012	DBLP BibTeX RDF
1	Eden Chlamtac, Zac Friggstad, Konstantinos Georgiou	Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods	CoRR	2012	DBLP BibTeX RDF
1	Yang Yu, Xin Yao, Zhi-Hua Zhou	On the approximation ability of evolutionary optimization with application to minimum set cover.	Artif. Intell.	2012	DBLP DOI BibTeX RDF
1	Valentin E. Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni	Approximation algorithms for a geometric set cover problem.	Discrete Applied Mathematics	2012	DBLP DOI BibTeX RDF
1	Timothy M. Chan, Elyot Grant, Jochen Könemann, Malcolm Sharpe	Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling.	SODA	2012	DBLP BibTeX RDF
1	Sungjin Im, Maxim Sviridenko, Ruben van der Zwaan	Preemptive and Non-Preemptive Generalized Min Sum Set Cover.	STACS	2012	DBLP DOI BibTeX RDF
1	Fen Liu, Gui Zhang	Analysis of Set-cover traitor tracing scheme.	CCNC	2012	DBLP DOI BibTeX RDF
1	Ankit Kagliwal, Shankar Balachandran	Set-Cover Heuristics for Two-Level Logic Minimization.	VLSI Design	2012	DBLP DOI BibTeX RDF
1	Martin Skutella, David P. Williamson	A note on the generalized min-sum set cover problem.	Oper. Res. Lett.	2011	DBLP DOI BibTeX RDF
1	Hiroki Morizumi	Improved approximation algorithms for minimum AND-circuits problem via k-set cover.	Inf. Process. Lett.	2011	DBLP DOI BibTeX RDF
1	Valentin E. Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni	On the Approximability of a Geometric Set Cover Problem.	Electronic Colloquium on Computational Complexity (ECCC)	2011	DBLP BibTeX RDF
1	Dana Moshkovitz	The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover.	Electronic Colloquium on Computational Complexity (ECCC)	2011	DBLP BibTeX RDF
1	Wei Ren, Qing Zhao	A note on 'Algorithms for connected set cover problem and fault-tolerant connected set cover problem'.	Theor. Comput. Sci.	2011	DBLP DOI BibTeX RDF
1	Asaf Levin, Uri Yovel	Uniform unweighted set cover: The power of non-oblivious local search.	Theor. Comput. Sci.	2011	DBLP DOI BibTeX RDF
1	Hao Chen	Restricted Parameter Range Promise Set Cover Problems Are Easy	CoRR	2011	DBLP BibTeX RDF
1	Martin Fürer, Huiwen Yu	Packing-Based Approximation Algorithm for the k-Set Cover Problem	CoRR	2011	DBLP BibTeX RDF
1	Wei Ren, Qing Zhao	A Note on: `Algorithms for Connected Set Cover Problem and Fault-Tolerant Connected Set Cover Problem'	CoRR	2011	DBLP BibTeX RDF
1	Martin Skutella, David P. Williamson	A note on the generalized min-sum set cover problem	CoRR	2011	DBLP BibTeX RDF
1	Hakob Aslanyan	Greedy Set Cover Estimations	CoRR	2011	DBLP BibTeX RDF
1	Elyot Grant, Timothy M. Chan	Exact Algorithms and APX-Hardness Results for Geometric Set Cover.	CCCG	2011	DBLP BibTeX RDF
1	Kashif Ali, Waleed Alsalih, Hossam S. Hassanein	Set-Cover Approximation Algorithms for Load-Aware Readers Placement in RFID Networks.	ICC	2011	DBLP DOI BibTeX RDF
1	Guy E. Blelloch, Richard Peng, Kanat Tangwongsan	Linear-work greedy parallel approximate set cover and variants.	SPAA	2011	DBLP DOI BibTeX RDF
1	Zheng Wu, Thomas H. Kunz, Margrit Betke	Efficient track linking methods for track graphs using network-flow and set-cover techniques.	CVPR	2011	DBLP DOI BibTeX RDF
1	Nikhil Bansal, Ravishankar Krishnaswamy, Barna Saha	On Capacitated Set Cover Problems.	APPROX-RANDOM	2011	DBLP DOI BibTeX RDF
1	Martin Fürer, Huiwen Yu	Packing-Based Approximation Algorithm for the k-Set Cover Problem.	ISAAC	2011	DBLP DOI BibTeX RDF
1	Andrew Guillory, Jeff A. Bilmes	Online Submodular Set Cover, Ranking, and Repeated Active Learning.	NIPS	2011	DBLP BibTeX RDF
1	Xiang-Yang Li, Zheng Sun, Weizhao Wang, Wei Lou	Cost sharing and strategyproof mechanisms for set cover games.	J. Comb. Optim.	2010	DBLP DOI BibTeX RDF
1	Xiang-Yang Li, Zheng Sun, Weizhao Wang, Xiaowen Chu, ShaoJie Tang, Ping Xu	Mechanism design for set cover games with selfish element agents.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	Misael Mongiovì, Raffaele Di Natale, Rosalba Giugno, Alfredo Pulvirenti, Alfredo Ferro, Roded Sharan	Sigma: a Set-Cover-Based Inexact Graph Matching Algorithm.	J. Bioinformatics and Computational Biology	2010	DBLP DOI BibTeX RDF
1	Andrew Guillory, Jeff A. Bilmes	Interactive Submodular Set Cover	CoRR	2010	DBLP BibTeX RDF
1	Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy	A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover.	SODA	2010	DBLP BibTeX RDF
1	Sandeep Sen, V. N. Muralidhara	The Covert Set-Cover Problem with Application to Network Discovery.	WALCOM	2010	DBLP DOI BibTeX RDF
1	Bruno Escoffier, Laurent Gourvès, Jérôme Monnot	On the Impact of Local Taxes in a Set Cover Game.	SIROCCO	2010	DBLP DOI BibTeX RDF
1	Andrew Guillory, Jeff Bilmes	Interactive Submodular Set Cover.	ICML	2010	DBLP BibTeX RDF
1	Piotr Berman, Marek Karpinski, Andrzej Lingas	Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems.	COCOON	2010	DBLP DOI BibTeX RDF
1	Thomas Erlebach, Erik Jan van Leeuwen	PTAS for Weighted Set Cover on Unit Squares.	APPROX-RANDOM	2010	DBLP DOI BibTeX RDF
1	Dulce B. Ponceleon, Jeff Lostpiech, Hongxia Jin, Eric Wilcox	SCOTT: set cover tracing technology.	ACM Multimedia	2010	DBLP DOI BibTeX RDF
1	Graham Cormode, Howard J. Karloff, Anthony Wirth	Set cover algorithms for very large datasets.	CIKM	2010	DBLP DOI BibTeX RDF
1	Erik D. Demaine, Morteza Zadimoghaddam	Scheduling to minimize power consumption using submodular functions.	SPAA	2010	DBLP DOI BibTeX RDF	pre-emptive scheduling, sleep state, approximation algorithms, multiprocessor scheduling
1	Daniel Lokshtanov, Jesper Nederlof	Saving space by algebraization.	STOC	2010	DBLP DOI BibTeX RDF	moebius, dynamic programming, space efficient, fourier
1	Marek Cygan, Lukasz Kowalik, Mateusz Wykurz	Exponential-time approximation of weighted set cover.	Inf. Process. Lett.	2009	DBLP DOI BibTeX RDF
1	Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos	Efficient approximation of min set cover by moderately exponential algorithms.	Theor. Comput. Sci.	2009	DBLP DOI BibTeX RDF