August 28, 2012: Congratulations to CS Prof. Bhaskar DasGupta on two new NSF grants for $556,000

Congratulations to UIC Computer Science Professor Bhaskar DasGupta on the receipt of two new National Science Foundation grants, and to his co-PIs on one of them, Computer Science Professor Ouri Wolfson and Civil Engineering Professor Jane Lin.


Grant 1:
Novel Algorithmic Tools For Analysis of Biological and Social Networks
$356,222 over three years; sole PI Prof. DasGupta
The overall project is joint work with R?ka Albert of Pennsylvania State University, with total funding of about $629,000.

Grant 2:
Dynamic Parking Assignment Games
Total grant amount: $200,000
PI: Bhaskar DasGupta, (CS, UIC)
Co-PI: Ouri Wolfson (CS, UIC), Jane Lin (Civil Eng., UIC)


Tools for analysis:
In this funding for my Laboratory for Creative Algorithms, I will design and apply novel algorithmic tools to explore several fundamental graph-theoretic problems that have significant applications in biological and social interaction networks. The research problems that I will address can be broadly classified into graph partitioning type of problems and graph sparsification type of problems. For example, one such problem in the context of social interaction networks is to partition the nodes into so-called ?communities of statistically significant interactions? to study the behavioral patterns of a group of individuals in a society. I will formulate precise computational problems, study their properties, use novel algorithmic tools to design efficient algorithms, and implement the resulting algorithms to test their accuracy and efficiency. The proposed research will leverage further development of novel combinatorial tools previously developed by me, in addition to developing new techniques, to design efficient algorithms for complex optimization problems. The algorithms developed in the course of this project will be implemented for validation on simulated and real data, and will lead to open-source software for the life science and social science communities.

On a broader level, since this proposal deals with fundamental combinatorial optimization problems that arise in diverse scientific fields, the proposed research will have a strong impact on research areas beyond the primary research area, such as in stability analysis of computer networks and in social network visualization. A central component of the proposal is the creation of meaningful educational activities that leverage the proposed interdisciplinary research and build on my substantial past experience in teaching, mentoring and outreach and on the diverse communities in Chicago. Additionally, I plan to integrate research and education via course and curriculum development, involvement of undergraduates, minorities and ?under-represented groups, effective dissemination of research, mentoring of undergraduate and graduate students, outreach and community involvement, and promoting diversity in research and educational activities.

The outcomes of the project will be made freely available through the websites of the Laboratory for Creative Algorithms:


Parking Games:
Finding parking has been a major hassle for drivers in many urban environments for decades. For example, studies conducted in 11 major cities revealed that the average time to search for curbside parking was 8.1 minutes and cruising for these parking spaces accounted for 30% of the traffic congestion in those cities, on an average. Thus, in the above case, each parking slot generated 4,927 vehicle miles traveled (VMT) per year, and of course the overall traffic is considerable since it is obtained by multiplying this number by the number of parking slots in the city. For example, in a city like Chicago with over 35,000 curbside parking slots, the total number of VMT becomes approximately 170 million VMT per year due to cruising while searching for parking. Furthermore, this would account for waste of over 8.3 million gallons of gasoline and over 129,000 tons of carbon di-oxide emissions. Motivated by these factors and enabled by the current revolution in pervasive, wireless, sensor and mobile computing, in this interdisciplinary project involving researchers from Computer Science and Civil Engineering departments of the University of Illinois at Chicago (UIC) the PIs propose to investigate a number of core algorithmic, game-theoretic, and computational complexity issues to address parking slot selection problems. This project seeks to make the urban transportation system more efficient, thus addressing the following crisis situation. On average, people traveling during morning and evening rush hours in urban areas experience 41 hours of delay annually in 2007. Between 1990 and 2007, VMT grew 41%, and the projected total VMT in 2050 is 4,834 billion miles, an increase of 60% over 2007.

The technical merits of the proposal include the investigation and analysis of real-time distributed competition for spatial resources. The competitive nature of the problem imposes a dynamic multi-player game-theoretic framework. The investigators will formulate computational problems, study their mathematical properties, design efficient algorithms for them and implement resulting algorithms to test accuracy and efficiency issues. In particular, partly inspired by Newton's laws of gravitation, the investigators will research a broad class of parking navigation strategies loosely termed as the Gravitational Parking Paradigms. The final goal of this project is to develop the theoretical underpinnings of applications that, given the locations of parking slots, will guide a driver to a most appropriate parking slot. Other components of the project include the integration of research and education via several means such as course and curriculum development, effective dissemination of research, mentoring undergraduate and graduate students as well as promoting diversity in related research and educational activities.

Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF