NP-Complete operations research problems and approximation algorithms

68Q25: Analysis of algorithms and problem complexity

90C10: Integer programming

90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

Related Items

Allowable processing orders in the accelerated cascade algorithm, Semirings and path spaces

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
NP-complete scheduling problems
Hamiltonian circuits in random graphs
Some simplified NP-complete graph problems
Fast algorithms for bin packing
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
On the Computational Complexity of Combinatorial Problems
Algorithms for Scheduling Independent Tasks
Exact and Approximate Algorithms for Scheduling Nonidentical Processors
Bounds for Multiprocessor Scheduling with Resource Constraints
Scheduling Tasks with Nonuniform Deadlines on Two Processors
Open Shop Scheduling to Minimize Finish Time
Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
The Planar Hamiltonian Circuit Problem is NP-Complete
Bounds for LPT Schedules on Uniform Processors
A Level Algorithm for Preemptive Scheduling
On the Complexity of Timetable and Multicommodity Flow Problems
Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
Approximate Algorithms for the 0/1 Knapsack Problem
Complexity Results for Multiprocessor Scheduling under Resource Constraints
Complexity of Scheduling under Precedence Constraints
Flowshop and Jobshop Schedules: Complexity and Approximation
Performance Guarantees for Scheduling Algorithms
An Application of Bin-Packing to Multiprocessor Scheduling
Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
`` Strong NP-Completeness Results
Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
Combinatorial Problems: Reductibility and Approximation
Two-Commodity Flow
Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
Best Algorithms for Approximating the Maximum of a Submodular Set Function
The Complexity of Flowshop and Jobshop Scheduling
Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
On the Complexity of Mean Flow Time Scheduling
Approximation Algorithms for Certain Scheduling Problems
Scheduling independent tasks to reduce mean finishing time
An Almost-Optimal Algorithm for the Assembly Line Scheduling Problem
Bounds for Certain Multiprocessing Anomalies
Bounds on Multiprocessing Timing Anomalies
The complexity of theorem-proving procedures
An Effective Heuristic Algorithm for the Traveling-Salesman Problem