Worst-Case Analysis

David Simchi-Levi, Xin Chen, Julien Bramel

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Since most complicated logistics problems, for example, the bin-packing problem and the traveling salesman problem, are (Formula Presented)-Hard, it is unlikely that polynomial-time algorithms will be developed for their optimal solutions. Consequently, a great deal of work has been devoted to the development and analyses of heuristics. In this chapter, we demonstrate one important tool, referred to as worst-case performance analysis, which establishes the maximum deviation from optimality that can occur for a given heuristic algorithm. We will characterize the worst-case performance of a variety of algorithms for the bin-packing problem and the traveling salesman problem. The results obtained here serve as important building blocks in the analysis of algorithms for vehicle routing problems.

Original languageEnglish (US)
Title of host publicationSpringer Series in Operations Research and Financial Engineering
PublisherSpringer Nature
Pages65-84
Number of pages20
DOIs
StatePublished - 2014

Publication series

NameSpringer Series in Operations Research and Financial Engineering
ISSN (Print)1431-8598
ISSN (Electronic)2197-1773

Keywords

  • Absolute Performance Ratio
  • Asymmetric Traveling Salesman Problem
  • Traveling Salesman
  • Triangle Inequality Assumption
  • Worst-case Bound

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computational Mathematics
  • Control and Optimization
  • Information Systems and Management
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Worst-Case Analysis'. Together they form a unique fingerprint.

Cite this