Buchumschlag

Learning-augmented Maximum Independent Set

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Braverman, Vladimir, Dharangutte, Prathamesh, Shah, Vihan, Wang, Chen
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
von: Braverman, Vladimir, et al.
Veröffentlicht: (2024)

Relative Error Fair Clustering in the Weak-Strong Oracle Model
von: Braverman, Vladimir, et al.
Veröffentlicht: (2025)

Learning-Augmented Hierarchical Clustering
von: Braverman, Vladimir, et al.
Veröffentlicht: (2025)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
von: Shah, Vihan
Veröffentlicht: (2026)

Online Learning with Limited Information in the Sliding Window Model
von: Braverman, Vladimir, et al.
Veröffentlicht: (2026)

Misalignment, Learning, and Ranking: Harnessing Users Limited Attention
von: Agarwal, Arpit, et al.
Veröffentlicht: (2024)

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Hardness and Approximation Algorithms for Balanced Districting Problems
von: Dharangutte, Prathamesh, et al.
Veröffentlicht: (2025)

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
von: Fahrbach, Matthew, et al.
Veröffentlicht: (2024)

Learning-augmented Online Algorithm for Two-level Ski-rental Problem
von: Zhang, Keyuan, et al.
Veröffentlicht: (2024)

Learning general Gaussian mixtures with efficient score matching
von: Chen, Sitan, et al.
Veröffentlicht: (2024)

Packing Compact Subgraphs with Applications to Districting
von: Chen, Ho-Lin, et al.
Veröffentlicht: (2026)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
von: Bieliński, Paweł Rafał, et al.
Veröffentlicht: (2026)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
von: Großmann, Ernestine, et al.
Veröffentlicht: (2026)

Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
von: Munteanu, Alexander, et al.
Veröffentlicht: (2024)

The Price of Privacy For Approximating Max-CSP
von: Dharangutte, Prathamesh, et al.
Veröffentlicht: (2026)

Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
von: Aliakbarpour, Maryam, et al.
Veröffentlicht: (2026)

Matroid Algorithms Under Size-Sensitive Independence Oracles
von: Banihashem, Kiarash, et al.
Veröffentlicht: (2026)

Hardness of Maximum Likelihood Learning of DPPs
von: Grigorescu, Elena, et al.
Veröffentlicht: (2022)

Learning-augmented smooth integer programs with PAC-learnable oracles
von: He, Hao-Yuan, et al.
Veröffentlicht: (2026)

Unrolled denoising networks provably learn optimal Bayesian inference
von: Karan, Aayush, et al.
Veröffentlicht: (2024)

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
von: Großmann, Ernestine, et al.
Veröffentlicht: (2024)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2026)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
von: Agarwal, Arpit, et al.
Veröffentlicht: (2024)

A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs
von: Shah, Poojan, et al.
Veröffentlicht: (2025)

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
von: Chaplick, Steven, et al.
Veröffentlicht: (2024)

Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization
von: Nath, Ankur, et al.
Veröffentlicht: (2024)

Towards Optimal Robustness in Learning-Augmented Paging
von: Chen, Peng, et al.
Veröffentlicht: (2026)

Learning-Augmented Moment Estimation on Time-Decay Models
von: Nagawanshi, Soham, et al.
Veröffentlicht: (2026)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2024)

On the Power of Learning-Augmented Search Trees
von: Chen, Jingbang, et al.
Veröffentlicht: (2022)

Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency
von: Chen, Peng, et al.
Veröffentlicht: (2025)

No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting
von: Oki, Taihei, et al.
Veröffentlicht: (2024)

Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets
von: Oki, Taihei, et al.
Veröffentlicht: (2026)

Learning Low Degree Hypergraphs
von: Balkanski, Eric, et al.
Veröffentlicht: (2022)

Learning-Augmented Frequent Directions
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

Multi-Agent Reinforcement Learning with Submodular Reward
von: Chen, Wenjing, et al.
Veröffentlicht: (2026)

Lower Bounds for Greedy Teaching Set Constructions
von: Compton, Spencer, et al.
Veröffentlicht: (2025)

Optimally Improving Cooperative Learning in a Social Setting
von: Haddadan, Shahrzad, et al.
Veröffentlicht: (2024)