Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Better Trees for Santa Claus
 
conference paper

Better Trees for Santa Claus

Bamas, Etienne  
•
Rohwedder, Lars
Servedio, RA
•
Saha, B
January 1, 2023
Proceedings Of The 55Th Annual Acm Symposium On Theory Of Computing, Stoc 2023
55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem we are given a directed graph with sources and sinks and our goal is to find vertex disjoint arborescences rooted in the sources such that at each non-sink vertex of an arborescence the out-degree is at least k, where k is to be maximized.|This problem is of particular interest, since it appears to capture much of the difficulty of the Santa Claus problem: (1) like in the Santa Claus problem the configuration LP has a large integrality gap in this case and (2) previous progress by Bateni et al. was quickly generalized to the Santa Claus problem (Chakrabarty et al. [FOCS'09]). These results remain the state-of-the-art both for the Santa Claus problem and for max-min degree arborescence and they yield a polylogarithmic approximation in quasi-polynomial time. We present an exponential improvement to this, a poly(log log n)-approximation in quasi-polynomial time for the max-min degree arborescence problem. To the best of our knowledge, this is the first example of breaking the logarithmic barrier for a special case of the Santa Claus problem, where the configuration LP cannot be utilized.|The main technical novelty of our result are locally good solutions: informally, we show that it suffices to find a poly(log n)approximation that locally has stronger guarantees. We use a liftand-project type of LP and randomized rounding, which were also used by Bateni et al., but unlike previous work we integrate careful pruning steps in the rounding. In the proof we extensively apply Lovasz Local Lemma and a local search technique, both of which were previously used only in the context of the configuration LP.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/3564246.3585174
Web of Science ID

WOS:001064640700151

Author(s)
Bamas, Etienne  
Rohwedder, Lars
Editors
Servedio, RA
•
Saha, B
Date Issued

2023-01-01

Publisher

Assoc Computing Machinery

Publisher place

New York

Published in
Proceedings Of The 55Th Annual Acm Symposium On Theory Of Computing, Stoc 2023
ISBN of the book

978-1-4503-9913-5

Start page

1862

End page

1875

Subjects

Technology

•

Physical Sciences

•

Max-Min

•

Allocation

•

Fairness

•

Lovasz Local Lemma

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL2  
Event nameEvent placeEvent date
55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

Orlando, FL

JUN 20-23, 2023

FunderGrant Number

Swiss National Science Foundation

200021-184656/1

Dutch Research Council (NWO) project "The Twilight Zone of Efficiency: Optimality of Quasi-Polynomial Time Algorithms"

OCEN.W.21.268

Available on Infoscience
February 20, 2024
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/204330
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés