Millburn HS senior Alex Lin, Intel Science Talent Search finalist
Millburn High School senior Alexander Lin was named as one of 40 national finalists in the Intel Science Talent Search 2015, a program of Society for Science & the Public. Lin is one of four students from New Jersey to attain finalist status this year, according to Millburn School District spokeswoman Nancy Dries.
Finalists receive an all-expenses-paid trip to Washington, D.C. from March 5-11, where they will undergo final judging, display their work to the public, meet with notable scientists, and compete for $1,012,500 in awards, including the three top awards of $150,000 each, said Dries.
Read more about Alex’s achievement:
These finalists were chosen from the select pool of 300 high school seniors named semifinalists in the Intel Science Talent Search 2015 on January 7, and more than 1,800 entrants based on the originality and creativity of their scientific research, as well as their achievement and leadership both inside and outside the classroom.
As one of this year’s 300 semifinalists Lin and Millburn High School were awarded $1,000 each.
This year’s Finalist projects are distributed among 17 categories, including animal sciences, behavioral and social sciences, biochemistry, bioengineering, bioinformatics and genomics, chemistry, computer science, earth and planetary science, engineering, environmental science, materials science, mathematics, medicine and health, microbiology, physics, plant science, and space science.
Lin’s project is titled, Approximating the Maximum k-Colorable Subgraph Problem on Dotted Interval Graphs (See abstract attached below.) Lin was named a semifinalist in the 2014 Siemens Competition in December.
Lin’s research has been done under the auspices of Millburn High School’s Authentic Science Research course, a three-year program that begins in the sophomore year, and is designed to offer students an opportunity to perform scientific research and participate in the community of science research and scholarship as part of their high school experience. After identifying a research topic, and obtaining a mentor at an outside university or research lab, students must write a 20-page scientific paper and enter their research into local, state and/or national competitions. The course is taught by Dr. Paul Gilmore and Ms. Gina Cocchiaro.
Alex Lin and Dr. Gilmore will be recognized at the February 9 Board of Education meeting. Alex Lin may be reached by email at alin5250@gmail.com.
More information about the Intel Science Talent Search program may be found here: https://www.societyforscience.org/
ABSTRACT
Approximating the Maximum k-Colorable Subgraph Problem on Dotted Interval Graphs
A fundamental problem that arises in many real world applications is how to divide a collection of objects into a set number of groups, while adhering to restrictions on certain objects being in the same group. For instance, in the airline industry, companies look to assign their various flight trips to airplanes with the obvious constraint that one airplane cannot make two simultaneous trips. At universities, professors attempt to schedule their exams in time slots such that no student will have exams from two of his classes being administered at the same time.
This universal problem, known as MAXIMUM k-COLORABLE SUBGRAPH in theoretical computer science, has applications in the natural sciences, scheduling, business, entertainment, and broadcasting. Previous literature essentially showed that there is no hope in designing a reasonably accurate and fast algorithm for this problem using simple graphs, the traditional mathematical model for optimization problems of this nature. Thus, we moved the problem to dotted interval graphs, a newly invented interface that has experienced success in algorithm design for other notoriously difficult problems.
The first result of the paper proved that there does not exist an algorithm that can solve MAXIMUM k-COLORABLE SUBGRAPH using dotted interval graphs to an accuracy of 100% unless a famous conjecture that is generally presumed to be false is actually true. Next, we present an algorithm that can produce approximate solutions, or solutions that are not optimal but decently close, for MAXIMUM k-COLORABLE SUBGRAPH on dotted interval graphs. We then mathematically prove that this algorithm is always guaranteed to return solutions that are at most a certain threshold away from optimum, even in the worst case. Finally, we give a second algorithm that can convert any dotted interval graph into an equivalent simple graph that holds the same information, because although the dotted interval graph is more suitable for solving hard problems, the solution is more useful to industry through the clarity of the simple graph. The paper concludes with a detailed biological application of our work to show how our results can be used in the real world.
