Institute of Computing and Cybersystems (ICC) Blog

Day: February 11, 2021

Student Town Hall Meetings Scheduled for Feb. 23 and Feb. 25

Published
By

College of Computing Dean Dennis Livesay will host two 60-minute virtual Town Hall meetings for College undergraduate and graduate students on February 23 and February 25, 2021.

At the Town Hall meetings, student are invited to share with Dean Livesay their thoughts and input about the College, curriculum, degree programs, departments, and other topics of interest.

The Undergraduate Town Hall is February 23, 2021, from 4:00 to 5:00 p.m. Join that meeting here: https://michigantech.zoom.us/j/87889920742.

The Graduate Town Hall is February 25, 2021, from 4:00 to 5:00 p.m. Join here: https://michigantech.zoom.us/j/82512917783.

Continue Reading →

Vijay Garg, UT Austin, to Present Lecture Feb. 19, 3 pm

Published
By

This lecture has been canceled.

Dr. Vijay Garg, University of Texas Austin, will present a lecture on February 19, 2021, at 3:00 p.m. The lecture is hosted by the Department of Computer Science.

Vijay Garg Bio

Vijay Garg is a Cullen Trust Endowed Professor in the Department of Electrical & Computer Engineering at The University of Texas at Austin. He received his Ph.D. in computer science at the University of California at Berkeley and B. Tech. in computer science at IIT, Kanpur.

His research interests are in distributed computing, discrete event systems and lattice theory. He is the author of “Elements of Distributed Computing” (Wiley, 2002), “Introduction to Lattice Theory with Computer Science Applications” (Wiley, 2015), and “Modeling and Control of Logical Discrete Event Systems” (Springer, 2012). He is an IEEE Fellow.

Lecture Title

Applying Predicate Detection to Discrete Optimization Problems

Lecture Abstract

We present a method to design parallel algorithms for the constrained combinatorial optimization problems. Our method solves and generalizes many classical combinatorial optimization problems including the stable marriage problem, the shortest path problem and the market clearing price problem.

These three problems are solved in the literature using Gale-Shapley algorithm, Dijkstra’s algorithm, and Demange, Gale, Sotomayor algorithm. Our method solves all these problems by casting them as searching for an element that satisfies an appropriate predicate in a distributive lattice. Moreover, it solves generalizations of all these problems — namely finding the optimal solution satisfying additional constraints called lattice-linear predicates.

For stable marriage problems, an example of such a constraint is that Peter’s regret is less than that of Paul. Our algorithm, called Lattice-Linear Predicate Detection (LLP) can be implemented in parallel with without any locks or compare-and-set instructions. It just assumes atomicity of reads and writes.

In addition to finding the optimal solution, our method is useful in enumerating all constrained stable matchings, and all constrained market clearing price vectors. The talk is an extended version of a paper that appeared in ACM SPAA’20.

Continue Reading →