Worst-Case Analysis of Heuristic Algorithms
From MaRDI portal
Publication:3895229
DOI10.1287/mnsc.26.1.1zbMath0448.90041OpenAlexW2031061043MaRDI QIDQ3895229
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
Numerical mathematical programming methods (65K05) Integer programming (90C10) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items (40)
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 ⋮ A Comparison of Inventory Replenishment Heuristics for Minimizing Maximum Storage ⋮ Incorporating vehicle into the vehicle routing fleet composition problem ⋮ Heuristics for parallel machine scheduling with delivery times ⋮ Conditional covering: greedy heuristics and computational results ⋮ Scheduling with incompatible jobs ⋮ Joint performance of greedy heuristics for the integer knapsack problem ⋮ Algorithms with guarantee value for knapsack problems ⋮ Developing new formulations and relaxations of single stage capacitated warehouse location problem (SSCWLP): empirical investigation for assessing relative strengths and computational effort ⋮ Optimal product design using conjoint analysis: Computational complexity and algorithms ⋮ Designing and reporting on computational experiments with heuristic methods ⋮ Scheduling Large-Scale Advance-Request Dial-A-Ride Systems ⋮ Heuristics and their design: A survey ⋮ Worst case performance for lot sizing heuristics ⋮ Average performance of greedy heuristics for the integer knapsack problem. ⋮ The multidimensional 0-1 knapsack problem: an overview. ⋮ On a posterior evaluation of a simple greedy method for set packing ⋮ Analysis of a linearization heuristic for single-machine scheduling to maximize profit ⋮ A total-value greedy heuristic for the integer knapsack problem ⋮ On worst-case aggregation analysis for network location problems ⋮ Data dependent worst case bounds for weighted set packing ⋮ Worst-case analysis of greedy algorithms for the subset-sum problem ⋮ Heuristics for scheduling unrelated parallel machines ⋮ Performance of the LPT algorithm in multiprocessor scheduling ⋮ 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 ⋮ Parallel machine scheduling with splitting jobs ⋮ A combined heuristic approach to dynamic lot sizing problems ⋮ Single machine scheduling with controllable processing times and compression costs. II: Heuristics for the general case ⋮ The simple plant location problem: Survey and synthesis ⋮ An investigation of mating and population maintenance strategies in hybrid genetic heuristics for product line designs ⋮ On the Greedy Heuristic for Continuous Covering and Packing Problems ⋮ Some remarks about the `equivalence' of performance measures in scheduling problems ⋮ Analysis of a linear programming heuristic for scheduling unrelated parallel machines ⋮ Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems ⋮ Data dependent worst case bound improving techniques in zero-one programming ⋮ The multidimensional 0-1 knapsack problem -- bounds and computational aspects
This page was built for publication: Worst-Case Analysis of Heuristic Algorithms
