Bilu-Linial stability, certified algorithms and the independent set problem

DOI10.4230/LIPICS.ESA.2019.7MaRDI QIDQ5075740FDOQ5075740

Authors: Haris Angelidakis, Pranjal Awasthi, Vaggos Chatziafratis, Chen Dan, Avrim Blum 

Publication date: 11 May 2022

Full work available at URL: https://arxiv.org/abs/1810.08414

Recommendations

• Bilu-Linial stable instances of max cut and minimum multiway cut
• Are stable instances easy?
• Perturbation Resilience
• Stability for maximal independent sets
• Algorithms for stable and perturbation-resilient problems

zbMATH Keywords

independent setvertex coverperturbation resiliencemultiway cutbeyond worst-case analysisBilu-Linial stability

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Title not available (Why is that?)
• A partial k-arboretum of graphs with bounded treewidth
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Approximation algorithms for NP-complete problems on planar graphs
• Approximating Maximum Clique by Removing Subgraphs
• Title not available (Why is that?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Vertex packings: Structural properties and algorithms
• Title not available (Why is that?)
• NP is as easy as detecting unique solutions
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Convex relaxations and integrality gaps
• Inapproximability of vertex cover and independent set in bounded degree graphs
• Approximating the independence number via the \(\vartheta\)-function
• On the Lovász theta function for independent sets in sparse graphs
• Approximation algorithms for the weighted independent set problem in sparse graphs
• Efficient bounds for the stable set, vertex cover and set packing problems
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
• Tree-width and the Sherali-Adams operator
• On the Complexity of the Metric TSP under Stability Considerations
• Center-based clustering under perturbation stability
• Title not available (Why is that?)
• Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS
• Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
• Are stable instances easy?
• Heuristics for semirandom graph problems
• Coloring Random and Semi-Random k-Colorable Graphs
• Approximating independent sets in sparse graphs
• Bilu-Linial stable instances of max cut and minimum multiway cut
• Sum-of-squares Lower Bounds for Planted Clique
• Approximation Resistance from Pairwise-Independent Subgroups
• \(k\)-center clustering under perturbation resilience
• LP-based robust algorithms for noisy minor-free and bounded treewidth graphs
• Statistical algorithms and a lower bound for detecting planted cliques
• Algorithms for stable and perturbation-resilient problems
• Title not available (Why is that?)
• On the practically interesting instances of MAXCUT
• Stability and recovery for independence systems

Cited In (2)

• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Preprocessing to reduce the search space: antler structures for feedback vertex set

This page was built for publication: Bilu-Linial stability, certified algorithms and the independent set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075740)