Hung Le Receives NSF CAREER Award for Work on Graph Theory Algorithms
Content
Manning College of Information and Computer Sciences (CICS) Assistant Professor Hung Le has received an NSF CAREER award of $655,466 for his project to advance the theoretical understanding of topological graphs, which appear in many practical applications, including logistics and planning, very large-scale integration design, image processing, and robot navigation.
Topological graphs have what Le calls “nice structures” with few or no edge crossings, where links between vertices in the graph are forced to intersect. According to Le, research on the structures of topological graphs has produced powerful algorithmic techniques over the past two decades, but current techniques are reaching their limits. His goal is to develop a new class of techniques inspired by geometry counterparts that will break through the limits of the existing ones. These geometrical techniques, according to Le, may provide breakthroughs for algorithms attempting to solve problems that are currently considered to be among the most difficult—such as the k-center problem, used to optimize the placement of network nodes or facilities, or the vehicle routing problem used in ride-sharing and logistic applications.
“Topology is very flexible, while geometry is very rigid,” explains Le. “This makes topology a great tool for modeling graphs, but its flexibility comes with a cost—it is very difficult for people to understand topology and solve problems in topological graphs. On the other hand, while people have been studying geometry for millennia—and are really good at understanding and solving geometric problems—geometry lacks the flexibility to model the graphs that are needed for real-world applications.”
Le proposes to begin by studying the geometry of the shortest path distances between vertices in a topological graph and extracting “geometrical features” from these paths. Once these features are found, they can be applied to solve algorithmic problems using ideas from computational geometry—in the final result, developing a new class of algorithm design techniques.
“This approach will get us the best of both worlds—topology and geometry—using the flexibility of topology to model practical graphs, and the power of geometry to solve algorithmic problems in these graphs,” says Le.
Le’s project also outlines plans to disseminate these new state-of-the-art algorithm design techniques, and to train graduate and undergraduate students on them. He has previously introduced graph algorithms to high school students from underserved communities through the Massenberg Summer STEM Institute, hosted at UMass Amherst.
Le joined the faculty of CICS in 2020, and is affiliated with the UMass Theory Group. His main research focus has been on designing algorithms for graph problems, particularly in understanding the power and limits of structures of graphs in algorithm design. Previously, he was a PIMS postdoc in computer science at the University of Victoria, Canada. He received his doctorate in computer science from Oregon State University and a bachelor’s in computer science from Hanoi University of Science and Technology.
