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

DOI10.4230/LIPICS.ESA.2019.7MaRDI QIDQ5075740zbMATH OpenFDO

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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

Cites work

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

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)