Combinatorial Problems: Reductibility and Approximation
Data up to Jan 2025
Total Citations Per Year
Abstract
References (61)
Reducibility among Combinatorial Problems
1972 • 10,743 citations
The Design and Analysis of Computer Algorithms
1974 • 9,688 citations
The complexity of theorem-proving procedures
1971 • 6,155 citations
An Effective Heuristic Algorithm for the Traveling-Salesman Problem
1973 • 3,730 citations
Bounds on Multiprocessing Timing Anomalies
1969 • 2,307 citations
Approximation algorithms for combinatorial problems
1974 • 2,224 citations
P-Complete Approximation Problems
1976 • 1,701 citations
Bounds for Certain Multiprocessing Anomalies
1966 • 1,606 citations
NP-complete scheduling problems
1975 • 1,365 citations
Computer and job-shop scheduling theory
1976 • 1,124 citations
On the Complexity of Timetable and Multicommodity Flow Problems
1976 • 1,045 citations
Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
1975 • 958 citations
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
1974 • 910 citations
HOW GOOD IS THE SIMPLEX ALGORITHM
1970 • 811 citations
Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
1977 • 803 citations
On the Computational Complexity of Combinatorial Problems
1975 • 683 citations
Structured Programming with go to Statements
1974 • 677 citations
Open Shop Scheduling to Minimize Finish Time
1976 • 656 citations
An Application of Bin-Packing to Multiprocessor Scheduling
1978 • 653 citations
`` Strong '' NP-Completeness Results
1978 • 624 citations
Some simplified NP-complete problems
1974 • 583 citations
Algorithms for Scheduling Independent Tasks
1976 • 582 citations
Computing Partitions with Applications to the Knapsack Problem
1974 • 556 citations
Fundamentals of data structures
1976 • 546 citations
Scheduling independent tasks to reduce mean finishing time
1974 • 498 citations
Hamiltonian circuits in random graphs
1976 • 488 citations
Complexity Results for Multiprocessor Scheduling under Resource Constraints
1975 • 486 citations
Exact and Approximate Algorithms for Scheduling Nonidentical Processors
1976 • 468 citations
Note—On “Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms”
1979 • 452 citations
Some NP-complete geometric problems
1976 • 400 citations
Computationally Related Problems
1974 • 355 citations
Approximate Algorithms for the 0/1 Knapsack Problem
1975 • 348 citations
Nondeterministic Algorithms
1967 • 348 citations
The Complexity of Near-Optimal Graph Coloring
1976 • 314 citations
Bounds for LPT Schedules on Uniform Processors
1977 • 288 citations
Estimating the efficiency of backtrack programs
1975 • 263 citations
Discrete Dynamic Programming and Capital Allocation
1969 • 230 citations
On the Significance of Solving Linear Programming Problems with Some Integer Variables
1960 • 210 citations
Sequencing by enumerative methods
1977 • 166 citations
A Level Algorithm for Preemptive Scheduling
1977 • 143 citations
Performance Guarantees for Scheduling Algorithms
1978 • 129 citations
Complexity of Scheduling Shops with No Wait in Process
1979 • 126 citations
Machine Scheduling Problems
1978 • 122 citations
General Techniques for Combinatorial Approximation
1977 • 120 citations
Approximation algorithms for some routing problems
1976 • 119 citations
Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
1977 • 107 citations
Fast probabilistic algorithms for hamiltonian circuits and matchings
1977 • 91 citations
Postscript about NP-hard problems
1974 • 91 citations
An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
1979 • 90 citations
Fast approximation algorithms for knapsack problems
1977 • 76 citations
Elements of Programming Style
1974 • 71 citations
An Almost-Optimal Algorithm for the Assembly Line Scheduling Problem
1974 • 55 citations
On the Complexity of Mean Flow Time Scheduling
1977 • 52 citations
Some complexity results for the Traveling Salesman Problem
1976 • 51 citations
Near-Optimal Solutions to a 2-Dimensional Placement Problem
1975 • 47 citations
P-complete problems and approximate solutions
1974 • 41 citations
Complexity of decision problems based on finite two-person perfect-information games
1976 • 34 citations
Algorithms for Minimizing Mean Flow Time.
1974 • 31 citations
Equivalent Integer Programs and Canonical Problems
1971 • 29 citations
An NP-complete number-theoretic problem
1978 • 10 citations
Deleted Work
1955 • 0 citations