Search results for "set-cover"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
72	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
72	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
69	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
67	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
56	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
54	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
54	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
54	Tianping Shuai, Xiao-Dong Hu 0001	Connected Set Cover Problem and Its Applications.	AAIM	2006	DBLP DOI BibTeX RDF	Approximation algorithm, Set cover, Wavelength assignment, Performance ratio
52	Uriel Feige	A Threshold of ln n for Approximating Set Cover.	J. ACM	1998	DBLP DOI BibTeX RDF	set cover, approximation ratio
50	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
49	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
48	Kasturi R. Varadarajan	Weighted geometric set cover via quasi-uniform sampling.	STOC	2010	DBLP DOI BibTeX RDF	approximation, set cover, epsilon nets
45	Kamesh Munagala, Shivnath Babu, Rajeev Motwani 0001, Jennifer Widom	The Pipelined Set Cover Problem.	ICDT	2005	DBLP DOI BibTeX RDF
45	Toshihiro Fujito, Tsuyoshi Okumura	A Modified Greedy Algorithm for the Set Cover Problem with Weights 1 and 2.	ISAAC	2001	DBLP DOI BibTeX RDF
45	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
45	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
44	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
43	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
43	Kenneth L. Clarkson, Kasturi R. Varadarajan	Improved approximation algorithms for geometric set cover.	SCG	2005	DBLP DOI BibTeX RDF	algorithms, approximation, set cover
42	Alexandre H. L. Porto, Valmir Carneiro 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
41	Chandra Chekuri, Kenneth L. Clarkson, Sariel Har-Peled	On the set multi-cover problem in geometric settings.	SCG	2009	DBLP DOI BibTeX RDF	set cover, cuttings, LP rounding
40	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
40	Julia Chuzhoy, Joseph Naor	Covering Problems with Hard Capacities.	FOCS	2002	DBLP DOI BibTeX RDF
39	Ruoming Jin, Yang Xiang, Lin Liu 0001	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
39	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
39	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
38	Gruia Calinescu	Bounding the Payment of Approximate Truthful Mechanisms.	ISAAC	2004	DBLP DOI BibTeX RDF
35	Asaf Levin	Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search.	WAOA	2006	DBLP DOI BibTeX RDF
35	Jean Cardinal, Samuel Fiorini, Gwenaël Joret	Tight Results on Minimum Entropy Set Cover.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
34	Peng Cui 0008	A Tighter Analysis of Set Cover Greedy Algorithm for Test Set.	ESCAPE	2007	DBLP DOI BibTeX RDF
34	Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni	Limitations of cross-monotonic cost sharing schemes.	SODA	2005	DBLP BibTeX RDF
33	Uriel Feige, László Lovász 0001, Prasad Tetali	Approximating Min Sum Set Cover.	Algorithmica	2004	DBLP DOI BibTeX RDF	Threshhold, NP-hardness, Greedy algorithm, Randomized rounding
33	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
33	Uriel Feige, László Lovász 0001, Prasad Tetali	Approximating Min-sum Set Cover.	APPROX	2002	DBLP DOI BibTeX RDF
33	Nikhil R. Devanur, Milena Mihail, Vijay V. Vazirani	Strategyproof cost-sharing mechanisms for set cover and facility location games.	EC	2003	DBLP DOI BibTeX RDF	mechanism design, facility location, set cover, cost sharing
32	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
31	Kasturi R. Varadarajan	Epsilon nets and union complexity.	SCG	2009	DBLP DOI BibTeX RDF	approximation algorithms, set cover, epsilon nets
31	Vangelis Th. Paschos	A Theorem on the Approximation of Set Cover and Vertex Cover.	FSTTCS	1991	DBLP DOI BibTeX RDF
31	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
30	Zhao Zhang 0002, Xiaofeng Gao 0001, Xuefei Zhang, Weili Wu 0001, Hui Xiong 0001	Three Approximation Algorithms for Energy-Efficient Query Dissemination in Sensor Database System.	DEXA	2009	DBLP DOI BibTeX RDF	Fault Tolerance, Set Cover, Sensor Database
30	Yuichi Yoshida, Masaki Yamamoto 0001, 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
30	Xiang-Yang Li 0001, Zheng Sun, Weizhao Wang	Cost Sharing and Strategyproof Mechanisms for Set Cover Games.	STACS	2005	DBLP DOI BibTeX RDF
29	Marcelo C. Couto, Pedro Jussieu de Rezende, Cid C. de Souza	An IP solution to the art gallery problem.	SCG	2009	DBLP DOI BibTeX RDF	integer programming, visibility, set cover, art gallery
28	Min Lu, Tian Liu 0001, Weitian Tong, Guohui Lin, Ke Xu 0001	Set Cover, Set Packing and Hitting Set for Tree Convex and Tree-Like Set Systems.	TAMC	2014	DBLP DOI BibTeX RDF
27	Julien Kritter, Mathieu Brévilliers, Julien Lepagnot, Lhassane Idoumghar	On the computational cost of the set cover approach for the optimal camera placement problem and possible set-cover-inspired trade-offs for surveillance infrastructure design.	RAIRO Oper. Res.	2021	DBLP DOI BibTeX RDF
27	Rahil Sharma	Hard Capacitated Set Cover and Uncapacitated Geometric Set Cover.	CoRR	2016	DBLP BibTeX RDF
27	Apurva Mudgal, Supantha Pandit	Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions.	Discret. Appl. Math.	2016	DBLP DOI BibTeX RDF
27	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
27	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
27	Zhao Zhang 0002, Xiaofeng Gao 0001, Weili Wu 0001	Algorithms for connected set cover problem and fault-tolerant connected set cover problem.	Theor. Comput. Sci.	2009	DBLP DOI BibTeX RDF
26	Francesco Bonchi, Carlos Castillo 0001, Debora Donato, Aristides Gionis	Topical query decomposition.	KDD	2008	DBLP DOI BibTeX RDF	query recommendation, clustering, set cover
26	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
26	Noga Alon, Dana Moshkovitz, Shmuel Safra	Algorithmic construction of sets for k-restrictions.	ACM Trans. Algorithms	2006	DBLP DOI BibTeX RDF	k-restriction, almost k-wise independence, generalized hashing, splitter, Set-Cover, Derandomization, group testing
25	Refael Hassin, Danny Segev	The Set Cover with Pairs Problem.	FSTTCS	2005	DBLP DOI BibTeX RDF
25	Zheng Sun, Xiang-Yang Li 0001, Weizhao Wang, Xiaowen Chu 0001	Mechanism Design for Set Cover Games When Elements Are Agents.	AAIM	2005	DBLP DOI BibTeX RDF
25	Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni	Limitations of cross-monotonic cost-sharing schemes.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	Cross-monotonic cost-sharing schemes, group-strategyproof mechanism design, probabilistic method
25	Paz Carmi, Matthew J. Katz, Nissan Lev-Tov	Covering Points by Unit Disks of Fixed Location.	ISAAC	2007	DBLP DOI BibTeX RDF
25	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
25	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
25	Stefan Porschen	On the Time Complexity of Rectangular Covering Problems in the Discrete Plane.	ICCSA (3)	2004	DBLP DOI BibTeX RDF	rectangular set cover, integer lattice, NP-completeness, discrete plane
24	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. Biol. Bioinform.	2007	DBLP DOI BibTeX RDF	graph algorithms, genetics, biology, bioinformatics (genome or protein) databases, Computations on discrete structures
24	Kenneth L. Clarkson, Kasturi R. Varadarajan	Improved Approximation Algorithms for Geometric Set Cover.	Discret. Comput. Geom.	2007	DBLP DOI BibTeX RDF
24	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
23	David Peleg	Approximation Algorithms for the Label-CoverMAX and Red-Blue Set Cover Problems.	SWAT	2000	DBLP DOI BibTeX RDF
22	Nikhil Bansal 0001, Jatin Batra, Majid Farhadi, Prasad Tetali	On Min Sum Vertex Cover and Generalized Min Sum Set Cover.	SIAM J. Comput.	2023	DBLP DOI BibTeX RDF
22	Nikhil Bansal 0001, Jatin Batra, Majid Farhadi, Prasad Tetali	Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover.	SODA	2021	DBLP DOI BibTeX RDF
22	Karthik C. S., Inbal Livni Navon	On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes.	SOSA	2021	DBLP DOI BibTeX RDF
22	Karthik C. S., Inbal Livni Navon	On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes.	CoRR	2020	DBLP BibTeX RDF
22	Nikhil Bansal 0001, Jatin Batra, Majid Farhadi, Prasad Tetali	Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover.	CoRR	2020	DBLP BibTeX RDF
22	Yossi Azar, Ashish Chiplunkar, Shay Kutten, Noam Touitou	Set Cover and Vertex Cover with Delay.	CoRR	2018	DBLP BibTeX RDF
22	Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan 0001, Saket Saurabh 0001	Partially Polynomial Kernels for Set Cover and Test Cover.	SIAM J. Discret. Math.	2016	DBLP DOI BibTeX RDF
22	Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan 0001, Saket Saurabh 0001	Partially Polynomial Kernels for Set Cover and Test Cover.	FSTTCS	2013	DBLP DOI BibTeX RDF
22	Barna Saha, Samir Khuller	Set Cover Revisited: Hypergraph Cover with Hard Capacities.	ICALP (1)	2012	DBLP DOI BibTeX RDF
22	Dorit S. Hochbaum, Asaf Levin	The multi-integer set cover and the facility terminal cover problem.	Networks	2009	DBLP DOI BibTeX RDF
22	Petr Slavík	Improved Performance of the Greedy Algorithm for the Minimum Set Cover and Minimum Partial Cover Problems	Electron. Colloquium Comput. Complex.	1995	DBLP BibTeX RDF
21	Michael Dom, Daniel Lokshtanov, Saket Saurabh 0001	Incompressibility through Colors and IDs.	ICALP (1)	2009	DBLP DOI BibTeX RDF
20	Liang Chen, Jason Crampton	Set Covering Problems in Role-Based Access Control.	ESORICS	2009	DBLP DOI BibTeX RDF
20	Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher	A Derandomization Using Min-Wise Independent Permutations.	RANDOM	1998	DBLP DOI BibTeX RDF
20	Satoru Iwata 0001, Kiyohito Nagano	Submodular Function Minimization under Covering Constraints.	FOCS	2009	DBLP DOI BibTeX RDF	approximation algorithm, set cover, vertex cover, submodular function
20	Fedor V. Fomin, Fabrizio Grandoni 0001, Artem V. Pyatkin, Alexey A. Stepanov	Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	Exact exponential algorithms, domatic number, listing algorithms, measure and conquer, minimum dominating set, minimum set cover
20	Venkatesh Raman 0001, Saket Saurabh 0001	Short Cycles Make W -hard Problems Hard: FPT Algorithms for W -hard Problems in Graphs with no Short Cycles.	Algorithmica	2008	DBLP DOI BibTeX RDF	t-vertex cover, Dominating set, Set cover, Independent set, Parameterized complexity
20	Meng-Chiou Wu, Rung-Bin Lin, Shih-Cheng Tsai	Chip placement in a reticle for multiple-project wafer fabrication.	ACM Trans. Design Autom. Electr. Syst.	2008	DBLP DOI BibTeX RDF	Multiple-project wafers (MPW), compatibility graph, reticle floorplanning, shuttle mask, wafer dicing, simulated annealing (SA), set cover, mixed-integer linear programming (MILP), conflict graph, set partition
20	Yang Xiang, Ruoming Jin, David Fuhry, Feodor F. Dragan	Succinct summarization of transactional databases: an overlapped hyperrectangle scheme.	KDD	2008	DBLP DOI BibTeX RDF	hyperrectangle, summarization, set cover, transactional databases
20	Doina Logofatu, Rolf Drechsler	Comparative Study by Solving the Test Compaction Problem.	ISMVL	2008	DBLP DOI BibTeX RDF	Backtracking, Multi-Valued Logic, Test Compaction, Set Cover Problem, Greedy, Don't Cares
20	Alberto Aloisio, Vincenzo Izzo, Salvatore Rampone	VLSI implementation of greedy-based distributed routing schemes for ad hoc networks.	Soft Comput.	2007	DBLP DOI BibTeX RDF	Greedy algorithm, Ad hoc wireless network, FPGA implementation, Minimum set cover
20	Anirban Dasgupta 0001, Arpita Ghosh, Ravi Kumar 0001, Christopher Olston, Sandeep Pandey, Andrew Tomkins	The discoverability of the web.	WWW	2007	DBLP DOI BibTeX RDF	max cover, discovery, set cover, crawling, greedy
20	Matthias F. M. Stallmann, Franc Brglez	High-contrast algorithm behavior: observation, hypothesis, and experimental design.	Experimental Computer Science	2007	DBLP DOI BibTeX RDF	all-integer dual simplex, block-diagonal form, optimization, set cover, crossing minimization
20	David S. Johnson	The NP-completeness column: The many limits on approximation.	ACM Trans. Algorithms	2006	DBLP DOI BibTeX RDF	label cover, Approximation algorithms, lower bounds, set cover, clique, probabilistically checkable proofs, Unique Games Conjecture
20	Yigal Bejerano, Rajeev Rastogi	Robust monitoring of link delays and faults in IP networks.	IEEE/ACM Trans. Netw.	2006	DBLP DOI BibTeX RDF	latency and fault monitoring, approximation algorithms, set cover problem, network failures
20	Torsten Fahle, Karsten Tiemann	A faster branch-and-bound algorithm for the test-cover problem based on set-covering techniques.	ACM J. Exp. Algorithmics	2006	DBLP DOI BibTeX RDF	test-cover problem, variable fixing, Branch-and-bound, Lagrangian relaxation, set-cover problem
20	Özgür Sümer	Partial covering of hypergraphs.	SODA	2005	DBLP BibTeX RDF	partial hypergraph cover, partial set cover, greedy algorithm
20	Adam Cannon, Lenore Cowen	Approximation Algorithms for the Class Cover Problem.	Ann. Math. Artif. Intell.	2004	DBLP DOI BibTeX RDF	disk cover, margin classifier, classification, approximation algorithms, set cover
20	Alon Efrat, Frank Hoffmann 0002, Christian Knauer, Klaus Kriegel, Günter Rote, Carola Wenk	Covering with Ellipses.	Algorithmica	2004	DBLP DOI BibTeX RDF	Approximation algorithm, Computational geometry, Set cover, Proteomics, Algorithms and data structures
20	Reuven Bar-Yehuda	Using Homogenous Weights for Approximating the Partial Cover Problem.	SODA	1999	DBLP BibTeX RDF	approximation algorithm, set cover, vertex cover, knapsack, covering problems, local ratio, partial covering
20	Moni Naor, Leonard J. Schulman, Aravind Srinivasan	Splitters and Near-Optimal Derandomization.	FOCS	1995	DBLP DOI BibTeX RDF	splitters, near-optimal derandomization, fairly general method, k-restrictions, probabilistic bound, near-optimal constructions, fixed-subgraph finding algorithms, deterministic constructions, local-coloring protocol, computational complexity, learning, probability, computational linguistics, hardness of approximation, set cover, derandomization, randomised algorithms, exhaustive testing
20	Carsten Lund, Mihalis Yannakakis	On the Hardness of Approximating Minimization Problems.	J. ACM	1994	DBLP DOI BibTeX RDF	clique cover, approximation algorithms, NP-hard, graph coloring, dominating set, set cover, independent set, chromatic number, probabilistically checkable proofs, hitting set
20	Aditi Dhagat, Lisa Hellerstein	PAC Learning with Irrelevant Attributes	FOCS	1994	DBLP DOI BibTeX RDF	polynomial-time Occam algorithm, irrelevant attributes, Occam algorithm, decision lists, greedy set cover, polynomial-time, PAC learning
20	Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk	The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations	FOCS	1993	DBLP DOI BibTeX RDF	approximate optima, NP-hard, lattices, codes, polynomial time algorithm, linear equations, interactive proof systems, hardness, set-cover problem, binary codes
20	Richard Chang 0001, William I. Gasarch	On Bounded Queries and Approximation	FOCS	1993	DBLP DOI BibTeX RDF	NP-optimization problems, NP oracle, maximum clique size, computational complexity, approximation, graph coloring, set cover, complexity measure, approximation factor, bounded queries
20	Vassilis Zissimopoulos, Vangelis Th. Paschos, Ferhan Pekergin	On the Approximation of NP-Complete Problems by Using the Boltzmann Machine Method: The Cases of Some Covering and Packing Problems.	IEEE Trans. Computers	1991	DBLP DOI BibTeX RDF	Boltzmann machine method, minimum vertex cover, computational complexity, parallel architectures, approximation, neural nets, NP-complete problems, heuristic programming, covering, clique, combinatorial mathematics, optimal solutions, maximum independent set, set partitioning, packing problems, minimum set cover