Strong lower bounds on the approximability of some NPO PB-complete maximization problems

This publication has 10 references indexed in Scilit:

• The complexity and approximability of finding maximum feasible subsystems of linear relations
  Theoretical Computer Science, 1995
• Structure in approximation classes
  Published by Springer Nature ,1995
• Logical Definability of NP Optimization Problems
  Information and Computation, 1994
• Improved non-approximability results
  Published by Association for Computing Machinery (ACM) ,1994
• Approximating the minimum maximal independence number
  Information Processing Letters, 1993
• Quantifiers and approximation
  Theoretical Computer Science, 1993
• The approximation of maximum subgraph problems
  Published by Springer Nature ,1993
• On the complexity of approximating the independent set problem
  Information and Computation, 1992
• The complexity of optimization problems
  Journal of Computer and System Sciences, 1988
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
  Journal of the ACM, 1975