approximation guarantee
A formal assurance that an algorithm's output is close to the optimal solution, typically expressed as a bound on the difference between the approximation and the exact result.
- A Unified Approach to Submodular Maximization Under Noise
- Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
- Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives
- Efficient $k$-Sparse Band–Limited Interpolation with Improved Approximation Ratio
- GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
- Mechanism Design via the Interim Relaxation
- Parsimonious Predictions for Strategyproof Scheduling