P-Complete Approximation Problems (2024)

Skip Abstract Section

1. 1 BODIN, L D. A graph theoretic approach to the grouping of ordering data. Networks 2 (1972), 307- 310Google Scholar
2. 2 BRUNO, J, COFFMAN, E G, AND SETm, R Scheduling independent tasks to reduce mean finishrag-time Comm ACM 17, 7 (July 1974), 382-387. Google Scholar
3. 3 CONWAY, R W., MAXWELL, N.L, AND MILLER, L W Theory of Scheduhng Addison-Wesley, Reading, Mass, 1967Google Scholar
4. 4 CooK, S A The complexity of theorem-proving procedures Conf. Record of Third ACM Syrup on Theory of Computing, 1970, pp 151-158. Google Scholar
5. 5 GARFINKEL, R S., AND NEMHAUSER, G L Integer Programming Wiley, New York, 1972Google Scholar
6. 6 GARE~, M R, AND JOHNSON, D S The complexity of near-optimal graph coloring. J ACM 23, 1 (Jan 1976), 43-69 Google Scholar
7. 7 GAREY, M R, JOHNSON, D S, AND STOCKMEYER, L J Some simplified NP-complete problems Theoretical Comput Sc~ (to appear) Google Scholar
8. 8 GRAHAM, R L Bounds on multlprocesslng timing anomalies SIAM j Appl Math 17, 2 (March 1969), 416-429Google Scholar
9. 9 HOROWITZ, E, AND SAHNI, S Exact and approximate algorithms for scheduhng nomdentlcal processors J ACM 23, 2 (April 1976), 317-327 Google Scholar
10. 10 InAaRA, O H, AND KIM, C E Fast approximation algorithms for the knapsack and sum of subset problems. J ACM 22, 4 (Oct. 1975), 463-468. Google Scholar
11. 11 JOHNSON, D Approximation algorithms for combinatorml problems. J Comput. Syst Sczs 9, 3 (Dec 1974), 256-278Google Scholar
12. 12 JOHNSON, D.B, ANY LAFUENTF., J M A controlled single pass classification algorithm with{ application to multilevel clustering Scientific Rep #ISR-18, Information Sczence and Retrieval, Cornell U , Ithaca, N Y , Oct 1970, pp XII-1-XII-37Google Scholar
13. 13 KARP, R M Reducibility among combinatorial problems In Complexity of Computer Computa-{ tions, R E Miller and J W Thatcher, Eds , Plenum Press, N Y, 1972, pp 85-104Google Scholar
14. 14 KNUTH, D E. A terminological proposal ACM SIGACT News 6, 1 (Jan 1974), 12-18Google Scholar
15. 15 LUKES, J A Combinatorml solutmn to the partitioning of general graphs IBM J Res and Develop 19, 2 (March 1975), 170-180Google Scholar
16. 16 ROS~NKRASTZ, D J , STEAar~S, R E , ANn L~.wm, P M Approximate algorithms for the travelhng salesperson problem 15th Annual IEEE Symp on Switching and Automata Theory, 1974, pp 33- 42Google Scholar
17. 17 Ross, G T, AND SOLAND, R M A branch and bound algorithm for the generalized assignment problem Math Programming 8 (1975), 91-103Google Scholar
18. 18 SAHNI, S. Algorithms for scheduhng independent tasks J ACM 23, 1 (Jan 1976), 116-127 Google Scholar
19. 19 SAHNI, S Computationally related problems. SIAM J Comput 3, 4 (Dec 1974), pp 262-279Google Scholar
20. 20 SAHNI, S Approximate algorithms for the 0/1 knapsack problem J ACM22, 1 (Jan 1975), 115- 124 Google Scholar

Index Terms

1. P-Complete Approximation Problems

   1. Mathematics of computing

      1. Mathematical analysis

         1. Functional analysis

            1. Approximation

         2. Mathematical optimization

   2. Theory of computation

      1. Design and analysis of algorithms

         1. Approximation algorithms analysis

         2. Mathematical optimization

• Approximation of Natural W[P]-Complete Minimisation Problems Is Hard

  CCC '08: Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity

  We prove that the weighted monotone circuit satisfiability problem has no fixed-parameter tractable approximation algorithm with constant or polylogarithmic approximation ratio unless FPT = W[P]. Our result answers a question of Alekhnovich and Razborov,...

  Read More

• Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems

  In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Max d-Clique and Max d-Club: A d-clique in a graph $$G = (V, E)$$G=(V,E) is a subset $$S\subseteq V$$S⊆V of vertices ...

  Read More

• Intractability results for problems in computational learning and approximation

  Read More