SMSimon Mauras

Simon Mauras

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Simon Mauras has a total of 4 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

    • 6 January 2021
    • Published by HAL in HAL
    Open Access

    Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

    by Chien-Chung Huang, Naonori Kakimura, Simon Mauras, Yuichi Yoshida

    Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is much gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat 1 − 1 e in the single-pass streaming model. Let n be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio 2

  • Open Access

    How to aggregate Top-lists: Approximation algorithms via scores and average ranks

    by Claire Mathieu, Simon Mauras

    A top-list is a possibly incomplete ranking of elements: only a subset of the elements are ranked, with all unranked elements tied for last. Top-list aggregation, a generalization of the well-known rank aggregation problem, takes as input a collection of top-lists and aggregates them into a single complete ranking, aiming to minimize the number of upsets (pairs ranked in opposite order in the input and in the output). In this paper, we give simple approximation algorithms for top-list aggregation. * We generalize the footrule algorithm for rank aggregation. * Using inspiration from approval voting, we define the score of an element as the frequency with which it is ranked, i.e. appears in an input top-list. We reinterpret Ailon's RepeatChoice algorithm for top-list aggregation using the score of an element and its average rank given that it is ranked. * Using average ranks, we generalize and analyze Borda's algorithm for rank aggregation. * We design a simple 2-phase variant of the Generalized Borda's algorithm, roughly sorting by scores and breaking ties by average ranks. * We then design another 2-phase variant in which in order to break ties we use, as a black box, the Mathieu-Schudy PTAS for rank aggregation, yielding a PTAS for top-list aggregation. * Finally, we discuss the special case in which all input lists have constant length.