Associate Professor of Mathematics Sally Cockburn presented a paper at MathFest, the summer meeting of the Mathematical Association of America on Aug. 12 in Knoxville. The paper, titled "Deranged Socks," was joint work with former visiting professor Joshua Lesperance, and grew out of a problem from Cockburn's junior-level graph theory and combinatorics course. Specifically, given n distinct pairs of socks, how many ways are there to distribute 2 socks to each of n people so that no one receives a matching pair? Like many combinatorial problems, it is easy to state, but remarkably difficult to solve.
Cockburn also recently published an article in the online version of the journal Mathematical Programming, titled "On the domino-parity inequalities for the STSP", which was joint work Dr. Sylvia Boyd of the University of Ottawa and Danielle Vella. The paper looks at a new approach for solving the famous Traveling Salesperson Problem, in which a salesman wants to find the shortest route for visiting each of n cities exactly once and returning home.
Also, a paper Cockburn wrote with Dr. R. Bruce Mattingly of SUNY Cortland and Dr. Ben Coleman and Dr. Kay Somers, both of Moravian College, titled "Some Problems are NP-Harder than Others," was published this summer as part of the NSF's DIMACS (Center for Discrete Mathematics and Computer Science) Educational Module Series. The module presents the results of recent results on the computational complexity of a pair of classic optimization problems in graph theory, the dominating set problem and the vertex cover problem. Although both are theoretically intractable in general for large instances, the latter can be solved in a reasonable amount of time for all cases that arise in practical settings.
Cockburn also recently published an article in the online version of the journal Mathematical Programming, titled "On the domino-parity inequalities for the STSP", which was joint work Dr. Sylvia Boyd of the University of Ottawa and Danielle Vella. The paper looks at a new approach for solving the famous Traveling Salesperson Problem, in which a salesman wants to find the shortest route for visiting each of n cities exactly once and returning home.
Also, a paper Cockburn wrote with Dr. R. Bruce Mattingly of SUNY Cortland and Dr. Ben Coleman and Dr. Kay Somers, both of Moravian College, titled "Some Problems are NP-Harder than Others," was published this summer as part of the NSF's DIMACS (Center for Discrete Mathematics and Computer Science) Educational Module Series. The module presents the results of recent results on the computational complexity of a pair of classic optimization problems in graph theory, the dominating set problem and the vertex cover problem. Although both are theoretically intractable in general for large instances, the latter can be solved in a reasonable amount of time for all cases that arise in practical settings.
