Please use this identifier to cite or link to this item:
http://hdl.handle.net/10267/16556
Title: | A Set Partition Analog of the Erd os-Szekeres Theorem |
Authors: | Liu, Rui |
Keywords: | Text;Honors papers;Student research;Mathematics and Computer Science, Department of |
Issue Date: | May-2013 |
Publisher: | Memphis, Tenn. : Rhodes College |
Abstract: | The monotonic subsequence problem has been studied in depth. Mathematicians and theoretical computer scientists have found and proved various results such as the Erd os-Szekeres Theorem and have studied algorithms to fi nd longest monotonic subsequences. The objective of my project is to establish the counterparts of the results mentioned above in the context of set partitions, namely the heaviest free subpartition problem. More speci cally, I introduce concepts such as "subpartition", "freeness" and other related terms to formulate the free subpartition problem. Then, I discuss various representations of the problem and evaluate the relationship between this problem and other widely studied algorithmic problems. Finally, I analyze the di fficulties we encountered and present a "greedy" algorithm that approximates the optimal solution. |
Description: | Permission to publish this work was granted by the author. The paper was submitted to the Archives on CD. |
URI: | http://hdl.handle.net/10267/16556 |
Appears in Collections: | Honors Papers |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Liu_Rui_Honors_2013.pdf | 341.67 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.