Algorithms For Dummies

  Employing Linear Programming 

     359

traveling salesman problem using integer linear programming). Linear program-

ming  has  a  wider  scope,  because  it  can  cope  with  almost  any  polynomial  time 

problem.

Linear programming sees use for needs such as manufacturing, logistics, trans-

portation (especially for airlines, for defining routes, timetables, and the cost of 

tickets),  marketing,  finance,  and  telecommunications.  All  these  applications 

require that you obtain a maximum economic result and minimum cost while opti-

mizing available resource allocation and satisfying all constraints and limitations. 

In addition, you can apply linear programming to common applications such as 

video games and computer visualization, because games require dealing with bidi-

mensional and tridimensional complex shapes, and you need to determine whether 

any shapes collide as well as ensure that they respect the rules of the game. You 

achieve these aims via the convex hull algorithm powered by linear programming 

(see 

http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_ss_07w/ 

Webprojects/Chen_hull/applications.htm

).  Finally,  linear  programming  is  at 

work  in  search  engines  for  document-retrieval  problems;  you  can  transform 

words,  phrases,  and  documents  into  functions  and  determine  how  to  maximize 

your search result (getting the documents you need in order to answer your query) 

when you look for documents with certain mathematical characteristics.