NP-Complete operations research problems and approximation algorithms

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Integer programming (90C10)

Cites Work

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

Cited In (2)

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

This page was built for publication: NP-Complete operations research problems and approximation algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4187586)