Back to search

Combinatorial Problems: Reductibility and Approximation

Data up to Jan 2025

Published1978
Citations33
References61

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

Cited By (0)

Loading...