Q5075740
type: Item
instance of: scholarly article
author: Haris Angelidakis
author: Pranjal Awasthi
author: Vaggos Chatziafratis
author: Chen Dan
author: Avrim Blum
publication date: 2022-05-11T00:00:00Z
full work available at URL: https://arxiv.org/abs/1810.08414
Mathematics Subject Classification ID: 68Wxx
zbMATH DE Number: 7525444
zbMATH Keywords: Bilu-Linial stability
zbMATH Keywords: perturbation resilience
zbMATH Keywords: beyond worst-case analysis
zbMATH Keywords: independent set
zbMATH Keywords: vertex cover
zbMATH Keywords: multiway cut
MaRDI profile type: MaRDI publication profile
cites work: Approximating the independence number via the \(\vartheta\)-function
cites work: Q4705344
cites work: Algorithms for stable and perturbation-resilient problems
cites work: Q3002828
cites work: Center-based clustering under perturbation stability
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: k-Center Clustering Under Perturbation Resilience
cites work: Clustering under Perturbation Resilience
cites work: Approximating independent sets in sparse graphs
cites work: On the Lovász Theta function for Independent Sets in Sparse Graphs
cites work: LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
cites work: Q3128896
cites work: Tree-width and the Sherali-Adams operator
cites work: On the practically interesting instances of MAXCUT
cites work: Are stable instances easy?
cites work: Coloring Random and Semi-Random k-Colorable Graphs
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Q5782525
cites work: Approximation Resistance from Pairwise-Independent Subgroups
cites work: Stability and Recovery for Independence Systems
cites work: Q5009501
cites work: Convex Relaxations and Integrality Gaps
cites work: Approximating Maximum Clique by Removing Subgraphs
cites work: Heuristics for semirandom graph problems
cites work: Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
cites work: Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS
cites work: Approximations of Weighted Independent Set and Hereditary Subset Problems
cites work: Q4698692
cites work: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: Approximation algorithms for the weighted independent set problem in sparse graphs
cites work: Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
cites work: Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
cites work: Bilu–Linial Stable Instances of Max Cut and Minimum Multiway Cut
cites work: Sum-of-squares Lower Bounds for Planted Clique
cites work: On the Complexity of the Metric TSP under Stability Considerations
cites work: Vertex packings: Structural properties and algorithms
cites work: NP is as easy as detecting unique solutions
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number
DOI: 10.4230/LIPICS.ESA.2019.7
description: scientific article; zbMATH DE number 7525444