Dissertation/Thesis Abstract

Tangle towns tie-breaker: A multidimensional knapsack study
by McCarthy, Audrey C., M.S., California State University, Long Beach, 2012, 89; 1522244
Abstract (Summary)

This thesis investigates the Tangle Towns Tie-Breaker problem produced by the Los Angeles Times newspaper from the 1960s to the 1980s. The problem is a special case of the multidimensional knapsack problem. A linear programming based approach and a modified genetic algorithm approach are taken in an attempt to surpass the winning scores of the contest. The linear programming based approach leads to optimal solutions that improve on the winners of the newspaper contest. The genetic algorithm approach does not result in an improvement.

Improvements on both approaches are made using a ranking system. Each word is measured by how efficient it is when added to the solution. This results in a shorter runtime for the linear programming approach and higher scores for the genetic algorithm approach.

Indexing (document details)
Advisor: Ebert, Todd
Commitee: Englert, Burkhard, Gittleman, Arthur
School: California State University, Long Beach
Department: Computer Engineering and Computer Science
School Location: United States -- California
Source: MAI 51/05M(E), Masters Abstracts International
Source Type: DISSERTATION
Subjects: Operations research, Computer science
Keywords:
Publication Number: 1522244
ISBN: 9781267977397
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest