5 Result(s)
within
S. Muthukrishnan
Computer Communication Networks
Theory of Computation
-
Chapter and Conference Paper
Quasi-Proportional Mechanisms: Prior-Free Revenue Maximization
Inspired by Internet ad auction applications, we study the problem of allocating a single item via an auction when bidders place very different values on the item. We formulate this as the problem of prior-free a...
-
Chapter and Conference Paper
Range Medians
We study a generalization of the classical median finding problem to batched query case: given an array of unsorted n items and k (not necessarily disjoint) intervals in the array, the goal is to determine the me...
-
Chapter and Conference Paper
Permutation Editing and Matching via Embeddings
If the genetic maps of two species are modelled as permutations of (homologous) genes, the number of chromosomal rearrangements in the form of deletions, block moves, inversions etc. to transform one such perm...
-
Chapter and Conference Paper
Augmenting Suffix Trees, with Applications
Information retrieval and data compression are the two main application areas where the rich theory of string algorithmics plays a fundamental role. In this paper, we consider one algorithmic problem from each...
-
Chapter and Conference Paper
Efficient array partitioning
We consider the problem of partitioning an array of n items into p intervals so that the maximum weight of the intervals is minimized. The currently best known bound for this problem is O(n+p 1+ε ) [HNC92] for an...
