Kamesh Munagala

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 9, 2026 In many decision-making scenarios, individuals strategically choose what information to disclose to optimize their own outcomes. It is unclear whether such strategic information disclosure can lead to good societal outcomes. To address this question, we co ... Full text Cite

Fair Multi-Agent Persuasion with Submodular Constraints

Conference Leibniz International Proceedings in Informatics Lipics · June 1, 2026 We study the problem of selection in the context of Bayesian persuasion. We are given multiple agents with hidden values (or quality scores), to whom resources must be allocated by a welfare-maximizing decision-maker. An intermediary with knowledge of the ... Full text Cite

Balanced Spanning Tree Distributions Have Separation Fairness

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2026 Sampling-based methods such as ReCom are widely used to audit redistricting plans for fairness, with the balanced spanning tree distribution playing a central role since it favors compact, contiguous, and population-balanced districts. However, whether suc ... Full text Cite

The Limits of Interval-Regulated Price Discrimination

Conference Lecture Notes in Computer Science · January 1, 2026 In this paper, we study third-degree price discrimination in a model first presented by Bergemann et al. [10]. Since such price discrimination might create market segments with vastly different posted prices, we consider regulating these prices, specifical ... Full text Cite

Metric Distortion of Small-Group Deliberation

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 15, 2025 We consider models for social choice where voters rank a set of choices (or alternatives) by deliberating in small groups of size at most k, and these outcomes are aggregated by a social choice rule to find the winning alternative. We ground these models i ... Full text Cite

Differential Privacy Under Multiple Selections

Conference Leibniz International Proceedings in Informatics Lipics · June 3, 2025 We consider the setting where a user with sensitive features wishes to obtain a recommendation from a server in a differentially private fashion. We propose a “multi-selection” architecture where the server can send back multiple recommendations and the us ... Full text Cite

Group Fairness and Multi-Criteria Optimization in School Assignment

Conference Leibniz International Proceedings in Informatics Lipics · June 3, 2025 We consider the problem of assigning students to schools when students have different utilities for schools and schools have limited capacities. The students belong to demographic groups, and fairness over these groups is captured either by concave objecti ... Full text Cite

Fair Division via the Cake-Cutting Share

Conference Proceedings of the Aaai Conference on Artificial Intelligence · April 11, 2025 In this paper, we consider the classic fair division problem of allocating m divisible items to n agents with linear valuations over the items. We define novel notions of fair shares from the perspective of individual agents via the cake-cutting process. T ... Full text Cite

Optimal algorithms for multiwinner elections and the Chamberlin–Courant Rule

Conference Social Choice and Welfare · February 1, 2025 We consider the algorithmic question of choosing a subset of candidates of a given size k from a set of m candidates, with knowledge of voters’ ordinal rankings over all candidates. We consider the well-known and classic scoring rule for achieving diverse ... Full text Cite

Majorized Bayesian Persuasion and Fair Selection

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2025 We address the fundamental problem of selection under uncertainty by modeling it from the perspective of Bayesian persuasion. In our model, a decision maker with imperfect information always selects the option with the highest expected value. We seek to ac ... Cite

Data Exchange Markets via Utility Balancing

Conference Www 2024 Proceedings of the ACM Web Conference · May 13, 2024 This paper explores the design of a balanced data-sharing marketplace for entities with heterogeneous datasets and machine learning models that they seek to refine using data from other agents. The goal of the marketplace is to encourage participation for ... Full text Cite

Fair Price Discrimination

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2024 A seller is pricing identical copies of a good to a stream of unit-demand buyers. Each buyer has a value on the good as his private information. The seller only knows the empirical value distribution of the buyer population and chooses the revenue-optimal ... Full text Cite

Individual Fairness in Graph Decomposition

Conference Proceedings of Machine Learning Research · January 1, 2024 In this paper, we consider classic randomized low diameter decomposition procedures for planar graphs that obtain connected clusters which are cohesive in that close-by pairs of nodes are assigned to the same cluster with high probability. We require the a ... Cite

Probabilistic Metric Embedding via Metric Labeling

Conference Leibniz International Proceedings in Informatics Lipics · September 1, 2023 We consider probabilistic embedding of metric spaces into ultra-metrics (or equivalently to a constant factor, into hierarchically separated trees) to minimize the expected distortion of any pairwise distance. Such embeddings have been widely used in netwo ... Full text Cite

Fair Multiwinner Elections with Allocation Constraints

Conference EC 2023 Proceedings of the 24th ACM Conference on Economics and Computation · July 9, 2023 We consider the classical multiwinner election problem where the goal is to choose a subset of k unit-sized candidates (called committee) given utility functions of the voters. We allow arbitrary additional constraints on the chosen committee, and the util ... Full text Cite

Online Learning and Bandits with Queried Hints

Conference Leibniz International Proceedings in Informatics Lipics · January 1, 2023 We consider the classic online learning and stochastic multi-armed bandit (MAB) problems, when at each step, the online policy can probe and find out which of a small number (k) of choices has better reward (or loss) before making its choice. In this model ... Full text Cite

Competing against Adaptive Strategies in Online Learning via Hints

Conference Proceedings of Machine Learning Research · January 1, 2023 For many of the classic online learning settings, it is known that having a “hint” about the loss function before making a prediction yields significantly better regret guarantees. In this work we study the question, do hints allow us to go beyond the stan ... Cite

Fairness in the Assignment Problem with Uncertain Priorities

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems Aamas · January 1, 2023 In the assignment problem, a set of items must be allocated to unit-demand agents who express ordinal preferences (rankings) over the items. In the assignment problem with priorities, agents with higher priority are entitled to their preferred goods with r ... Cite

Optimal Price Discrimination for Randomized Mechanisms

Conference EC 2022 Proceedings of the 23rd ACM Conference on Economics and Computation · July 12, 2022 We study the power of price discrimination via an intermediary in bilateral trade, when there is a revenue-maximizing seller selling an item to a buyer with a private value drawn from a prior. Between the seller and the buyer, there is an intermediary that ... Full text Cite

Locally Fair Partitioning

Conference Proceedings of the 36th Aaai Conference on Artificial Intelligence Aaai 2022 · June 30, 2022 We model the societal task of redistricting political districts as a partitioning problem: Given a set of n points in the plane, each belonging to one of two parties, and a parameter k, our goal is to compute a partition Π of the plane into regions so that ... Full text Cite

Approximate Core for Committee Selection via Multilinear Extension and Market Clearing

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2022 Motivated by civic problems such as participatory budgeting and multiwinner elections, we consider the problem of public good allocation: Given a set of indivisible projects (or candidates) of different sizes, and voters with different monotone utility fun ... Cite

Auditing for Core Stability in Participatory Budgeting

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2022 We consider the participatory budgeting problem where each of n voters specifies additive utilities over m candidate projects with given sizes, and the goal is to choose a subset of projects (i.e., a committee) with total size at most k. Participatory budg ... Full text Cite

All Politics is Local: Redistricting via Local Fairness

Conference Advances in Neural Information Processing Systems · January 1, 2022 In this paper, we propose to use the concept of local fairness for auditing and ranking redistricting plans. Given a redistricting plan, a deviating group is a population-balanced contiguous region in which a majority of individuals are of the same interes ... Cite

A Simple Mechanism for a Budget-Constrained Buyer

Conference ACM Transactions on Economics and Computation · May 1, 2021 We study a classic Bayesian mechanism design setting of monopoly problem for an additive buyer in the presence of budgets. In this setting, a monopolist seller with m heterogeneous items faces a single buyer and seeks to maximize her revenue. The buyer has ... Full text Cite

Robust Allocations with Diversity Constraints

Conference Advances in Neural Information Processing Systems · January 1, 2021 We consider the problem of allocating divisible items among multiple agents, and consider the setting where any agent is allowed to introduce diversity constraints on the items they are allocated. We motivate this via settings where the items themselves co ... Cite

Group Fairness in Committee Selection

Conference ACM Transactions on Economics and Computation · November 1, 2020 In this article, we study fairness in committee selection problems. We consider a general notion of fairness via stability: A committee is stable if no coalition of voters can deviate and choose a committee of proportional size, so that all these voters st ... Full text Cite

Dynamic Weighted Fairness with Minimal Disruptions

Conference Performance Evaluation Review · July 8, 2020 In this paper, we consider the following dynamic fair allocation problem: Given a sequence of job arrivals and departures, the goal is to maintain an approximately fair allocation of the resource against a target fair allocation policy, while minimizing th ... Full text Cite

Adaptive probing policies for shortest path routing

Conference Advances in Neural Information Processing Systems · January 1, 2020 Inspired by traffic routing applications, we consider the problem of finding the shortest path from a source s to a destination t in a graph, when the lengths of the edges are unknown. Instead, we are given hints or predictions of the edge lengths from a c ... Cite

The Segmentation-Thickness Tradeoff in Online Marketplaces

Conference Performance Evaluation Review · December 17, 2019 A core tension in the operations of online marketplaces is between segmentation (wherein platforms can increase revenue by segmenting the market into ever smaller sub-markets) and thickness (wherein the size of the sub-market affects the utility experience ... Full text Cite

Improved metric distortion for deterministic social choice rules

Conference ACM EC 2019 Proceedings of the 2019 ACM Conference on Economics and Computation · June 17, 2019 In this paper, we study the metric distortion of deterministic social choice rules that choose a winning candidate from a set of candidates based on voter preferences. Voters and candidates are located in an underlying metric space. A voter has cost equal ... Full text Cite

Group fairness in committee selection

Conference ACM EC 2019 Proceedings of the 2019 ACM Conference on Economics and Computation · June 17, 2019 In this paper, we study fairness in committee selection problems. We consider a general notion of fairness via stability: A committee is stable if no coalition of voters can deviate and choose a committee of proportional size, so that all these voters stri ... Full text Cite

Random dictators with a random referee: Constant sample complexity mechanisms for social choice

Conference 33rd Aaai Conference on Artificial Intelligence Aaai 2019 31st Innovative Applications of Artificial Intelligence Conference Iaai 2019 and the 9th Aaai Symposium on Educational Advances in Artificial Intelligence Eaai 2019 · January 1, 2019 We study social choice mechanisms in an implicit utilitarian framework with a metric constraint, where the goal is to minimize Distortion, the worst case social cost of an ordinal mechanism relative to underlying cardinal utilities. We consider two additio ... Full text Cite

Proportionally Fair Clustering

Conference Proceedings of Machine Learning Research · January 1, 2019 We extend the fair machine learning literature by considering the problem of proportional centroid clustering in a metric context. For clustering n points with k centers, we define fairness as proportionality to mean that any n/k points are entitled to for ... Cite

Fair allocation of indivisible public goods

Conference ACM EC 2018 Proceedings of the 2018 ACM Conference on Economics and Computation · June 11, 2018 We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume that agents have additive utilities across elements. Our model g ... Full text Cite

Subtrajectory clustering: Models and algorithms

Conference Proceedings of the ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems · May 27, 2018 We propose a model for subtrajectory clustering'the clustering of subsequences of trajectories; each cluster of subtrajectories is represented as a pathlet, a sequence of points that is not necessarily a subsequence of an input trajectory. Given a set of t ... Full text Cite

A simple mechanism for a budget-constrained buyer

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2018 We study a classic Bayesian mechanism design setting of monopoly problem for an additive buyer in the presence of budgets. In this setting a monopolist seller with m heterogeneous items faces a single buyer and seeks to maximize her revenue. The buyer has ... Full text Cite

Metric distortion of social choice rules: Lower bounds and fairness properties

Conference EC 2017 Proceedings of the 2017 ACM Conference on Economics and Computation · June 20, 2017 We study social choice rules under the utilitarian distortion framework, with an additional metric assumption on the agents' costs over the alternatives. In this approach, these costs are given by an underlying metric on the set of all agents plus alternat ... Full text Cite

ROBUS: Fair cache allocation for data-parallel workloads

Conference Proceedings of the ACM SIGMOD International Conference on Management of Data · May 9, 2017 Systems for processing big data-e.g., Hadoop, Spark, and massively parallel databases-need to run workloads on behalf of multiple tenants simultaneously. The abundant disk-based storage in these systems is usually complemented by a smaller, but much faster ... Full text Cite

Sequential deliberation for social choice

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2017 Social choice is a normative study of designing protocols for collective decision making. However, in instances where the underlying decision space is too large or complex for ordinal voting, standard voting methods may be impractical. How then can we desi ... Full text Cite

Collaborative optimization for collective decision-making in continuous spaces

Conference 26th International World Wide Web Conference Www 2017 · January 1, 2017 Many societal decision problems lie in high-dimensional continuous spaces not amenable to the voting techniques common for their discrete or single-dimensional counterparts. These problems are typically discretized before running an election or decided upo ... Full text Cite

ROBUS: Fair Cache Allocation for Data-parallel Workloads.

Conference SIGMOD Conference · 2017 Cite

Segmenting two-sided markets

Conference 26th International World Wide Web Conference Www 2017 · January 1, 2017 Recent years have witnessed the rise of many successful e-commerce marketplace platforms like the Amazon marketplace, AirBnB, Uber/Lyft, and Upwork, where a central platform mediates economic transactions between buyers and sellers. A common feature of man ... Full text Cite

Massively parallel algorithms for computing TIN DEMs and contour trees for large terrains

Conference GIS Proceedings of the ACM International Symposium on Advances in Geographic Information Systems · October 31, 2016 We propose parallel algorithms in the massively parallel communication (MPC) model (e.g. MapReduce) for processing large terrain elevation data (represented as a 3D point cloud) that are too big to fit on one machine. In particular, given a set S of 3D poi ... Full text Cite

Competitive analysis of constrained queueing systems

Conference Leibniz International Proceedings in Informatics Lipics · August 1, 2016 We consider the classical problem of constrained queueing (or switched networks): There is a set of N queues to which unit sized packets arrive. The queues are interdependent, so that at any time step, only a subset of the queues can be activated. One pack ... Full text Cite

Parallel algorithms for constructing range and nearest-neighbor searching data structures

Conference Proceedings of the ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems · June 15, 2016 With the massive amounts of data available today, it is common to store and process data using multiple machines. Parallel programming platforms such as MapReduce and its variants are popular frameworks for handling such large data. We present the first pr ... Full text Cite

The core of the participatory budgeting problem

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2016 In participatory budgeting, communities collectively decide on the allocation of public tax dollars for local public projects. In this work, we consider the question of fairly aggregating preferences to determine an allocation of funds to projects. We argu ... Full text Cite

A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints

Conference APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION. ALGORITHMS AND TECHNIQUES, APPROX/RANDOM 2016 · 2016 Full text Link to item Cite

Competitive Flow Time Algorithms for Polyhedral Scheduling

Conference Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs · December 11, 2015 Many scheduling problems can be viewed as allocating rates to jobs, subject to convex packing constraints on the rates. In this paper, we consider the problem of rate allocation when jobs of unknown size arrive online (non-clairvoyant setting), with the go ... Full text Cite

Combating Friend Spam Using Social Rejections

Conference Proceedings International Conference on Distributed Computing Systems · July 22, 2015 Unwanted friend requests in online social networks (OSNs), also known as friend spam, are among the most evasive malicious activities. Friend spam can result in OSN links that do not correspond to social relationship among users, thus pollute the underlyin ... Full text Cite

A note on modeling retweet cascades on Twitter

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2015 Information cascades on social networks, such as retweet cascades on Twitter, have been often viewed as an epidemiological process, with the associated notion of virality to capture popular cascades that spread across the network. The notion of structural ... Full text Cite

SelfishMigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors

Conference Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs · December 7, 2014 We consider the classical problem of minimizing the total weighted flow-time for unrelated machines in the online non-clairvoyant setting. In this problem, a set of jobs J arrive over time to be scheduled on a set of M machines. Each job J has processing l ... Full text Cite

Coordination mechanisms from (almost) all scheduling policies

Conference Itcs 2014 Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science · January 1, 2014 We study the price of anarchy of coordination mechanisms for a scheduling problem where each job j has a weight wj, processing time p ij, assignment cost hij, and communication delay (or release date) rij on mach ... Full text Cite

Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 2014 We introduce and study a general scheduling problem that we term the Packing Scheduling problem (PSP). In this problem, jobs can have different arrival times and sizes; a scheduler can process job j at rate xj, subject to arbitrary packing const ... Full text Cite

Modeling opinion dynamics in social networks

Conference Wsdm 2014 Proceedings of the 7th ACM International Conference on Web Search and Data Mining · January 1, 2014 Our opinions and judgments are increasingly shaped by what we read on social media - whether they be tweets and posts in social networks, blog posts, or review boards. These opinions could be about topics such as consumer products, politics, life style, or ... Full text Cite

Value-based network externalities and optimal auction design

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2014 We study revenue maximization in settings where agents’ valuations exhibit positive network externalities. In our model, items have unlimited supply, and agents are unit demand. In a departure from previous literature, we assume agents have value based ext ... Full text Cite

Efficient primal-dual graph algorithms for MapReduce

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2014 In this paper, we obtain improved algorithms for two graphtheoretic problems in the popular MapReduce framework. The first problem we consider is the densest subgraph problem. We present a primal-dual algorithm that provides a (1 + ϵ) approximation and tak ... Full text Cite

Stochastic regret minimization via Thompson Sampling

Conference Journal of Machine Learning Research · January 1, 2014 The Thompson Sampling (TS) policy is a widely implemented algorithm for the stochastic multiarmed bandit (MAB) problem. Given a prior distribution over possible parameter settings of the underlying reward distributions of the arms, at each time instant, th ... Cite

Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints.

Conference STOC · 2014 Cite

Algorithms for cost-aware scheduling

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · December 1, 2013 Full text Cite

Approximate indexability and bandit problems with concave rewards and delayed feedback

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · October 15, 2013 We consider two stochastic multi-armed bandit problems in this paper in the Bayesian setting. In the first problem the accrued reward in a step is a concave function (such as the maximum) of the observed values of the arms played in that step. In the secon ... Full text Cite

Coevolutionary opinion formation games

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · July 11, 2013 We present game-theoretic models of opinion formation in social networks where opinions themselves co-evolve with friendships. In these models, nodes form their opinions by maximizing agreements with friends weighted by the strength of the relationships, w ... Full text Cite

On the precision of social and information networks

Conference Cosn 2013 Proceedings of the 2013 Conference on Online Social Networks · January 1, 2013 The diffusion of information on online social and information networks has been a popular topic of study in recent years, but attention has typically focused on speed of dissemination and recall (i.e. the fraction of users getting a piece of information). ... Full text Cite

Optimal auctions via the multiplicative weight method.

Conference EC · 2013 Cite

Mechanisms and allocations with positive network externalities

Conference Proceedings of the ACM Conference on Electronic Commerce · June 4, 2012 With the advent of social networks such as Facebook and LinkedIn, and online offers/deals web sites, network externalties raise the possibility of marketing and advertising to users based on influence they derive from their neighbors in such networks. Inde ... Full text Cite

Consideration set generation in commerce search

Conference Proceedings of the 20th International Conference on World Wide Web Www 2011 · December 1, 2011 In commerce search, the set of products returned by a search engine often forms the basis for all user interactions leading up to a potential transaction on the web. Such a set of products is known as the consideration set. In this study, we consider the p ... Full text Cite

Optimal auctions with positive network externalities

Conference Proceedings of the ACM Conference on Electronic Commerce · June 5, 2011 We consider the problem of designing auctions in social networks for goods that exhibit single-parameter submodular network externalities in which a bidder's value for an outcome is a fixed private type times a known submodular function of the allocation o ... Full text Cite

Approximation algorithm for security games with costly resources

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2011 In recent years, algorithms for computing game-theoretic solutions have been developed for real-world security domains. These games are between a defender, who must allocate her resources to defend potential targets, and an attacker, who chooses a target t ... Full text Cite

Storing matrices on disk: Theory and practice revisited

Conference Proceedings of the VLDB Endowment · January 1, 2011 We consider the problem of storing arrays on disk to support scalable data analysis involving linear algebra. We propose Linearized Array B-tree, or LAB-tree, which supports flexible array layouts and automatically adapts to varying sparsity across parts o ... Full text Cite

On allocations with negative externalities

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2011 We consider the problem of a monopolist seller who wants to sell some items to a set of buyers. The buyers are strategic, unit-demand, and connected by a social network. Furthermore, the utility of a buyer is a decreasing function of the number of neighbor ... Full text Cite

On Allocations with Negative Externalities.

Conference WINE · 2011 Cite

False-name-proofness in social networks

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · December 1, 2010 In mechanism design, the goal is to create rules for making a decision based on the preferences of multiple parties (agents), while taking into account that agents may behave strategically. An emerging phenomenon is to run such mechanisms on a social netwo ... Full text Cite

Budget constrained auctions with heterogeneous items

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · July 23, 2010 In this paper, we present the first approximation algorithms for the problem of designing revenue optimal Bayesian incentive compatible auctions when there are multiple (heterogeneous) items and when bidders have arbitrary demand and budget constraints (an ... Full text Cite

Incentive compatible budget elicitation in multi-unit auctions

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2010 In this paper, we consider the problem of designing incentive compatible auctions for multiple (homogeneous) units of a good, when bidders have private valuations and private budget constraints. When only the valuations are private and the budgets are publ ... Full text Cite

Learning and approximating the optimal strategy to commit to

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · December 14, 2009 Computing optimal Stackelberg strategies in general two-player Bayesian games (not to be confused with Stackelberg strategies in routing games) is a topic that has recently been gaining attention, due to their application in various security and law enforc ... Full text Cite

Hybrid keyword search auctions

Conference Www 09 Proceedings of the 18th International World Wide Web Conference · December 1, 2009 Search auctions have become a dominant source of revenue generation on the Internet. Such auctions have typically used per-click bidding and pricing. We propose the use of hybrid auctions where an advertiser can make a per-impression as well as a per-click ... Full text Cite

Order matters: Transmission reordering in wireless networks

Conference Proceedings of the Annual International Conference on Mobile Computing and Networking MOBICOM · November 30, 2009 Modern wireless interfaces support a physical layer capability called Message in Message (MIM). Briefly, MIM allows a receiver to disengage from an ongoing reception, and engage onto a stronger incoming signal. Links that otherwise conflict with each other ... Full text Cite

Multi-armed bandits with metric switching costs

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · November 12, 2009 In this paper we consider the stochastic multi-armed bandit with metric switching costs. Given a set of locations (arms) in a metric space and prior information about the reward available at these locations, cost of getting a sample/play at every location ... Full text Cite

Fa: A system for automating failure diagnosis

Conference Proceedings International Conference on Data Engineering · July 8, 2009 Failures of Internet services and enterprise systems lead to user dissatisfaction and considerable loss of revenue. Since manual diagnosis is often laborious and slow, there is considerable interest in tools that can diagnose the cause of failures quickly ... Full text Cite

Exceeding expectations and clustering uncertain data

Conference Proceedings of the ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems · June 29, 2009 Database technology is playing an increasingly important role in understanding and solving large-scale and complex scientific and societal problems and phenomena, for instance, understanding biological networks, climate modeling, electronic markets, etc. I ... Full text Cite

Large-scale uncertainty management systems: Learning and exploiting your data

Conference SIGMOD Pods 09 Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems · January 1, 2009 The database community has made rapid strides in capturing, representing, and querying uncertain data. Probabilistic databases capture the inherent uncertainty in derived tuples as probability estimates. Data acquisition and stream systems can produce succ ... Full text Cite

Approximation algorithms for restless bandit problems

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2009 In this paper, we consider the restless bandit problem, which is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit problem in decision theory. In its ultimate generality, the restless bandit problem is known to be ... Full text Cite

Modeling and exploiting query interactions in database systems

Conference International Conference on Information and Knowledge Management Proceedings · December 1, 2008 The typical workload in a database system consists of a mixture of multiple queries of different types, running concurrently and interacting with each other. Hence, optimizing performance requires reasoning about query mixes and their interactions, rather ... Full text Cite

Processing diagnosis queries: A principled and scalable approach

Conference Proceedings International Conference on Data Engineering · October 1, 2008 Many popular Web sites suffer occasional user-visible problems such as slow responses, blank pages or error messages being displayed, items not being added to shopping carts, database slowdowns, and others. Such deviations of systems from desired behavior, ... Full text Cite

The stochastic machine replenishment problem

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · June 30, 2008 We study the stochastic machine replenishment problem, which is a canonical special case of closed multiclass queuing systems in Markov decision theory. The problem models the scheduling of processor repairs in a multiprocessor system in which one repair c ... Full text Cite

Message in Message (MIM): A Case for Reordering Transmissions in Wireless Networks

Conference 7th ACM Workshop on Hot Topics in Networks Hotnets 2008 · January 1, 2008 Message in Message (MIM) is an exciting development at the physical layer of IEEE 802.11. Two transmissions that otherwise conflict with each other, may be made concurrent with MIM. However, the benefits from MIM are not immediate. Higher layer protocols n ... Cite

Approximation algorithms for partial-information based stochastic control with Markovian rewards

Conference Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs · December 1, 2007 We consider a variant of the classic multi-armed bandit problem (MAB), which we call FEEDBACK MAB, where the reward obtained by playing each of n independent arms varies according to an underlying on/off Markov process with known parameters. The evolution ... Full text Cite

Approximation algorithms for budgeted learning problems

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · October 30, 2007 We present the first approximation algorithms for a large class of budgeted learning problems. One classicexample of the above is the budgeted multi-armed bandit problem. In this problem each arm of the bandithas an unknown reward distribution on which a p ... Full text Cite

Approximate Hypergraph Partitioning and Applications

Conference 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · October 2007 Full text Cite

Approximation Algorithms for Partial-Information Based Stochastic Control with Markovian Rewards

Conference 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · October 2007 Full text Cite

Optimization of continuous queries with shared expensive filters

Conference Proceedings of the ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems · June 11, 2007 We consider the problem of optimizing and executing multiple continuous queries, where each query is a conjunction of filters and each filter may occur in multiple queries. When filters are expensive, significant performance gains are achieved by sharing f ... Full text Cite

Suppression and failures in sensor networks: A Bayesian approach

Conference 33rd International Conference on Very Large Data Bases VLDB 2007 Conference Proceedings · January 1, 2007 Sensor networks allow continuous data collection on unprecedented scales. The primary limiting factor of such networks is energy, of which communication is the dominant consumer. The default strategy of nodes continually reporting their data to the root re ... Cite

From data reverence to data relevance: Model-mediated wireless sensing of the physical environment

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2007 Wireless sensor networks can be viewed as the integration of three subsystems: a low-impact in situ data acquisition and collection system, a system for inference of process models from observed data and a priori information, and a system that controls the ... Full text Cite

Data-driven processing in sensor networks

Conference Cidr 2007 3rd Biennial Conference on Innovative Data Systems Research · January 1, 2007 Wireless sensor networks are poised to enable continuous data collection on unprecedented scales, in terms of area location and size, and frequency. This is a great boon to fields such as ecological modeling. We are collaborating with researchers to build ... Cite

Making Sense of Suppressions and Failures in Sensor Data: A Bayesian Approach.

Conference VLDB · 2007 Cite

Model-driven optimization using adaptive probes

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2007 In several applications such as databases, planning, and sensor networks, parameters such as selectivity, load, or sensed values are known only with some associated uncertainty. The performance of such a system (as captured by some objective function over ... Cite

Approximation Schemes for Information Acquisition and Exploitation in Multichannel Wireless Networks

Conference 44th Annual Allerton Conference on Communication Control and Computing 2006 · January 1, 2006 Nodes in future wireless networks are likely to have access to multiple channels. A node can learn the instantaneous state of a channel only by probing it which in turn consumes both additional energy and time. A node therefore needs to not only optimally ... Cite

Jointly optimal transmission and probing strategies for multichannel wireless systems

Conference 2006 IEEE Conference on Information Sciences and Systems Ciss 2006 Proceedings · January 1, 2006 We consider a wireless system with multiple channels when each channel has several different transmission states. Different states are associated with different probabilities of successful transmissions. In such networks, we are faced with making transmiss ... Full text Cite

Query optimization over Web Services

Conference VLDB 2006 Proceedings of the 32nd International Conference on Very Large Data Bases · January 1, 2006 Web services are becoming a standard method of sharing data and functionality among loosely-coupled systems. We propose a general-purpose Web Service Management System (WSMS) that enables querying multiple web services in a transparent and integrated fashi ... Cite

Optimizing transmission rate in wireless channels using adaptive probes.

Conference SIGMETRICS/Performance · 2006 Cite

Application of the Two-Sided Depth Test to CSG Rendering

Conference 2003 ACM SIGGRAPH Symposium on Interactive 3D Graphics I3d 2003 · April 27, 2003 Shadow mapping is a technique for doing real-time shadowing. Recent work has shown that shadow mapping hardware can be used as a second depth test in addition to the z-test. In this paper, we explore the computational power provided by this second depth te ... Full text Cite

Improved algorithms for the data placement problem

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2002 Introduction: We study the data placement problem [1, 3], where the goal is to place certain data objects (with possible replication) in fixed capacity caches in a network to optimize latency of access. The locations of the caches are given and each cache ... Cite

Generalized clustering

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2002 Cite

Web caching using access statistics

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · December 1, 2001 We consider the problem of caching web pages with the objective of minimizing latency of access. Demands for web domains/pages are computed using access statistics; the frequency with which these statistics change is considerably longer than the frequency ... Cite

Improved algorithms for fault tolerant facility location

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · December 1, 2001 We consider a generalization of the classical facility location problem, where we reguire the solution to be fault-tolerant. Every demand point; is served by rj facilities instead of just one. The facilities other than the closest one are "backup" faciliti ... Cite

Designing networks incrementally

Conference Annual Symposium on Foundations of Computer Science Proceedings · January 1, 2001 We consider the problem of incrementally designing a network to route demand to a single sink on an underlying metric space. We are given cables whose costs per unit length scale in a concave fashion with capacity. Under certain natural restrictions on the ... Full text Cite

A constant factor approximation for the single sink edge installation problem

Conference Conference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 2001 We present the first constant approximation to the single sink buy-at-bulk network design problem, where we have to design a network by buying pipes of different costs and capacities per unit length to route demands at a set of sources to a single sink. Th ... Full text Cite

Local search heuristics for k-median and facility location problems

Conference Conference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 2001 In this paper, we analyze local search heuristics for the k-median and facility location problems. We define the locality gap of a local search procedure as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optim ... Full text Cite

COST-DISTANCE: Two metric network design

Conference Annual Symposium on Foundations of Computer Science Proceedings · December 1, 2000 We present the COST-DISTANCE problem: finding a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We give the first known O(log k) randomized approximation scheme for ... Cite

Hierarchical placement and network design problems

Conference Annual Symposium on Foundations of Computer Science Proceedings · December 1, 2000 In this paper, we give the first constant-approximations for a number of layered network design problems. We begin by modeling hierarchical caching, where caches are placed in layers and each layer satisfies a fixed percentage of the demand (bounded miss r ... Cite

Balancing Steiner trees and shortest path trees online

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2000 Given a weighted undirected graph G(V, E) and a subset R of V, we present an online algorithm for finding a Steiner tree on R that simultaneously approximates the shortest path tree and the minimum weight Steiner tree. The cost of the tree we construct is ... Cite

Online algorithms for caching multimedia streams

Conference Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2000 We consider the problem of caching multimedia streams in the internet. We use the dynamic caching framework of Dan et al. and Hofmann et al.. We define a novel performance metric based on the maximum number of simultaneous cache misses, and present near-op ... Full text Cite

I/O-complexity of graph algorithms

Conference Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 1999 We show lower bounds of Ω(E/V Sort(V)) for the I/O-complexity of graph theoretic problems like connected components, biconnected components, and minimum spanning trees, where E and V are the number of edges and vertices in the input graph, respectively. We ... Cite