TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. browse.metadata.journals.breadcrumbs

Browsing by browse.metadata.journals "ACM transactions on algorithms"

Now showing1 - 2 of 2
Results Per Page
Sort Options
  • Some of the metrics are blocked by your 
    consent settings
    Publicationwithout files
    Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
    (Association for Computing Machinery (ACM), 2024-01-22)
    Chalermsook, Parinya  
    ;
    Kaul, Matthias  orcid-logo
    ;
    Mnich, Matthias  orcid-logo
    ;
    Spoerhase, Joachim  
    ;
    Uniyal, Sumedha  
    ;
    Vaz, Daniel  
    The fundamental Sparsest Cut problem takes as input a graph G together with edge capacities and demands, and seeks a cut that minimizes the ratio between the capacities and demands across the cuts. For n-vertex graphs G of treewidth k, Chlamtáč, Krauthgamer, and Raghavendra (APPROX 2010) presented an algorithm that yields a factor-22k approximation in time 2O(k) · nO(1). Later, Gupta, Talwar and Witmer (STOC 2013) showed how to obtain a 2-approximation algorithm with a blown-up run time of nO(k). An intriguing open question is whether one can simultaneously achieve the best out of the aforementioned results, that is, a factor-2 approximation in time 2O(k) · nO(1). In this paper, we make significant progress towards this goal, via the following results: (i) A factor-O(k2) approximation that runs in time 2O(k) · nO(1), directly improving the work of Chlamtáč et al. while keeping the run time single-exponential in k. (ii) For any ε ∈ (0, 1], a factor-O(1/ε2) approximation whose run time is 2O(k1+ε/ε)⋅nO(1), implying a constant-factor approximation whose run time is nearly single-exponential in k and a factor-O(log 2k) approximation in time kO(k) · nO(1). Key to these results is a new measure of a tree decomposition that we call combinatorial diameter, which may be of independent interest.
    Publicationtype: Journal Article
    Citation Publisher Version:ACM Transactions in Algorithms (2024)
    Publisher DOI:10.1145/3632623
      105
  • Some of the metrics are blocked by your 
    consent settings
    Publicationwithout files
    Domination when the stars are out
    (Association for Computing Machinery, 2019)
    Hermelin, Danny  
    ;
    Mnich, Matthias  orcid-logo
    ;
    Leeuwen, Erik Jan van  
    ;
    Woeginger, Gerhard  
    Publicationtype: Journal Article
    Citation Publisher Version:ACM Transactions on Algorithms (2019)
    Publisher DOI:10.1145/3301445
      151
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback