Towards Average-Case Complexity Analysis of NP Optimization Problems.
Rainer SchulerOsamu WatanabePublished in: Computational Complexity Conference (1995)
Keyphrases
- average case
- complexity analysis
- optimization problems
- computational complexity
- worst case
- evolutionary algorithm
- theoretical analysis
- lower bound
- worst case analysis
- metaheuristic
- objective function
- learning curves
- uniform distribution
- cost function
- np hard
- traveling salesman problem
- first order logic
- knapsack problem
- learning theory
- vc dimension
- sample complexity bounds
- combinatorial optimization
- learning algorithm
- upper bound
- special case
- average case complexity