Algorithms for stable and perturbation-resilient problems

No abstract is available for this paper.

• Publication year

  2017

• Venue

  Symposium on the Theory of Computing

• Publication date

  2017-06-19

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/3055399.3055487
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Beyond worst-case analysis: observed low depth for a P-complete problem

  2018cited by this paper
• Simplex Transformations and the Multiway Cut Problem

  2017cited by this paper
• An Improved Integrality Gap for the Călinescu-Karloff-Rabani Relaxation for Multiway Cut

  2016cited by this paper
• k-center Clustering under Perturbation Resilience

  2015influential reference
• CS264: Beyond Worst-Case Analysis Lecture #8: Exact Recovery in Stable Cut Instances

  2014cited by this paper
• Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut

  2013influential reference
• Multiway cut, pairwise realizable distributions, and descending thresholds

  2013cited by this paper
• On the practically interesting instances of MAXCUT

  2012cited by this paper
• Data stability in clustering: A closer look

  2011cited by this paper
• Clustering under Perturbation Resilience

  2011influential reference
• On the Complexity of the Metric TSP under Stability Considerations

  2011influential reference
• Center-based clustering under perturbation stability

  2010cited by this paper
• Are Stable Instances Easy?

  2009influential reference
• Linear degree extractors and the inapproximability of max clique and chromatic number

  2006cited by this paper
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion

  2006cited by this paper
• Robust algorithms for restricted domains

  2001cited by this paper
• A lower bound of 8/(7+(1/k)-1) on the integrality ratio of the Calinescu-Karloff-Rabani relaxation for multiway cut

  2000cited by this paper
• Clique is hard to approximate withinn1−ε

  1999cited by this paper
• An improved approximation algorithm for multiway cut

  1998influential reference
• Clique is hard to approximate within n/sup 1-/spl epsiv//

  1996cited by this paper
• Clique is hard to approximate within n1-epsilon

  1996cited by this paper

• Non-Center-Based Clustering Under Bilu-Linial Stability

  2025cites this paper
• On the Adversarial Robustness of Benjamini Hochberg

  2025cites this paper
• Connected k-Median with Disjoint and Non-disjoint Clusters

  2025cites this paper
• Bilevel Models for Adversarial Learning and a Case Study

  2025cites this paper
• Low-Distortion Clustering with Ordinal and Limited Cardinal Information

  2024cites this paper
• Robust Object Detection Under Smooth Perturbations in Precision Agriculture

  2024cites this paper
• A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering

  2024influential citation
• Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds

  2024cites this paper
• On Generalization Bounds for Projective Clustering

  2023cites this paper
• One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes

  2022cites this paper
• Fair Representation Clustering with Several Protected Classes

  2022cites this paper
• Phylogenetic CSPs are Approximation Resistant

  2022cites this paper
• Massively Parallel k-Means Clustering for Perturbation Resilient Instances

  2022cites this paper
• Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances

  2021cites this paper
• Strategyproof Facility Location in Perturbation Stable Instances

  2021influential citation
• Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries

  2021influential citation
• New Aspects of Beyond Worst-Case Analysis

  2021cites this paper
• Robust k-center with two types of radii

  2021cites this paper
• An exact algorithm for stable instances of the $ k $-means problem with penalties in fixed-dimensional Euclidean space

  2021cites this paper
• Graph cuts always find a global optimum (with a catch)

  2020cites this paper
• A Relational Gradient Descent Algorithm For Support Vector Machine Training

  2020cites this paper
• Mechanism Design for Perturbation Stable Combinatorial Auctions

  2020cites this paper
• Clustering under Perturbation Stability in Near-Linear Time

  2020influential citation
• Algorithmic Game Theory: 13th International Symposium, SAGT 2020, Augsburg, Germany, September 16–18, 2020, Proceedings

  2020cites this paper
• Graph Cuts Always Find a Global Optimum for Potts Models (With a Catch)

  2020cites this paper
• Certified Algorithms: Worst-Case Analysis and Beyond

  2020cites this paper
• On Perturbation Resilience of Non-uniform k-Center

  2020cites this paper
• Beyond the Worst-Case Analysis of Algorithms

  2019influential citation
• On semi-supervised active clustering of stable instances with oracles

  2019cites this paper
• Digging deeper into clustering and covering problems

  2019cites this paper
• Solving (k-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(k-1)$$\end{document}-stable instances of k-terminal cut

  2019cites this paper
• A Polynomial-Time Algorithm for $(2-2/k)$-stable Instances of the k-terminal cut Problem

  2018cites this paper
• Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations

  2018influential citation
• On Euclidean $k$-Means Clustering with $\alpha$-Center Proximity

  2018influential citation
• Clustering Perturbation Resilient Instances

  2018influential citation
• Algorithms for Analyzing Spatio-Temporal Data

  2018cites this paper
• Bilu-Linial stability, certified algorithms and the Independent Set problem

  2018influential citation
• Clustering Redemption-Beyond the Impossibility of Kleinberg's Axioms

  2018cites this paper
• Shortest path queries, graph partitioning and covering problems in worst and beyond worst case settings

  2018influential citation
• Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means

  2018influential citation
• Beyond worst-case analysis: observed low depth for a P-complete problem

  2018cites this paper
• Optimality of Approximate Inference Algorithms on Stable Instances

  2017influential citation
• Robust Communication-Optimal Distributed Clustering Algorithms

  2017cites this paper
• Clustering Stable Instances of Euclidean k-means

  2017cites this paper
• Alpha-expansion is Exact on Stable Instances

  2017influential citation
• CS 264 : Beyond Worst-Case Analysis Lecture # 6 : Perturbation-Stable Clustering ∗

  2017cites this paper
• A Fast Approximation Scheme for Low-Dimensional k-Means

  2017cites this paper
• Stability and Recovery for Independence Systems

  2017cites this paper
• On the Local Structure of Stable Clustering Instances

  2017cites this paper
• Clustering under Local Stability: Bridging the Gap between Worst-Case and Beyond Worst-Case Analysis

  2017influential citation
• Nash Equilibria in Perturbation-Stable Games

  2017cites this paper
• Approximate Correlation Clustering Using Same-Cluster Queries

  2017cites this paper
• k-center Clustering under Perturbation Resilience

  2015influential citation