Academic Journal
Learning-Augmented Maximum Independent Set
| العنوان: | Learning-Augmented Maximum Independent Set |
|---|---|
| المؤلفون: | Braverman, Vladimir, Dharangutte, Prathamesh, Shah, Vihan, Wang, Chen |
| المساهمون: | Vladimir Braverman and Prathamesh Dharangutte and Vihan Shah and Chen Wang |
| بيانات النشر: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| سنة النشر: | 2024 |
| المجموعة: | DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| مصطلحات موضوعية: | Learning-augmented algorithms, maximum independent set, graph algorithms |
| الوصف: | We study the Maximum Independent Set (MIS) problem on general graphs within the framework of learning-augmented algorithms. The MIS problem is known to be NP-hard and is also NP-hard to approximate to within a factor of n^(1-δ) for any δ > 0. We show that we can break this barrier in the presence of an oracle obtained through predictions from a machine learning model that answers vertex membership queries for a fixed MIS with probability 1/2+ε. In the first setting we consider, the oracle can be queried once per vertex to know if a vertex belongs to a fixed MIS, and the oracle returns the correct answer with probability 1/2 + ε. Under this setting, we show an algorithm that obtains an Õ((√Δ)/ε)-approximation in O(m) time where Δ is the maximum degree of the graph. In the second setting, we allow multiple queries to the oracle for a vertex, each of which is correct with probability 1/2 + ε. For this setting, we show an O(1)-approximation algorithm using O(n/ε²) total queries and Õ(m) runtime. |
| نوع الوثيقة: | article in journal/newspaper conference object |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.24 |
| DOI: | 10.4230/LIPIcs.APPROX/RANDOM.2024.24 |
| الاتاحة: | https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.24 https://nbn-resolving.org/urn:nbn:de:0030-drops-210179 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.24 |
| Rights: | https://creativecommons.org/licenses/by/4.0/legalcode |
| رقم الانضمام: | edsbas.266175FB |
| قاعدة البيانات: | BASE |
| DOI: | 10.4230/LIPIcs.APPROX/RANDOM.2024.24 |
|---|