Carnegie Mellon University

Summer Undergraduate Applied Mathematics Institute

May 26 - July 21, 2015

Projects

► Giuga Ideals, Duncan Gichimu, Kerrek Stinson (download paper)

Advisor:  Greggo Johnson
Abstract: In 1950, Giussipe Giuga conjectured that an integer $n$ satisfies $\sum\limits_{k=1}^{n-1} k^{n-1} \equiv -1 \pmod{n}$ if and only if $n$ is prime. Sixty-five years later and this problem is yet to be solved. The complexity of working in the integers has indeed proven challenging.

To explore this problem further, we consider the Generalized Giuga Conjecture for ideals in number rings. We introduce the idea of correspondence between weak Giuga numbers and weak Giuga ideals. These concepts are further developed in the quadratic extensions.

Rose-Hulman Undergraduate Mathematics Journal: Vol. 18 : Iss. 1 , Article 5.

► Ant Colony Optimization Applied to the Bike Sharing Problem, Cashous Bortner, Can Gürkan (download paper)

Advisor:  Brian Kell
Abstract:  In this study, we analyze a single vehicle capacitated pickup and deliv ery problem, namely the bike sharing problem as seen in bike sharing systems around the world. We investigate previous works and formulate our own, novel algorithm for solving the bike sharing problem which is based on an ant colony optimization heuristic. Our algorithm takes into account the total distance traveled, and the distribution of the bikes within the system. We then test our algorithm on random data samples as well as real world data in order to compare our algorithm to other formulations.

Ant Colony Optimization

► Subrings of $\mathbb{C}$ Generated by Angles, Jackson Bahr, Arielle Roth (download paper)

Advisor:  Greggo Johnson
Abstract: In [1], Buhler et al. considered the following scenario. Given a collection $U$ of unit magnitude complex numbers and a set $S$ of constructed points initially containing just $0$ and $1$, through each constructed point draw lines whose angles with the real axis are in $U$. The intersections of such lines are also constructed points. Upon taking the closure we form a set $R(U)$. They investigated which $U$ result in $R(U)$ being a ring.

Our main result holds for when $1 \in U$ and $\vert{U}\vert \ge 4$. We classify $R(U)$ as the set of linear combinations of elementary monomials which are the points constructed in the first step. The coefficients are taken from $Z[P] = R(U) \cap R$ which is easily calculated. We also show that when $\vert{U}\vert \ge 4$, $R(U)$ is dense in the complex plane. Furthermore, we classify $R(U)$ completely for when $1 \in U$ and $\vert{U}\vert \ge 3$, showing that $R(U)$ is a ring whenever one of the points constructed in the first step is a quadratic integer.

Rose-Hulman Undergraduate Mathematics Journal: Vol. 17 : Iss. 1 , Article 2.

► Rainbow Numbers with Respect to $2$-Matchings and $3$-Matchings, Kate Borst, Jüergen Kritschgau (download paper)

Advisor:  Michael Young
Abstract: Our results focus on the rainbow numbers of the various graphs with respect to $M_2$ and $M_3$. We find the rainbow numbers for all graphs with respect to $M_2$. From then on out, the number of troublesome cases increases for rainbow numbers with respect to $M_3$. We prove that the rainbow numbers of trees with a diameter of 6 or greater have $rb(T,M_3)=\Delta +2$. We extend this result to all graphs with diameter 6 or greater.

Our results suggest that $rb(G, M_3)= \Delta +2$ for unconnected graphs $G$; this is an area for further study.

Rainbow Numbers

► Exploring the use of hyper-heuristics to solve a dynamic bike-sharing problem, Emily Myers, Ghofran Shaker (download paper)

Advisor:  Brian Kell
Abstract: In a self-service bike-share system we have a finite number of stations with limited capacity. In any real-world situation, some stations will have more demand than others and will accumulate or lose bikes. The system operator must use vehicles to pick up the bikes from full stations and redistribute them in empty ones. We define the problem and explore a hyperheuristic approach previously used successfully to solve the Vehicle Routing Problem.

bike-sharing problem

Students

  • Bahr, Jackson, Carnegie Mellon University
  • Borst, Katherine, Carnegie Mellon University
  • Bortner, Cashous, University of Nebraska, Lincoln
  • Gichimu, Duncan, Towson University
  • Gürkan, Can, Rensselaer Polytechnic Institute
  • Kritschgau, Jüurgen, Bates College
  • Myers, Emily, Smith College
  • Roth, Arielle, Elizabethtown College
  • Shaker, Ghofran, University of Pittsburgh
  • Stinson, Kerrek, Colorado School of Mines

Group photo

SUAMI Group 2015

Faculty

Handron

Dave Handron, Associate Teaching Professor
Course: Symbolic Programming in Mathematics

E-mail:  handron@andrew.cmu.edu
Wean Hall 6214
412-268-5583

Kell

Dr. Brian Kell, Google Pittsburgh
Course: Combinatorial Optimization

Project Director

E-mail:  bkell@cmu.edu

Johnson

Gregory Johnson, Assistant Teaching Professor

Project Director

E-mail:  greggo@andrew.cmu.edu
Wean Hall 8122
412-268-1504

Young

Michael Young, Assistant Professor, Iowa State University

Project Director

E-mail:  myoung@iastate.edu