Approximation algorithms for combinatorial problems
Explore this paper's citation graph
Summary
For the problem of finding the maximum clique in a graph, no algorithm has been found for which the ratio does not grow at least as fast as 0(nε), where n is the problem size and ε> 0 depends on the algorithm.
- Type
- article
- Published
- 1973-04-30
- Cited by
- 2,648
- References
- 14
- Access
- Open access
- OpenAlex
- https://openalex.org/W2040924621
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:42632644
Keywords
Mathematics, Simple (philosophy), Approximation algorithm, Bounded function, Constant (computer programming)
References
- On The Knapsack And Other Computationally Related Problems
- Near-optimal bin packing algorithms
- Fast Allocation Algorithms
- The complexity of theorem-proving procedures
- Bounds on multiprocessing anomalies and related packing algorithms
- Worst-case analysis of memory allocation algorithms
- An upper bound for the chromatic number of a graph and its application to timetabling problems
- A technique for colouring a graph applicable to large scale timetabling problems
- Reducibility among combinatorial problems" in complexity of computer computations
- GRAPH COLORING ALGORITHMS
- Reducibility Among Combinatorial Problems
Cited by
- Computational study for domination problems in planar graphs
- A Theoretical Analysis of Query Selection for Collaborative Filtering
- Biclique Coverings, Rectifier Networks and the Cost of ε-Removal
- ROSETTA Technical Reference Manual
- A Note on Set Cover Inapproximability Independent of Universe Size
- How to guard a graph against tree movements
- Structure in Approximation Classes (Extended Abstract)
- Routing and scheduling of vehicles and crews : The state of the art
- Heuristic algorithms for wireless mesh network planning
- Towards an Approximation Theory of Discrete Problems. Part I
- Hiding information by cell suppression
- Quantifying the Inductive Bias in Concept Learning (Extended Abstract)
- Methodologies for Designing and Recording Speech Databases for Corpus Based Synthesis
- Approximation algorithms via the primal-dual schema: applications of the simple dual-ascent method to problems from logistics
- On the performance of on-line algorithms for partition problems
- Tradeoffs in the Design of On-Line Systems
- Обобщенные покрытия и их аппроксимации
- Improving Generation of Object-Oriented Test Suites by Avoiding Redundant Tests
- Maximum independent set and related problems, with applications
- Approximation for Dominating Set Problem with Measure Functions
Related papers
- A fast algorithm for the maximum clique problem
- NK-PMC: A new exact branch and bound parallel algorithm for the maximum clique problem
- Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
- A simple and efficient heuristic algorithm for maximum clique problem
- Approximate local search in combinatorial optimization
- Approximate local search in combinatorial optimization
- A Hypercube Algorithm for the 0/1 Knapsack Problem