4/8/2016 Emily Scott
Researchers at ISE are looking at complex problems emerging from new Internet markets — some of which are in the early stages of analysis.
Written by Emily Scott
Researchers at ISE are looking at complex problems emerging from new Internet markets — some of which are in the early stages of analysis. This is the case for Jugal Garg, who joined ISE faculty as a research assistant professor in the spring of 2016.
With his research background being at the intersection of economics and computation, Garg is investigating many different markets and the computation and complexity questions arising from them.
“My work is more towards designing simple and fast algorithms for computing equilibrium prices in various market models, which is pivotal for predictions and policy analysis,” Garg said. “(It’s) more applying the mathematical techniques to the underlying optimization problems.”
In one of his current research projects, Garg is looking to figure out ways to manage cloud markets, a multi-billion dollar market that is growing at a rapid pace. Cloud markets involve storing data and performing various computation tasks remotely.
The challenge here is to design mechanisms for pricing and scheduling these resources in order to be efficient and fair. These relatively new markets also differ greatly from traditional markets.
“For the cloud, it is a little bit different than going to shop at a grocery store. In a grocery store, you see the prices and you buy whatever you like in a quantity you can afford,” Garg said. “But in the cloud space, you want to complete a task that requires five gigabytes of memory or two gigahertz of processing power. So customers specify their requirements on resources or just the tasks they wish to perform, and the service has to make sure all the requirements are fulfilled, in addition to pricing and scheduling.”
Specifying the explicit requirement first is what makes the cloud market different, and is also why the market requires a different approach, according to Garg.
“There is no theoretical understanding of what is a ‘good’ mechanism and what is the best way to sell these resources,” he said. “Currently I am working on designing a market-based mechanism for allocating these resources, and we have some success of a basic model that we want to expand.”
What interests Garg about this type of problem is the fact that it’s new, it’s huge in terms of potential impact, and it’s challenging due to a combination of both scheduling and market based issues which makes it not amenable to traditional models.
“This is the first time we are proposing a model for cloud computing based on the basic tenets of general equilibrium theory,” he said.
Another area of Garg’s research is network flow problems that arise when moving materials through a system. He hopes to design efficient algorithms that can compute solutions faster for problems that have eluded researchers for decades. These problems involve complex functions which make them very challenging.
The need for fast algorithms is becoming more important, especially in the era of big data.
“Earlier, the problem size was very small. Now, it has become huge,” Garg said. “There is so much data. So you need fast algorithms, even though the processing power capability is increasing, because data is increasing at an even faster rate, and . . . we need a fast response.”
On the other hand, sometimes the problem turns out to be inherently difficult, so Garg said it is also important to look at problems from a complexity theory perspective.
“I also study the complexity of a problem; whether there could be an efficient algorithm or not,” Garg said. “In spite of trying very hard, you’re not able to get an efficient algorithm, so it could mean that an efficient algorithm may not exist.”
Garg said that in his career, he hopes to find answers for these challenging and important problems that affect the optimization community at large.
“I want to model and analyze new phenomenon arising on the Internet as well as solve problems that have challenged us for decades. That’s why I’m here.”