S. Muthukrishnan

AAMAS Conference 2018 Conference Paper

Arbitrage-free Pricing in User-based Markets

• Chaolun Xia
• S. Muthukrishnan

Users have various attributes, and in user-based markets there are buyers who wish to buy a target set of users with specific sets of attributes. The problem we address is that, given a set of demand from the buyers, how to allocate users to buyers, and how to price the transactions. This problem arises in online advertising, and is particularly relevant in advertising in social platforms like Facebook, LinkedIn and others where users are represented with many attributes, and advertisers are buyers with specific targets. This problem also arises more generally in selling data about online users, in a variety of data markets. We introduce arbitrage-free pricing, that is, pricing that prevents buyers from acquiring a lower unit price for their true target by strategically choosing substitute targets and combining them suitably. We show that uniform pricing – pricing where all the targets have identical price – can be computed in polynomial time, and while this is arbitrage-free, it is also a logarithmic approximation to the maximum revenue arbitrage-free pricing solution. We also design a different arbitrage-free non-uniform pricing – pricing where different targets have different prices – solution which has the same guarantee as the arbitrage-free uniform pricing but is empirically more effective as we show through experiments. We also study more general versions of this problem and present hardness and approximation results.

AAAI Conference 2014 Conference Paper

Large-Scale Optimistic Adaptive Submodularity

• Victor Gabillon
• Branislav Kveton
• Zheng Wen
• Brian Eriksson
• S. Muthukrishnan

Maximization of submodular functions has wide applications in artificial intelligence and machine learning. In this paper, we propose a scalable learning algorithm for maximizing an adaptive submodular function. The key structural assumption in our solution is that the state of each item is distributed according to a generalized linear model, which is conditioned on the feature vector of the item. Our objective is to learn the parameters of this model. We analyze the performance of our algorithm, and show that its regret is polylogarithmic in time and quadratic in the number of features. Finally, we evaluate our solution on two problems, preference elicitation and face detection, and show that high-quality policies can be learned sample efficiently.

NeurIPS Conference 2013 Conference Paper

Adaptive Submodular Maximization in Bandit Setting

• Victor Gabillon
• Branislav Kveton
• Zheng Wen
• Brian Eriksson
• S. Muthukrishnan

Maximization of submodular functions has wide applications in machine learning and artificial intelligence. Adaptive submodular maximization has been traditionally studied under the assumption that the model of the world, the expected gain of choosing an item given previously selected items and their states, is known. In this paper, we study the scenario where the expected gain is initially unknown and it is learned by interacting repeatedly with the optimized function. We propose an efficient algorithm for solving our problem and prove that its expected cumulative regret increases logarithmically with time. Our regret bound captures the inherent property of submodular maximization, earlier mistakes are more costly than later ones. We refer to our approach as Optimistic Adaptive Submodular Maximization (OASM) because it trades off exploration and exploitation based on the optimism in the face of uncertainty principle. We evaluate our method on a preference elicitation problem and show that non-trivial K-step policies can be learned from just a few hundred interactions with the problem.

TCS Journal 2008 Journal Article

The Magnus–Derek game

• Z. Nedev
• S. Muthukrishnan

We introduce a new combinatorial game between two players: Magnus and Derek. Initially, a token is placed at position 0 on a round table with n positions. In each round of the game Magnus chooses the number of positions for the token to move, and Derek decides in which direction, + (clockwise) or − (counterclockwise), the token will be moved. Magnus aims to maximize the total number of positions visited during the course of the game, while Derek aims to minimize this quantity. We define f ∗ ( n ) to be the eventual size of the set of visited positions when both players play optimally. We prove a closed form expression for f ∗ ( n ) in terms of the prime factorization of n, and provide algorithmic strategies for Magnus and Derek to meet this bound. We note the relevance of the game for a mobile agent exploring a ring network with faulty sense of direction, and we pose variants of the game for future study.

TCS Journal 2007 Journal Article

Foreword

• Paolo Ferragina
• Giovanni Manzini
• S. Muthukrishnan

TCS Journal 2006 Journal Article

Preface

• Suleyman Cenk Sahinalp
• Ugur Dogrusoz
• S. Muthukrishnan

TCS Journal 2004 Journal Article

An efficient algorithm for sequence comparison with block reversals

• S. Muthukrishnan
• S. Cenk Sahinalp

Given two sequences X and Y that are strings over some alphabet set, we consider the distance d(X, Y) between them defined to be minimum number of character replacements and block (substring) reversals needed to transform X to Y (or vice versa). The operations are required to be disjoint. This is the “simplest” sequence comparison problem we know of that allows natural block edit operations. Block reversals arise naturally in genomic sequence comparison; they are also of interest in matching music data. We present an algorithm for exactly computing the distance d(X, Y); it takes time O(|X|log2|X|), and hence, is near-linear. Trivial approach takes quadratic time.

I&C Journal 2004 Journal Article

Parallel two dimensional witness computation

• Richard Cole
• Zvi Galil
• Ramesh Hariharan
• S. Muthukrishnan
• Kunsoo Park

An optimal parallel CRCW-PRAM algorithm to compute witnesses for all non-period vectors of an m 1×m 2 pattern is given. The algorithm takes O(loglogm) time and does O(m 1×m 2) work, where m=max{m 1, m 2}. This yields a work optimal algorithm for 2D pattern matching which takes O(loglogm) preprocessing time and O(1) text processing time.

I&C Journal 1995 Journal Article

String Matching under a General Matching Relation

• S. Muthukrishnan
• H. Ramesh

In standard string matching, each symbol matches only itself, In other string matching problems, e. g. , the string matching with "don′t-cares" problem, a symbol may match several symbols. In general, an arbitrary many-to-many matching relation might hold between symbols. We consider a general string matching problem in which such a matching relation is specified and those positions in a text t, of length n, are sought at which the pattern p, of length m, matches under this relation. Depending upon the existence of a simple and easily recognizable property in the given matching relation, we show that string matching either requires linear (i. e. , O(n + m)) time or is at least as hard as boolean convolution. As an application, we show that the matching relations of several independently studied string matching problems do indeed fall into the latter (hard) category. We also give a generic string matching algorithm that works far any matching relation and has complexity o(nm) except for very "large" matching relations.