scientific article; zbMATH DE number 7525444
From MaRDI portal
Publication:5075740
DOI10.4230/LIPIcs.ESA.2019.7MaRDI QIDQ5075740
Chen Dan, Vaggos Chatziafratis, Haris Angelidakis, Pranjal Awasthi, Avrim L. Blum
Publication date: 11 May 2022
Full work available at URL: https://arxiv.org/abs/1810.08414
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
independent setvertex coverperturbation resiliencemultiway cutbeyond worst-case analysisBilu-Linial stability
Related Items (1)
Cites Work
- Center-based clustering under perturbation stability
- Approximation algorithms for the weighted independent set problem in sparse graphs
- Efficient bounds for the stable set, vertex cover and set packing problems
- NP is as easy as detecting unique solutions
- A partial k-arboretum of graphs with bounded treewidth
- Approximating the independence number via the \(\vartheta\)-function
- Heuristics for semirandom graph problems
- Tree-width and the Sherali-Adams operator
- Convex Relaxations and Integrality Gaps
- Are Stable Instances Easy?
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Sum-of-squares Lower Bounds for Planted Clique
- On the Lovász Theta function for Independent Sets in Sparse Graphs
- On the practically interesting instances of MAXCUT
- On the Complexity of the Metric TSP under Stability Considerations
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Approximation Resistance from Pairwise-Independent Subgroups
- Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- Vertex packings: Structural properties and algorithms
- Approximation algorithms for NP-complete problems on planar graphs
- Approximations of Weighted Independent Set and Hereditary Subset Problems
- LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
- k-Center Clustering Under Perturbation Resilience
- Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
- Approximating Maximum Clique by Removing Subgraphs
- Coloring Random and Semi-Random k-Colorable Graphs
- Algorithms for stable and perturbation-resilient problems
- Stability and Recovery for Independence Systems
- Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS
- Approximating independent sets in sparse graphs
- Bilu–Linial Stable Instances of Max Cut and Minimum Multiway Cut
- Clustering under Perturbation Resilience
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication:
