Approximation Algorithms
Explore this paper's citation graph
Summary
Over the past 6 years, there has been a sequence of major breakthroughs in the understanding of the design of approximation algorithms and of limits to obtaining such performance guarantees; this area has been one of the most flourishing areas of discrete mathematics and theoretical computer science.
- Type
- article
- Published
- 1997-11-25
- Cited by
- 4,079
- References
- 142
- OpenAlex
- https://openalex.org/W2296326525
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:834161
Keywords
Computer science, Algorithm
References
- The primal-dual method for approximation algorithms and its application to network design problems
- The Sandwich Theorem
- Algorithms for Random Generation and Counting: A Markov Chain Approach
- Combinatorial problems and exercises
- Cut problems and their application to divide-and-conquer
- Probabilistic checking of proofs and hardness of approximation problems
- Near-optimal bin packing algorithms
- A randomized fully polynomial time approximation scheme for the all terminal network reliability problem
- Improved bounds for sampling colorings
- A bound for the Steiner tree problem in graphs
- A Fast Monte-Carlo Test for Primality
- On the bidirected cut relaxation for the metric Steiner tree problem
- On Coupling and the Approximation of the Permanent
- Clustering to Minimize the Maximum Intercluster Distance
- Approximating Latin Square Extensions
- A primal-dual schema based approximation algorithm for the element connectivity problem
- The Swendsen-Wang process does not always mix rapidly
- The complexity of optimization problems
- Easy and hard bottleneck location problems
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Cited by
- Computational study for domination problems in planar graphs
- Mechanisms for discrete optimization with rational agents
- Multi-vehicle Routing
- Covering problems in edge- and node-weighted graphs
- Truthful mechanisms for real-time system scheduling in competitive environments
- Using Classification to Protect the Integrity of Spectrum Measurements in White Space Networks
- Book List for Algorithms and Data Structures Summer 2008
- Analysis of STAGE Algorithm Based on Solving Bin Packing Problem
- Accelerated Fuzzy Clustering
- Efficient query processing for modern data management
- First Fit Algorithm for Bin Packing
- Approximation Algorithms for Feasibility Analysis in Real-Time Static-Priority Systems ⁄
- Strategic Optimization Techniques For FRTU Deployment and Chip Physical Design
- Computationally Tractable stochastic Integer Programming Models for Air Traffic Flow Management
- Efficient Resource Utilization in Advanced Wireless Networks
- Search in the Physical World
- Anytime Algorithms for Mining Groups with Maximum Coverage
- Stability Via Convexity and LP Duality in OCF Games
- Algorithms for cartographic visualization
- Approximation Algorithms for Constrained Knapsack Problems
Related papers
- Remarks on Algorithm 2, Algorithm 3, Algorithm 15, Algorithm 25 and Algorithm 26
- Remarks on Algorithm 332: Jacobi polynomials: Algorithm 344: student's t-distribution: Algorithm 351: modified Romberg quadrature: Algorithm 359: factoral analysis of variance
- Using DataGrid Control to Realize DataBase of Querying in VB6.0
- Study and Two Types of Typical Usage of DataGrid Web Server Control
- PACWON: A parallelizing compiler for workstations on a network
- Bidirectional Sort and Choosing a Row to Update or Delete by Click Any Cell in DataGrid
- OpenCL-accelerated object classification in video streams using Spatial Pooler of Hierarchical Temporal Memory
- ESKVS: efficient and secure approach for keyframes-based video summarization framework