Home

José A. Soto

  1. Generalizations and Variants of the Largest Non-crossing Matching Problem in Random Bipartite Graphs.

    Wed, 05/04/2011 - 15:01 — SomNambul
    Authors: Marcos Kiwi, José A. Soto
    Subjects: Combinatorics
    Abstract

    We are interested in the statistics of the length of the longest increasing
    subsequence of 2-rowed lexicographically sorted arrays chosen according to
    distinct families of distributions D = (D_n)_n, and when n goes to infinity.
    This framework encompasses well studied problems such as the so called Longest
    Increasing Subsequence problem, the Longest Common Subsequence problem,
    problems concerning directed bond percolation models, among others.

  2. Matroid Secretary Problem in the Random Assignment Model.

    Wed, 07/14/2010 - 15:02 — SomNambul
    Authors: José A. Soto
    Subjects: Data Structures and Algorithms
    Abstract

    In the Matroid Secretary Problem, introduced by Babaioff et al. [SODA 2007],
    the elements of a given matroid are presented to an online algorithm in random
    order. When an element is revealed, the algorithm learns its weight and decides
    whether or not to select it under the restriction that the selected elements
    form an independent set in the matroid. The objective is to maximize the total
    weight of the chosen elements. In the most studied version of this problem, the
    algorithm has no information about the weights beforehand. We refer to this as
    the zero information model.

  3. Symmetric Submodular Function Minimization Under Hereditary Family Constraints.

    Wed, 07/14/2010 - 15:02 — SomNambul
    Authors: Michel X. Goemans, José A. Soto
    Subjects: Data Structures and Algorithms
    Abstract

    We present an efficient algorithm to find non-empty minimizers of a symmetric
    submodular function over any family of sets closed under inclusion. This for
    example includes families defined by a cardinality constraint, a knapsack
    constraint, a matroid independence constraint, or any combination of such
    constraints. Our algorithm make $O(n^3)$ oracle calls to the submodular
    function where $n$ is the cardinality of the ground set.

Math-arch

Syndicate content