Skip to main content

31 Result(s)

within S. Muthukrishnan Remove this filter Computer Science Remove this filter Discrete Mathematics in Computer Science Remove this filter

previous disabled Page of 2
and

  1. No Access

    Chapter and Conference Paper

    Graph editing to bipartite interval graphs: Exact and asymptotic bounds

    Graph editing problems deal with the complexity of transforming a given input graph G from class Q to any graph H in the target class H by adding and deleting edges. Motivated by a physical map** scenario in Co...

    K. Cirino, S. Muthukrishnan… in Foundations of Software Technology and The… (1997)

  2. No Access

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

    Yossi Matias, S. Muthukrishnan, Süleyman Cenk Sahinalp, Jacob Ziv in Algorithms — ESA’ 98 (1998)

  3. No Access

    Chapter and Conference Paper

    Second-Order Methods for Distributed Approximate Single- and Multicommodity Flow

    We study local-control algorithms for maximum flow and multicommodity flow problems in distributed networks. We propose a second-order method for accelerating the convergence of the “first-order” distributed a...

    S. Muthukrishnan, Torsten Suel in Randomization and Approximation Techniques… (1998)

  4. No Access

    Chapter and Conference Paper

    An Improved Algorithm for Sequence Comparison with Block Reversals

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

    S. Muthukrishnan, S. Cenk Sahinalp in LATIN 2002: Theoretical Informatics (2002)

  5. No Access

    Chapter and Conference Paper

    Estimating Rarity and Similarity over Data Stream Windows

    In the windowed data stream model, we observe items coming in over time. At any time t, we consider the window of the last N observations a t-(N-1), a t-(N-2), . . ...

    Mayur Datar, S. Muthukrishnan in Algorithms — ESA 2002 (2002)

  6. No Access

    Chapter and Conference Paper

    Range Searching in Categorical Data: Colored Range Searching on Grid

    Range searching, a fundamental problem in numerous applications areas, has been widely studied in computational geometry and spatial databases. Given a set of geometric objects, a typical range query asks for ...

    Pankaj K. Agarwal, Sathish Govindarajan, S. Muthukrishnan in Algorithms — ESA 2002 (2002)

  7. No Access

    Book and Conference Proceedings

    Combinatorial Pattern Matching

    15th Annual Symposium, CPM 2004, Istanbul, Turkey, July 5-7, 2004. Proceedings

    Suleyman Cenk Sahinalp, S. Muthukrishnan… in Lecture Notes in Computer Science (2004)

  8. No Access

    Chapter and Conference Paper

    Workload-Optimal Histograms on Streams

    A histogram is a piecewise-constant approximation of an observed data distribution. A histogram is used as a small-space, approximate synopsis of the underlying data distribution, which is often too large to b...

    S. Muthukrishnan, M. Strauss, X. Zheng in Algorithms – ESA 2005 (2005)

  9. No Access

    Chapter and Conference Paper

    Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods

    Much recent work in the theoretical computer science, linear algebra, and machine learning has considered matrix decompositions of the following form: given an m ×n matrix A, decompose it as a product of three ma...

    Petros Drineas, Michael W. Mahoney, S. Muthukrishnan in Algorithms – ESA 2006 (2006)

  10. No Access

    Chapter and Conference Paper

    Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods

    Given an m ×n matrix A and an integer k less than the rank of A, the “best” rank k approximation to A that minimizes the error with respect to the Frobenius norm is A k ...

    Petros Drineas, Michael W. Mahoney… in Approximation, Randomization, and Combinat… (2006)

  11. No Access

    Chapter and Conference Paper

    Estimating Entropy and Entropy Norm on Data Streams

    We consider the problem of computing information theoretic functions such as entropy on a data stream, using sublinear space.

    Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan in STACS 2006 (2006)

  12. No Access

    Chapter and Conference Paper

    Combinatorial Algorithms for Compressed Sensing

    In sparse approximation theory, the fundamental problem is to reconstruct a signal A ∈ ℝ n from linear measurements 〈A ψ i

    Graham Cormode, S. Muthukrishnan in Structural Information and Communication Complexity (2006)

  13. No Access

    Chapter and Conference Paper

    In-Place Suffix Sorting

    Given string T = T[1,...,n], the suffix sorting problem is to lexicographically sort the suffixes T[i,...,n] for all i. This problem is central to the construction of suffix arrays and trees with many application...

    Gianni Franceschini, S. Muthukrishnan in Automata, Languages and Programming (2007)

  14. No Access

    Chapter and Conference Paper

    Radix Sorting with No Extra Space

    It is well known that n integers in the range [1,n c ] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1,

    Gianni Franceschini, S. Muthukrishnan, Mihai Pǎtraşcu in Algorithms – ESA 2007 (2007)

  15. No Access

    Chapter and Conference Paper

    Bidding to the Top: VCG and Equilibria of Position-Based Auctions

    Many popular search engines run an auction to determine the placement of advertisements next to search results. Current auctions at Google and Yahoo! let advertisers specify a single amount as their bid in the...

    Gagan Aggarwal, Jon Feldman, S. Muthukrishnan in Approximation and Online Algorithms (2007)

  16. No Access

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

    Sariel Har-Peled, S. Muthukrishnan in Algorithms - ESA 2008 (2008)

  17. No Access

    Chapter and Conference Paper

    Internet Ad Auctions: Insights and Directions

    On the Internet, there are advertisements (ads) of different kinds: image, text, video and other specially marked objects that are distinct from the underlying content of the page. There is an industry behind ...

    S. Muthukrishnan in Automata, Languages and Programming (2008)

  18. No Access

    Chapter and Conference Paper

    A Truthful Mechanism for Offline Ad Slot Scheduling

    We consider the Offline Ad Slot Scheduling problem, where advertisers must be scheduled to sponsored search slots during a given period of time. Advertisers specify a budget constraint, as well as a maximum cost ...

    Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, Martin Pál in Algorithmic Game Theory (2008)

  19. No Access

    Chapter and Conference Paper

    Bidding on Configurations in Internet Ad Auctions

    In Internet advertising, a configuration of ads is determined by the seller, and advertisers buy spaces in the configuration. In this paper, motivated by sponsored search ads, we propose an auction where adver...

    S. Muthukrishnan in Computing and Combinatorics (2009)

  20. No Access

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

    Vahab Mirrokni, S. Muthukrishnan, Uri Nadav in LATIN 2010: Theoretical Informatics (2010)

previous disabled Page of 2