@inbook{34369eaff0b04c07a9a93e1b7d00baf1,

title = "Worst-Case Analysis",

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.",

keywords = "Absolute Performance Ratio, Asymmetric Traveling Salesman Problem, Traveling Salesman, Triangle Inequality Assumption, Worst-case Bound",

author = "David Simchi-Levi and Xin Chen and Julien Bramel",

note = "Publisher Copyright: {\textcopyright} 2014, Springer Science+Business Media New York.",

year = "2014",

doi = "10.1007/978-1-4614-9149-1_4",

language = "English (US)",

series = "Springer Series in Operations Research and Financial Engineering",

publisher = "Springer Nature",

pages = "65--84",

booktitle = "Springer Series in Operations Research and Financial Engineering",

address = "United States",

}