Microaggregation is a method of statistical disclosure control that attempts to reconcile the need to release information to researchers with the need to protect privacy of individual records in a dataset. Under microaggregation, records are divided into groups containing at least k members. Actual data values of the members are replaced by the mean value of the group, such that each record in the group is indistinguishable from at least k-1 other records. The goal of microaggregation is to create groups of similar records such that information loss is minimized, where information loss is the sum squared deviation between the actual data values and the group means. Optimal multivariate microaggregation is an NP-hard problem, and heuristics have been proposed to generate solutions in reasonable running time. New heuristics are desirable for either producing groups with lower information loss, or for producing groups with similar information loss but lower computational complexity. Some of the best performing existing microaggregation heuristics are based on record ordering, since it has been proven that for a given ordering of records, the optimal set of groups for that particular ordering can be efficiently computed. This dissertation improves on previous heuristics that order records in a dataset and subsequently use this record ordering to generate high quality microaggregated k- partitions. This was accomplished by using heuristics from the traveling salesman problem (TSP) literature in order to more effectively order the records. In particular, two tour construction heuristics - the Greedy heuristic and the Quick Boruvka heuristic - that are comparable in complexity to extant microaggregation methods were investigated. Next, three tour improvement heuristics - 2-opt, 3-opt, and Lin-Kernighan - were used on the tours constructed to investigate whether further reduction in information loss could be achieved. The tour improvement heuristics - particularly the 3-opt and Lin-Kernighan heuristics - provided microaggregation solutions better than the best previous known solutions across several datasets and values of k.

Genetic algorithms are an evolutionary technique that use crossover and mutation operators to solve optimization problems using a survival of the fittest idea. They have been used successfully in a variety of different problems, including the traveling salesman problem. In the traveling salesman problem we wish to find a tour of all nodes in a weighted graph so that the total weight is minimized. The traveling salesman problem is NP-hard but has many real world applications so a good solution would be useful. Many different crossover and mutation operators have been devised for the traveling salesman problem and each give different results. We compare these results and find that operators that use heuristic information or a matrix representation of the graph give the best results.

The Time-Dependent Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem, where the cost for travel between two nodes is dependent on the nodes and their position in the tour. Inequalities for the Asymmetric TSP can be easily extended to the TDTSP, but the added time information can be used to strengthen these inequalities. We look at extending the Lifted Cycle Inequalities, a large family of inequalities for the ATSP. We define a new inequality, the Extended Cycle (X-cycle) Inequality, based on cycles in the graph. We extend the results of Balas and Fischetti for Lifted Cycle Inequalities to define Lifted X-cycle Inequalities. We show that the Lifted X-cycle Inequalities include some inequalities which define facets of the submissive of the TDTS Polytope.

published_or_final_version / Mathematics / Master / Master of Philosophy

The Time-Dependent Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem, where the cost for travel between two nodes is dependent on the nodes and their position in the tour. Inequalities for the Asymmetric TSP can be easily extended to the TDTSP, but the added time information can be used to strengthen these inequalities. We look at extending the Lifted Cycle Inequalities, a large family of inequalities for the ATSP. We define a new inequality, the Extended Cycle (X-cycle) Inequality, based on cycles in the graph. We extend the results of Balas and Fischetti for Lifted Cycle Inequalities to define Lifted X-cycle Inequalities. We show that the Lifted X-cycle Inequalities include some inequalities which define facets of the submissive of the TDTS Polytope.

No description available.

Thesis (M. Phil.)--University of Hong Kong, 2000. / Includes bibliographical references (leaves 112-117).

Thesis (M.S.)--Rochester Institute of Technology, 2006. / Typescript. Includes bibliographical references (leaves [70]-72).

Thesis (Ph. D.)--University of Missouri-Columbia, 2006. / The entire dissertation/thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file (which also appears in the research.pdf); a non-technical general description, or public abstract, appears in the public.pdf file. Title from title screen of research.pdf file (viewed on August 10, 2007) Vita. Includes bibliographical references.

University, Diss., 2001--Saarbrücken.