Journal: SIAM Journal on Computing

Abbreviation

SIAM j. comput. (Print)

Publisher

SIAM

Journal Volumes

ISSN

0097-5397
1095-7111

Description

Filters

Reset filters

Search Results

Publications 1 - 10 of 32
  • On the Number of Crossing-Free Matchings, Cycles, and Partitions
    Item type: Journal Article
    Sharir, Micha; Welzl, Emo (2006)
    SIAM Journal on Computing
  • Polynomial-Time Computation of Homotopy Groups and Postnikov Systems in Fixed Dimension
    Item type: Journal Article
    Čadek, Martin; Krčál, Marek; Matoušek, Jiří; et al. (2014)
    SIAM Journal on Computing
  • On range searching with semialgebraic sets II
    Item type: Journal Article
    Agarwal, Pankaj K.; Matoušek, Jiří; Sharir, Micha (2013)
    SIAM Journal on Computing
  • On Some Distance Problems in Fixed Orientations
    Item type: Journal Article
    Widmayer, Peter; Wu, Y.F.; Wong, C.K. (1987)
    SIAM Journal on Computing
  • Nondeterministic communication with a limited number of advice bits
    Item type: Journal Article
    Hromkovič, Juraj; Schnitger, Georg (2003)
    SIAM Journal on Computing
  • An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
    Item type: Journal Article
    Traub, Vera; Vygen, Jens (2022)
    SIAM Journal on Computing
    We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and Ve'\gh [J. ACM, 67 (2020), 37]. We improve on each part of this algorithm. We avoid the reduction to irreducible instances and thus obtain a simpler and much better reduction to vertebrate pairs. We also show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio. Overall we improve the approximation ratio from 506 to 22 + \varepsilon for any \varepsilon > 0. This also improves the upper bound on the integrality ratio from 319 to 22.
  • A Framework for the Secretary Problem on the Intersection of Matroids
    Item type: Journal Article
    Feldman, Moran; Svensson, Ola; Zenklusen, Rico (2022)
    SIAM Journal on Computing
    The secretary problem became one of the most prominent online selection problems due to its numerous applications in online mechanism design. The task is to select a maximum weight subset of elements subject to given constraints, where elements arrive one-by-one in random order, revealing a weight upon arrival. The decision whether to select an element has to be taken immediately after its arrival. The different applications that map to the secretary problem ask for different constraint families to be handled. The most prominent ones are matroid constraints, which both capture many relevant settings and admit strongly competitive secretary algorithms. However, dealing with more involved constraints proved to be much more difficult, and strong algorithms are known only for a few specific settings. In this paper, we present a general framework for dealing with the secretary problem over the intersection of several matroids. This framework allows us to combine and exploit the large set of matroid secretary algorithms known in the literature. As one consequence, we get constant-competitive secretary algorithms over the intersection of any constant number of matroids whose corresponding (single-)matroid secretary problems are currently known to have a constant-competitive algorithm. Moreover, we show that our results extend to submodular objectives.
  • Distributed Verification and Hardness of Distributed Approximation
    Item type: Journal Article
    Das Sarma, Atish; Holzer, Stephan; Kor, Liah; et al. (2012)
    SIAM Journal on Computing
  • Binary space partitions or line segments with a limited number of directions
    Item type: Journal Article
    Toth, Casaba D. (2003)
    SIAM Journal on Computing
  • Zone diagrams
    Item type: Journal Article
    Asano, Tetsuo.; Matoušek, Jiří; Tokuyama, Takeshi (2007)
    SIAM Journal on Computing
Publications 1 - 10 of 32