A Novel LP-based Local Search Technique– Fast and Quite Good –Vom Fachbereich Informatik derTechnische Universit¨at Darmstadtzur Erlangung des akademischen Grades einesDr. rer. nat.genehmigte DissertationvonHerrn Alaubek Avdil (M.Sc.)aus der Ulaanbaatar, MongoleiReferent: Professor Dr. Karsten WeiheKorreferent: Professor Dr. Matthias Mu¨ller-HannemannTag der Einreichung: 04. Juni 2009Tag der mu¨ndlichen Pru¨fung: 17. Juli 2009Darmstadt 2009D 17iiAcknowledgmentsIwanttoexpressmydeepandsinceregratitudetomysupervisorProf.KarstenWeiheforenablingmy doctoral study, inspiringwith scientific work and motivating and providing mepleasant research and work atmosphere. Without his trust and encouragement my researchwould not be done and this theses would not exist.Iam extremely grateful toProf. Matthias Mu¨ller-Hannemann forhis invaluablesupportand advice on my research, excellent and critical review to improve the presentation of mywork, and for his friendship, and making it possible for my young family be close with meduring my doctoral study in Germany.I would like to express my warm and sincere thanks to the colleagues and membersof Algorithmics Group at the Department of Computer Science of Technische Universit¨atDarmstadt for their support and valuable comments on my research. My special ackno-wledgment goes to Dr.