Kamesh Munagala

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cost-Distance: Two Metric Network Design

Journal article SIAM Journal on Computing · January 2008 Full text 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

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

Asking the right questions: Model-driven optimization using probes

Journal article Proceedings of the ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems · June 26, 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

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

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

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

Operator placement for in-network stream query processing

Journal article Proceedings of the ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems · June 13, 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

The pipelined set cover problem

Journal article Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 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

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