Scholars@Duke
Kamesh Munagala

Kamesh Munagala

Professor of Computer Science
Computer Science
Box 90129, Computer Science Department, Durham, NC 27708-0129
D205, LSRC, Research Drive, Durham, NC

Selected Publications

Optimal Price Discrimination for Randomized Mechanisms

Journal Article ACM Transactions on Economics and Computation · June 12, 2024 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

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

Optimal algorithms for multiwinner elections and the Chamberlin–Courant Rule

Conference Social Choice and Welfare · January 1, 2024 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

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

ACHIEVING PARITY WITH HUMAN MODERATORS: A self-moderating platform for online deliberation1

Chapter · January 1, 2023 We describe the design of a video-conferencing platform for online deliberation that is self-moderating in the sense that it works without a human moderator. The platform includes an audio and video conferencing system and incorporates automated and user-a ... Full text Cite

The Limits of an Information Intermediary in Auction Design

Journal Article EC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation · July 12, 2022 We study the limits of an information intermediary in the classical Bayesian auction, where a revenue-maximizing seller sells one item to n buyers with independent private values. In addition, we have an intermediary who knows the buyers' private values, a ... Full text 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 ... 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

Centrality with Diversity

Journal Article WSDM 2021 - Proceedings of the 14th ACM International Conference on Web Search and Data Mining · August 3, 2021 Graph centrality measures use the structure of a network to quantify central or "important"nodes, with applications in web search, social media analysis, and graphical data mining generally. Traditional centrality measures such as the well known PageRank i ... Full text Cite

Optimal Algorithms for Multiwinner Elections and the Chamberlin-Courant Rule

Journal Article EC 2021 - Proceedings of the 22nd ACM Conference on Economics and Computation · July 18, 2021 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

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

Fair for All: Best-effort Fairness Guarantees for Classification

Journal Article Proceedings of Machine Learning Research · January 1, 2021 Standard approaches to group-based notions of fairness, such as parity and equalized odds, try to equalize absolute measures of performance across known groups (based on race, gender, etc.). Consequently, a group that is inherently harder to classify may h ... 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

Clustering under perturbation stability in near-linear time

Journal Article Leibniz International Proceedings in Informatics, LIPIcs · December 1, 2020 We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is α-stable if the underlying optimal clustering continues to remain optimal even when all pairwise distances ar ... Full text 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

Predict and Match: Prophet Inequalities with Uncertain Supply

Journal Article Performance Evaluation Review · July 8, 2020 We consider the problem of selling perishable items to a stream of buyers in order to maximize social welfare. A seller starts with a set of identical items, and each arriving buyer wants any one item, and has a valuation drawn i.i.d. from a known distribu ... 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

Approximately stable committee selection

Journal Article Proceedings of the Annual ACM Symposium on Theory of Computing · June 8, 2020 In the committee selection problem, we are given m candidates, and n voters. Candidates can have different weights. A committee is a subset of candidates, and its weight is the sum of weights of its candidates. Each voter expresses an ordinal ranking over ... Full text Cite

Dynamic Weighted Fairness with Minimal Disruptions

Journal Article SIGMETRICS Performance 2020 - Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems · June 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

Concentration of distortion: The value of extra voters in randomized social choice

Journal Article IJCAI International Joint Conference on Artificial Intelligence · January 1, 2020 We study higher statistical moments of Distortion for randomized social choice in a metric implicit utilitarian model. The Distortion of a social choice mechanism is the expected approximation factor with respect to the optimal utilitarian social cost (OPT ... 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

The Segmentation-Thickness Tradeoff in Online Marketplaces

Journal Article Proceedings of the ACM on Measurement and Analysis of Computing Systems · March 26, 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 ex ... Full text Cite

Iterative local voting for collective decision-making in continuous spaces

Journal Article Journal of Artificial Intelligence Research · February 1, 2019 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

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 ... Cite

Proportionally fair clustering

Journal Article 36th International Conference on Machine Learning, ICML 2019 · 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

Proportionally Fair Clustering.

Conference ICML · 2019 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

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

Journal Article Journal of the ACM · December 1, 2017 We introduce and study a general scheduling problem that we term the Polytope Scheduling problem (PSP). In this problem, jobs can have different arrival times and sizes, and the rates assigned by the scheduler to the jobs are subject to arbitrary packing c ... 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

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

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 machine i. Each machine is free to declare its o ... 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 constraints over ... 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

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

Approximation Algorithms for Bayesian Multi-Armed Bandit Problems

Report · June 14, 2013 In this paper, we consider several finite-horizon Bayesian multi-armed bandit problems with side constraints which are computationally intractable (NP-Hard) and for which no optimal (or near optimal) algorithms are known to exist with sub-exponential runni ... Link to item Cite

Optimal Auctions with Positive Network Externalities

Journal Article ACM Transactions on Economics and Computation · May 2013 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 ... 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

Complexity Measures for Map-Reduce, and Comparison to Parallel Computing

Report · November 28, 2012 The programming paradigm Map-Reduce and its main open-source implementation, Hadoop, have had an enormous impact on large scale data processing. Our goal in this expository writeup is two-fold: first, we want to present some complexity measures that allow ... Link to item Cite

Mechanisms and allocations with positive network externalities

Conference Proceedings of the ACM Conference on Electronic Commerce · July 10, 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

How to approximate optimal auctions

Journal Article ACM SIGecom Exchanges · June 2012 Bayesian auction design investigates how to sell scarce resources to agents with private values drawn according to known distributions. A natural objective in this setting is revenue maximization. The seminal work of Roger Myerson pres ... Full text Cite

Order matters: Transmission reordering in wireless networks

Journal Article IEEE/ACM Transactions on Networking · April 1, 2012 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

Adaptive uncertainty resolution in bayesian combinatorial optimization problems

Journal Article ACM Transactions on Algorithms · January 1, 2012 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 ... 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

Interaction-aware scheduling of report-generation workloads

Journal Article VLDB Journal · August 1, 2011 The typical workload in a database system consists of a mix of multiple queries of different types that run concurrently. Interactions among the different queries in a query mix can have a significant impact on database performance. Hence, optimizing datab ... Full text Cite

Optimal auctions with positive network externalities

Conference Proceedings of the ACM Conference on Electronic Commerce · June 30, 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

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

Approximation algorithms for restless bandit problems

Journal Article Journal of the ACM · December 1, 2010 The restless bandit problem is one of the mostwell-studied generalizations of the celebrated stochastic multi-armed bandit (MAB) problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate t ... Full text Cite

How to probe for an extreme value

Journal Article ACM Transactions on Algorithms · November 1, 2010 In several systems applications, parameters such as load are known only with some associated uncertainty, which is specified, or modeled, as a distribution over values. The performance of the system optimization and monitoring schemes can be improved by sp ... 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

Exceeding expectations and clustering uncertain data

Conference Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems · November 9, 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

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

A constant factor approximation for the single sink edge installation problem

Journal Article SIAM Journal on Computing · June 1, 2009 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

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

QShuffler: Getting the query mix right

Journal Article Proceedings - International Conference on Data Engineering · October 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

Information Acquisition and Exploitation in Multichannel Wireless Networks

Journal Article · April 10, 2008 A wireless system with multiple channels is considered, where each channel has several transmission states. A user learns about the instantaneous state of an available channel by transmitting a control packet in it. Since probing all channels consumes sign ... Link to item 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

Cost-Distance: Two Metric Network Design

Journal Article SIAM Journal on Computing · January 2008 Full text Cite

Data-driven processing in sensor networks

Conference CIDR 2007 - 3rd Biennial Conference on Innovative Data Systems Research · December 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

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

Optimization of continuous queries with shared expensive filters

Conference Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems · October 29, 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

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

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

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

Energy-efficient monitoring of extreme values in sensor networks

Journal Article Proceedings of the ACM SIGMOD International Conference on Management of Data · December 1, 2006 Monitoring extreme values (MAX or MIN) is a fundamental problem in wireless sensor networks (and in general, complex dynamic systems). This problem presents very different algorithmic challenges from aggregate and selection queries, in the sense that an in ... Full text Cite

Asking the right questions: Model-driven optimization using probes

Journal Article Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems · December 1, 2006 In several database applications, parameters like selectivities and load are known only with some associated uncertainty, which is specified, or modeled, as a distribution over values. The performance of query optimizers and monitoring schemes can be impro ... Full text Cite

A sampling-based approach to optimizing top-k queries in sensor networks

Journal Article Proceedings - International Conference on Data Engineering · October 17, 2006 Wireless sensor networks generate a vast amount of data. This data, however, must be sparingly extracted to conserve energy, usually the most precious resource in battery-powered sensors. When approximation is acceptable, a model-driven approach to query p ... Full text Cite

Optimizing transmission rate in wireless channels using adaptive probes

Journal Article Performance Evaluation Review · June 1, 2006 We consider a wireless system with multiple channels where each channel is either on or off, and probing the state of any channel incurs a cost. We present a polynomial time algorithm that determines which channels to probe and also which channel to transm ... Full text 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

Model-driven dynamic control of embedded wireless sensor networks

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2006 Next-generation wireless sensor networks may revolutionize understanding of environmental change by assimilating heterogeneous data, assessing the relative value and costs of data collection, and scheduling activities accordingly. Thus, they are dynamic, d ... Full text 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

Adaptive caching for continuous queries

Journal Article Proceedings - International Conference on Data Engineering · December 12, 2005 We address the problem of executing continuous multiway join queries in unpredictable and volatile environments. Our query class captures windowed join queries in data stream systems as well as conventional maintenance of materialized join views. Our adapt ... Full text Cite

The pipelined set cover problem

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2005 A classical problem in query optimization is to find the optimal ordering of a set of possibly correlated selections. We provide an abstraction of this problem as a generalization of set cover called pipelined set cover, where the sets are applied sequenti ... Full text Cite

Operator placement for in-network stream query processing

Journal Article Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems · December 1, 2005 In sensor networks, data acquisition frequently takes place at low-capability devices. The acquired data is then transmitted through a hierarchy of nodes having progressively increasing network band-width and computational power. We consider the problem of ... Cite

Online view maintenance under a response-time constraint

Journal Article Lecture Notes in Computer Science · January 1, 2005 A materialized view is a certain synopsis structure precomputed from one or more data sets (called base tables) in order to facilitate various queries on the data. When the underlying base tables change, the materialized view also needs to be updated accor ... Full text Cite

Local search heuristics for k-median and facility location problems

Journal Article SIAM Journal on Computing · July 28, 2004 We analyze local search heuristics for the metric k-median and facility location problems. We define the locality gap of a local search procedure for a minimization problem as the maximum ratio of a locally optimum solution (obtained using this procedure) ... Full text Cite

Cancer characterization and feature set extraction by discriminative margin clustering.

Journal Article BMC bioinformatics · March 2004 BackgroundA central challenge in the molecular diagnosis and treatment of cancer is to define a set of molecular features that, taken together, distinguish a given cancer, or type of cancer, from all normal cells and tissues.ResultsDiscri ... Full text Cite

Adaptive ordering of pipelined stream filters

Journal Article Proceedings of the ACM SIGMOD International Conference on Management of Data · January 1, 2004 We consider the problem of pipelined filters, where a continuous stream of tuples is processed by a set of commutative filters. Pipelined filters are common in stream applications and capture a large class of multiway stream joins. We focus on the problem ... Full text Cite

Application of the two-sided depth test to CSG rendering

Journal Article Proceedings of the Symposium on Interactive 3D Graphics · January 1, 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

A constant factor approximation algorithm for the fault-tolerant facility location problem

Journal Article Journal of Algorithms · January 1, 2003 We consider a generalization of the classical facility location problem, where we require the solution to be fault-tolerant. In this generalization, every demand point j must be served by rj facilities instead of just one. The facilities other than the clo ... Full text Cite

Extending greedy multicast routing to delay sensitive applications

Journal Article Algorithmica (New York) · January 1, 2002 For multicasting applications which need large amounts of data, it is important to minimize the total amount of resources consumed on the multicast tree. The greedy multicasting algorithm was proposed by Imase and Waxman as a solution to this problem for t ... 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

A constant factor approximation for the single sink edge installation problem

Conference Conference Proceedings of the Annual ACM Symposium on Theory of Computing · September 29, 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 ... 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

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 ... 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