Improved Approximations for Hard Graph Problems using Predictions

• URL: http://arxiv.org/abs/2505.23967v1
• Date: Thu, 29 May 2025 19:47:09 GMT
• Title: Improved Approximations for Hard Graph Problems using Predictions
• Authors: Anders Aamand, Justin Y. Chen, Siddharth Gollapudi, Sandeep Silwal, Hao Wu,
• Abstract summary: We design improved approximation algorithms for NP-hard graph problems by incorporating predictions.<n>Our prediction model builds upon and extends the $varepsilon$-prediction framework by Cohen-Addad, d'Orsi, Gupta, Lee, and Panigrahi.
• Score: 13.827632579682795
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We design improved approximation algorithms for NP-hard graph problems by incorporating predictions (e.g., learned from past data). Our prediction model builds upon and extends the $\varepsilon$-prediction framework by Cohen-Addad, d'Orsi, Gupta, Lee, and Panigrahi (NeurIPS 2024). We consider an edge-based version of this model, where each edge provides two bits of information, corresponding to predictions about whether each of its endpoints belong to an optimal solution. Even with weak predictions where each bit is only $\varepsilon$-correlated with the true solution, this information allows us to break approximation barriers in the standard setting. We develop algorithms with improved approximation ratios for MaxCut, Vertex Cover, Set Cover, and Maximum Independent Set problems (among others). Across these problems, our algorithms share a unifying theme, where we separately satisfy constraints related to high degree vertices (using predictions) and low-degree vertices (without using predictions) and carefully combine the answers.

Related papers

• Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model [0.688204255655161]
  We study the online unweighted bipartite matching problem in the random arrival order model.<n>Our learning-augmented algorithm achieves $(1-o(1))$-consistency and $(-o(1))$-robustness.
  arXiv  Detail & Related papers  (2025-11-28T17:31:11Z)
• Learning-Augmented Streaming Algorithms for Correlation Clustering [6.0943362338120055]
  We study streaming algorithms for Correlation Clustering.<n>We give the first learning-augmented streaming algorithms for the problem on both complete and general graphs.
  arXiv  Detail & Related papers  (2025-10-12T17:04:40Z)
• Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
  We study learning problems on correlated block models with two balanced communities.<n>Our main result gives the first efficient algorithm for graph matching in this setting.<n>We extend this to an efficient algorithm for exact graph matching whenever this is information-theoretically possible.
  arXiv  Detail & Related papers  (2024-12-03T18:36:45Z)
• Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
  We use predictions to improve over approximation guarantees of classic algorithms. Our algorithms produce optimal solutions when provided with perfect predictions. Although we show our approach to be optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds.
  arXiv  Detail & Related papers  (2024-11-25T17:31:34Z)
• Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
  We make novel use of sparsification techniques from the non-private streaming and static algorithms literature to achieve new results in the sublinear space, continual release setting.<n>This includes algorithms for densest subgraph, maximum matching, and the first continual release $k$-core decomposition algorithm.
  arXiv  Detail & Related papers  (2024-07-24T20:15:07Z)
• Enhancing Hyperedge Prediction with Context-Aware Self-Supervised Learning [57.35554450622037]
  We propose a novel hyperedge prediction framework (CASH)<n>CASH employs context-aware node aggregation to capture complex relations among nodes in each hyperedge for (C1) and (2) self-supervised contrastive learning in the context of hyperedge prediction to enhance hypergraph representations for (C2)<n>Experiments on six real-world hypergraphs reveal that CASH consistently outperforms all competing methods in terms of the accuracy in hyperedge prediction.
  arXiv  Detail & Related papers  (2023-09-11T20:06:00Z)
• Learning-Based Heuristic for Combinatorial Optimization of the Minimum Dominating Set Problem using Graph Convolutional Networks [1.5469452301122175]
  A dominating set of a graph $mathcalG=(V, E) is a subset of vertices $SsubseteqmathcalV setminus S$ outside the dominating set. We propose a novel learning-based approach to compute solutions for the minimum dominating set problem using graph$ convolutional networks.
  arXiv  Detail & Related papers  (2023-06-06T06:22:42Z)
• MAgNet: Mesh Agnostic Neural PDE Solver [68.8204255655161]
  Climate predictions require fine-temporal resolutions to resolve all turbulent scales in the fluid simulations. Current numerical model solveers PDEs on grids that are too coarse (3km to 200km on each side) We design a novel architecture that predicts the spatially continuous solution of a PDE given a spatial position query.
  arXiv  Detail & Related papers  (2022-10-11T14:52:20Z)
• The Neural-Prediction based Acceleration Algorithm of Column Generation for Graph-Based Set Covering Problems [20.1479227701035]
  We propose an improved column generation algorithm with neural prediction (CG-P) for solving graph-based set covering problems. We leverage a graph neural network based neural prediction model to predict the probability to be included in the final solution for each edge. We evaluate the CG-P algorithm on railway crew scheduling problems and it outperforms the baseline column generation algorithm.
  arXiv  Detail & Related papers  (2022-07-04T13:46:59Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  We study the fundamental online $k$-server problem in a learning-augmented setting. We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
  arXiv  Detail & Related papers  (2021-03-02T11:04:33Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.