Worst-Case Analysis of Heuristic Algorithms

DOI10.1287/MNSC.26.1.1MaRDI QIDQ3895229zbMATH OpenOpenAlexFDO

Authors Marshall L. Fisher

Publication date 1980

Published in Management Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/mnsc.26.1.1

zbMATH Keywords

approximate solution of integer programsheuristic algorithmsknapsack problemworst-case analysis

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Integer programming (90C10)

Cited in

(40)

• Analysis of a linear programming heuristic for scheduling unrelated parallel machines
• The 2-quasi-greedy algorithm for cardinality constrained matroid bases
• Average and worst-case analysis of heuristics for the maximum tardiness problem
• Exact methods for the knapsack problem and its generalizations
• Conditional covering: greedy heuristics and computational results
• Optimal product design using conjoint analysis: Computational complexity and algorithms
• Heuristics and their design: A survey
• Worst case performance for lot sizing heuristics
• A total-value greedy heuristic for the integer knapsack problem
• Single machine scheduling with controllable processing times and compression costs. II: Heuristics for the general case
• Some remarks about the `equivalence' of performance measures in scheduling problems
• Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems
• Heuristics for parallel machine scheduling with delivery times
• Scheduling with incompatible jobs
• Joint performance of greedy heuristics for the integer knapsack problem
• Average performance of greedy heuristics for the integer knapsack problem.
• The multidimensional 0-1 knapsack problem: an overview.
• Parallel machine scheduling with splitting jobs
• Assessment of approximate algorithms: The error measure's crucial role
• Solving the fixed charge problem with Lagrangian relaxation and cost allocation heuristics
• Heuristic methods and applications: A categorized survey
• The simple plant location problem: Survey and synthesis
• Designing and reporting on computational experiments with heuristic methods
• Heuristics for scheduling unrelated parallel machines
• Incorporating vehicle into the vehicle routing fleet composition problem
• Data dependent worst case bounds for weighted set packing
• An investigation of mating and population maintenance strategies in hybrid genetic heuristics for product line designs
• Algorithms with guarantee value for knapsack problems
• Worst-case analysis of greedy algorithms for the subset-sum problem
• Analysis of a linearization heuristic for single-machine scheduling to maximize profit
• Scheduling Large-Scale Advance-Request Dial-A-Ride Systems
• A Comparison of Inventory Replenishment Heuristics for Minimizing Maximum Storage
• A combined heuristic approach to dynamic lot sizing problems
• On the Greedy Heuristic for Continuous Covering and Packing Problems
• Performance of the LPT algorithm in multiprocessor scheduling
• On worst-case aggregation analysis for network location problems
• Data dependent worst case bound improving techniques in zero-one programming
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• Developing new formulations and relaxations of single stage capacitated warehouse location problem (SSCWLP): empirical investigation for assessing relative strengths and computational effort
• On a posterior evaluation of a simple greedy method for set packing

This page was built for publication: Worst-Case Analysis of Heuristic Algorithms

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