Computer Science Research Profile:
In Search of a Simple Solution
From Threads, Spring 2009 issue
Kamesh Munagala wants nothing more than to simplify. At first glance, it seems like a strange goal for a mathematician/ computer scientist who specializes in the design and analysis of algorithms for NP- hard combinatorial optimization problems. But while Munagala’s research has one foot in the theoretical, the other is grounded in the practical—the application of models and algorithms to databases, computer and sensor networks, and e-commerce.
Many emerging applications, such as Internet advertising and wireless transmissions, present difficult decision problems, called stochastic control problems, in which solving for an exact solution would take exponential time or space. So much time and space, in fact, that the attempt is prohibitive. This is referred to as “the curse of intractability.” Researchers in operations and control theory have tackled such problems, but Munagala is addressing them from a new direction: “We propose to look at the same problems, but from the lens of approximation algorithms,” he says.
Approximation algorithms are computational methods that trade perfection for efficiency: A good solution that can be found in a day is better than an ideal solution that requires a month of processing. Such algorithms are valuable when efficiency takes precedence over exactness, as in many modern computing infrastructures. But simply designing algorithms to ease the strain of computing isn’t enough, Munagala believes. There is a second step: proving that the performance of the designed algorithm will be close to optimal. The algorithm must prove its mettle. This is often the hard part, says Munagala, but it’s vital to the process. “Both are tied together—the process of proving an algorithm is close to optimal gives more insights into what the correct algorithm itself should be.”
With support from a NSF CAREER Award (see page 2), Munagala is currently focused on unraveling problems of allocating resources, such as time or money, when there is uncertainty, such as gaps in information. Using the time-honored ‘multi-armed bandit’ approach, a model for studying systems with inherent trade-offs, Munagala is currently investigating two applications: Internet bidding and wireless networks.
Advertisers on Google or Yahoo! bid on keywords so that when a user searches for the keyword, the advertisement pops up on the screen. Faced with a limited budget (the resource), advertisers must decide which keywords to pay for despite limited knowledge (the uncertainty) about whether likely users of that keyword will actually click the advertisement. For example, the keyword “mortgage” may result in twice the number of clicks than the keyword “home.” How does an advertiser allocate its budget among several keywords? Working with PhD candidate Sayan Bhattacharya, Munagala hopes to simplify the problem and design a model to solve it. Munagala plans to confer with employees at Google and Yahoo! about the model design and what company policies might need to be incorporated.
Munagala is also collaborating with researchers in ecology and statistics, as well as Professors Jun Yang and Pankaj Agarwal, on a variety of wireless network decision problems. In general, a single wireless node has the option of a variety of channels that can be used for transmission, like exits on and off a freeway. But traffic among channels may vary widely and randomly change over time. To maximize its transmission rate, a node confronts the trade-off between sticking to a channel with a high rate and updating its information about the other channels in case the initial channel begins to slow. But to gather information on the other channels, it must stop transmitting on the currently high rate channel and transmit on the alternate channels. “This leads to a ‘chicken-and- egg’ issue,” says Munagala. “The decision to transmit not only influences the current rate, but also what information is available to make decisions in the future.” It’s a classic decision problem, one for which a practical solution would be beneficial to a variety of network applications.
“The focus of approximation algorithms is to simplify,” says Munagala. “Instead of looking at problems in their full complexity, you try to find the most simple structure in the problems. If you analyze that structure, it gives you insights into what is going on in the process.”