Volume 13

DOI: 10.1137/20S1355549

Authors

Arjun Kodialam (Marlboro High School)

Project Advisors

T.V. Lakshman (Nokia Bell Labs)

Abstract

We consider the problem of allocating resources to meet an uncertain demand. There are well studied approaches to solve this problem when distributional information is known about the demand. We consider this resource allocation problem when we lack information about the statistics of the demand. These types of resource allocation problems, where there is only minimal information available about the demand, arises naturally in many instances. The motivation for studying this problem is the allocation of resources (testing kits, masks) for pandemic control. While resources are being allocated, there is only minimal information known about the demand size. Decision makers have to solve some version of the Caterer’s problem when making advance reservation of resources (processing, storage) in the cloud for new applications. We develop deterministic and randomized competitive algorithms for the Caterer’s problem. Unlike the closely related online Ski-rental problem, the Caterer’s problem does not satisfy the principle of equality and this makes the Caterer’s problem more challenging. We prove the optimality of the randomized algorithms by using Yao’s Lemma and developing matching lower bounds for the problem.

DOI: 10.1137/20S1340460

Authors

Zijie Zhou (Purdue University)

Project Advisors

Jonathon Peterson (Purdue University)

Abstract

In `J. Schwenk.(2018) [3] What is the Correct Way to Seed a Knockout Tournament? Retrieved from The American Mathematical Monthly' , Schwenk identified a surprising weakness in the standard method of seeding a single elimination (or knockout) tournament. In particular, he showed that for a certain probability model for the outcomes of games it can be the case that the top seeded team would be less likely to win the tournament than the second seeded team. This raises the possibility that in certain situations it might be advantageous for a team to intentionally lose a game in an attempt to get a more optimal (though possibly lower) seed in the tournament. We examine this question in the context of a four team league which consists of a round robin \regular season" followed by a single elimination tournament with seedings determined by the results from the regular season [4]. Using the same probability model as Schwenk we show that there are situations where it is indeed optimal for a team to intentionally lose. Moreover, we show how a team can make the decision as to whether or not it should intentionally lose. We did two detailed analysis. One is for the situation where other teams always try to win every game. The other is for the situation where other teams are smart enough, namely they can also lose some games intentionally if necessary. The analysis involves computations in both probability and (multi-player) game theory.

DOI: 10.1137/19S1300534

Authors

Qinyi Chen (UCLA), Andrea Boscovik (Amherst College), Dominik Kufel (University College London), Zijie Zhou (Purdue University)

Project Advisors

Anna Ma (UCLA)

Abstract

In order for an e-commerce platform to maximize its revenue, it must recommend customers items they are most likely to purchase. However, the company often has business constraints on these items, such as the number of each item in stock. In this work, our goal is to recommend items to users as they arrive on a webpage sequentially, in an online manner, in order to maximize reward for a company, but also satisfy budget constraints. We first approach the simpler online problem in which the customers arrive as a stationary Poisson process, and present an integrated algorithm that performs online optimization and online learning together. We then make the model more complicated but more realistic, treating the arrival processes as non-stationary Poisson processes. To deal with heterogeneous customer arrivals, we propose a time segmentation algorithm that converts a non-stationary problem into a series of stationary problems. Experiments conducted on large-scale synthetic data demonstrate the effectiveness and efficiency of our proposed approaches on solving constrained resource allocation problems.

DOI: 10.1137/20S1335091

Authors

Christiana Guan (Pine View School, Osprey, FL), Michael Gutierrez (Pine View School, Osprey, FL), Pragnya Govindu (Pine View School, Osprey, FL), Nicholas Butakow (Pine View School, Osprey, FL), Kristoffer Selberg (Pine View School, Osprey, FL)

Project Advisors

Mark Mattia (Pine View School, Osprey, FL)

Abstract

In the past century, as energy usage rapidly increased and fossil fuel consumption and carbon emissions have increased along with it, transportation has accounted for a large share of this. With e-commerce and delivery increasing in popularity and trucks accounting for around a third of transport-related carbon emissions and 20% of the global demand for oil [1], it is important to evaluate more energy-efficient and sustainable alternatives. One example of such is using electricity powered semi-trucks instead of semi trucks fueled by diesel. Multiple companies are already in the process of producing electric semi-trucks including Freightliner and Tesla, whose electric semis are supposed to enter production this year. Transitioning to electric semi-trucks could help with both reducing the environmental impact of trucks and reducing the total operating cost in the long run.

DOI: 10.1137/20S131494X

Authors

Akash Anickode (Arizone State University)

Project Advisors

Abba Gumel (Arizona State University)

Abstract

Malaria, a deadly infectious disease caused by the Plasmodium parasite, remains a major public health challenge in many parts of the world. It causes over 200 million cases and 500,000 fatalities globally each year. There is now a global effort, spearheaded by the World Health Organization and the Bill and Melinda Gates Foundation, to eradicate the disease by 2040. These efforts are primarily based on the large-scale use of insecticide based control measures against the adult female Anopheles mosquito (the malaria vector in humans). This project is based on the use of a basic compartmental model for malaria transmission dynamics to assess various anti-malaria control strategies. The disease-free equilibrium of the model is shown to be locally-asymptotically stable when a certain threshold quantity is less than unity. Furthermore, this equilibrium is globally-asymptotically stable for the special case with no malaria mortality in the human population. Numerical simulations of the model show that the use of a vaccine as a sole anti-malaria strategy may not lead to the elimination of malaria in malaria-endemic setting. However, the study shows that combining vaccination with other vector management strategies (notably insecticide-based mosquito reduction strategies), can lead to such elimination. It is shown that the prospects for the global malaria eradication by 2040 are very promising if the extended vector management strategies (which entails the use of a vaccine together with the insecticide-based mosquito reduction strategies) is implemented at moderate level of effectiveness.

DOI: 10.1137/19S1282015

Authors

William Melville (Brigham Young University)

Project Advisors

Sean Warnick (Brigham Young University)

Abstract

This paper describes the process used to create two different models to define the intrinsic value of a batted ball. The first model, which was originally created by Dr. Glenn Healey, maps a batted ball's speed, vertical angle, and horizontal angle to an intrinsic value. This first model has the property that above average runners tend to be underrated and below average runners tend to be overrated by the intrinsic value. Thus, the second model described in this work attempts to address this property by including the batter's sprint speed in the mapping to an intrinsic value. A visual representation of the first mapping called the wOBA cube is presented as well as a visual representation of the second mapping called the wOBA tesseract. The mean absolute deviation between the intrinsic statistic and the outcomes-based statistic is used to compare the accuracy of both intrinsic values, and it is determined that the sprint speed intrinsic value is at least as accurate as the non-sprint speed intrinsic value. The two intrinsic statistics' reliabilities are compared using Cronbach's alpha, and it is determined that they are similarly reliable and that they are both more reliable than the outcomes-based statistic. Finally, the ten most under and overrated players, in terms of the difference between their outcomes-based statistic and their intrinsic statistic, are identified for both intrinsic statistics, and it is determined that the sprint speed intrinsic value underrates fast runners and overrates slow runners less frequently than the non-sprint speed intrinsic value.

DOI: 10.1137/20S1316263

Authors

Marie Neubrander (University of Alabama)

Project Advisors

Roger Sidje (University of Alabama)

Abstract

Often, given a system of biochemical reactions, it is useful to be able to predict the system's future state from the initial quantities of the involved molecules. There are methodologies for developing such predictions, ranging from simple approaches such as Monte Carlo simulations to more sophisticated higher-order tensors and stochastic automata networks. Many revolve around solving the chemical master equation that arises in the modeling of the underlying biochemical kinetics. This work considers the case of dealing with the resulting high-dimensional data and shows how tensor representations allow us to cope with the \curse of dimensionality" that significantly complicates such problems. A key outcome in this work is the demonstration of the inherent differences and similarities between two prominent modeling methods, by computational examples on one hand and a mathematical proof on the other hand. Applications where biochemical reactions occur are found in a variety of scenarios, including enzyme kinetics and genetics. Tensor-based solutions may have applications in dealing with many other high dimensional data outside of strictly chemical reaction systems.

DOI: 10.1137/19S1308475

Authors

Jack Hughes (University of Guelph)

Project Advisors

Herman Eberl (University of Guelph)

Abstract

We derive a mathematical model for biofilm growth on a degradable substratum. The starting point is the one-dimensional Wanner-Gujer biofilm model. The processes included are diffusion of a dissolved growth controlling substrate into the biofilm, cell lysis, detachment of biomass, and growth from substrate conversion and substratum degradation. The resulting model is a system of two non-linear ordinary differential equations, the evaluation of the right-hand side of which requires the solution of a semi-linear two-point boundary value problem. We perform standard analysis from the existence and uniqueness of solutions to equilibrium and stability analysis. Finally, we study our model through numerical simulations and investigate how biofilms evolve on degradable substratum. We find in our setting that the addition of substratum degradation has no effect on the long-term behaviour of the biofilm, but does affect the transient behaviour.

DOI: 10.1137/19S1280211

Authors

Luciano Vinas (University of California, Berkeley)

Project Advisors

Atchar Sudhyadhom (University of California, San Francisco)

Abstract

We explore the effects of interleaved shuffling on the rate of convergence for the discrete heat equation with Dirichlet boundary conditions. We derive a closed form for the expected value of the shuffled discrete heat equation and establish bounds on its rate of convergence. In particular for any connected region D _ Zd with volume jDj and a non-negative initial state h0 2 RjDj, there is an upper bound on the spectral radius associated with the shuffled discrete heat equation that grows on the order of 1 (1=jDj1=d). An analogous lower bound for the standard discrete heat equation is also derived which grows on the order of 1O(1=jDj2=d).

DOI: 10.1137/18S017302

Authors

So Mang Han (St. Olaf College), Taylor Okonek (St. Olaf College), Nikesh Yadav (St. Olaf College), Xiaojun Zheng (St. Olaf College)

Project Advisors

Matthew Wright (St. Olaf College)

Abstract

Topological data analysis seeks to discern topological and geometric structure of data, and to understand whether or not certain features of data are significant as opposed to random noise. While progress has been made on statistical techniques for single-parameter persistence, the case of two-parameter persistence, which is highly desirable for real-world applications, has been less studied. This paper provides an accessible introduction to two-parameter persistent homology and presents results about matching distance between 2-parameter persistence modules obtained from families of simple point clouds. Results include observations of how differences in geometric structure of point clouds affect the matching distance between persistence modules. We offer these results as a starting point for the investigation of more complex data.

DOI: 10.1137/19S128274X

Authors

Amy Ngo (Rensselaer Polytechnic Institute)

Project Advisors

Dr. Richard Moeckel (University of Minnesota)

Abstract

In this paper, we aim to develop models of the action potentials of healthy human myocardial and pacemaker cells using the periodically forced Fitzhugh-Nagumo system. Pacemaker cells generate impulses which cause myocardial cells to contract, producing a heartbeat. Such impulses both cause and result from changes in membrane potential. Using eigenvalue stability analysis and the Hopf Bifurcation Theorem, we determined ranges of the two constants intrinsic to the system and the forcing amplitude for which the system has a unique, stable limit cycle. From simulations in MATLAB, we discovered that at forcing amplitudes near and greater than the maximum value which induces the limit cycle, the square wave and the cosine wave forced systems describe the behaviors of myocardial and pacemaker action potentials, respectively, with high fidelity.

DOI: 10.1137/19S019073

Authors

Aidan Bowman (Socrates Preparatory School, Casselberry, FL), Jonathan H. Yu (Homeschooled)

Project Advisors

Dr. Neal Gallagher (Socrates Preparatory School Casselberry, FL), Kristina Vuong (Socrates Preparatory School Casselberry, FL)

Abstract

Multiple methods are brought together here. Change of base transformation for fractions, continued products, mixed radix representations, the binary Spigot Algorithm, and repeating decimals are all used to compute a million binary digits of π, and to investigate interesting properties of repeating decimals in arbitrary bases. An Excel spreadsheet utilizes the Spigot algorithm to compute binary digits of π. A Java program listing is also included that can be used to compute a million binary digits of π.

DOI: 10.1137/19S017621

Authors

Jacob Householder (Whittier College)

Project Advisors

Fredrick Park (Whittier College)

Abstract

Image segmentation is the task of finding salient regions of importance in an image. In this work, we take a curve evolution approach to this problem where we deform an initial curve in the inward normal direction with the objective of finding the boundaries of objects in an image. To achieve this, we propose a variational image segmentation model that incorporates a clique based shape signature with a geodesic active contours energy. The model scheme consists of evolving a parametric representation of an active contour to minimize the penalty that the model induces. This penalty is minimized when the curve is on the boundaries of objects in the image, areas with sudden change in pixel intensity i.e. light to dark. We demonstrate successful capture of illusory contours, segmentation of objects in a cluttered background, and segmentation of occluded objects.