---
name: approximation-ratio-calculator
description: Analyze and prove approximation ratios for optimization algorithms
allowed-tools:
  - Bash
  - Read
  - Write
  - Edit
  - Glob
  - Grep
metadata:
  specialization: computer-science
  domain: science
  category: complexity-theory
  phase: 6
---

# Approximation Ratio Calculator

## Purpose

Provides expert guidance on analyzing approximation algorithms and proving approximation guarantees.

## Capabilities

- LP relaxation analysis
- Integrality gap computation
- Randomized rounding analysis
- Approximation factor derivation
- PTAS/FPTAS feasibility assessment
- Inapproximability results analysis

## Usage Guidelines

1. **Problem Setup**: Formalize the optimization problem
2. **LP Relaxation**: Construct and analyze LP relaxation
3. **Rounding Design**: Design rounding scheme
4. **Ratio Proof**: Prove approximation ratio
5. **Gap Analysis**: Analyze integrality gap

## Tools/Libraries

- LP/ILP solvers
- Symbolic computation
- Proof assistants