Approximation Algorithms and New Models for Clustering and Learning

No abstract is available for this paper.

• Publication year

  2013

• Venue

  Unknown venue

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1184/r1/6714833.v1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Clustering under approximation stability

  2013cited by this paper
• Robust hierarchical clustering

  2013cited by this paper
• Restriction access

  2012cited by this paper
• Efficient Active Algorithms for Hierarchical Clustering

  2012cited by this paper
• Reliable Agnostic Learning

  2012influential reference
• Randomness and Non-determinism

  2012cited by this paper
• Agglomerative Bregman Clustering

  2012cited by this paper
• Learning DNF Expressions from Fourier Spectrum

  2012influential reference
• Data reduction for weighted and outlier-resistant clustering

  2012influential reference
• Learning Using Local Membership Queries

  2012cited by this paper
• Smoothed Analysis of the k-Means Method

  2011influential reference
• Efficiently learning mixtures of two Gaussians

  2010cited by this paper
• Supervised Clustering

  2010cited by this paper
• Efficient Clustering with Limited Distance Information

  2010cited by this paper
• Settling the Polynomial Learnability of Mixtures of Gaussians

  2010cited by this paper
• Hardness results for agnostically learning low-degree polynomial threshold functions

  2010cited by this paper
• Stability Yields a PTAS for k-Median and k-Means Clustering

  2010influential reference
• Clustering with Spectral Norm and the k-Means Algorithm

  2010cited by this paper
• Improved Guarantees for Agnostic Learning of Disjunctions.

  2010influential reference
• Center-based clustering under perturbation stability

  2010cited by this paper
• Bayesian Maximum Margin Clustering

  2010cited by this paper
• Polynomial Learning of Distribution Families

  2010cited by this paper
• Learning Halfspaces with Malicious Noise

  2009cited by this paper
• Potential-Based Agnostic Boosting

  2009cited by this paper
• New Results for Random Walk Learning

  2009cited by this paper
• The Top Ten Algorithms in Data Mining

  2009cited by this paper
• Finding Low Error Clusterings

  2009influential reference
• A Uniqueness Theorem for Clustering

  2009cited by this paper
• Distribution-Specific Agnostic Boosting

  2009cited by this paper
• Approximate clustering without the approximation

  2009cited by this paper
• Are Stable Instances Easy?

  2009cited by this paper
• Agnostic Clustering

  2009cited by this paper
• Learning and Smoothed Analysis

  2009cited by this paper
• Agnostic Learning of Monomials by Halfspaces Is Hard

  2009cited by this paper
• Streaming k-means approximation

  2009cited by this paper
• On the Power of Membership Queries in Agnostic Learning

  2009cited by this paper
• On agnostic boosting and parity learning

  2008cited by this paper
• k-means Requires Exponentially Many Iterations Even in the Plane

  2008cited by this paper
• Clustering with Interactive Feedback

  2008influential reference
• The hardness of k-means clustering

  2008cited by this paper
• Isotropic PCA and Affine-Invariant Clustering

  2008cited by this paper
• A discriminative framework for clustering via similarity functions

  2008influential reference
• Efficiency and computational limitations of learning algorithms

  2007cited by this paper
• k-means++: the advantages of careful seeding

  2007cited by this paper
• How slow is the k-means method?

  2006cited by this paper
• New Results for Learning Noisy Parities and Halfspaces

  2006cited by this paper
• Learning a circuit by injecting values

  2006cited by this paper
• Optimal hardness results for maximizing agreements with monomials

  2006cited by this paper
• Hardness of Learning Halfspaces with Noise

  2006cited by this paper
• The Effectiveness of Lloyd-Type Methods for the k-Means Problem

  2006cited by this paper
• Agnostically learning halfspaces

  2005cited by this paper
• Learning Monotone Functions from Random Examples in Polynomial Time

  2005influential reference
• The Spectral Method for General Mixture Models

  2005cited by this paper
• Generative model-based document clustering: a comparative study

  2005cited by this paper
• Approximately dominating representatives

  2005cited by this paper
• On Spectral Learning of Mixtures of Distributions

  2005influential reference
• Bayesian hierarchical clustering

  2005cited by this paper
• Local Search Heuristics for k-Median and Facility Location Problems

  2004influential reference
• Toward efficient agnostic learning

  2004cited by this paper
• A simple linear time (1 + /spl epsiv/)-approximation algorithm for k-means clustering in any dimensions

  2004cited by this paper
• Combining Multiple Clustering Systems

  2004cited by this paper
• On coresets for k-means and k-median clustering

  2004cited by this paper
• Deterministic clustering with data nets

  2004cited by this paper
• Approximation schemes for clustering problems

  2003cited by this paper
• Learning DNF from random walks

  2003influential reference
• Approximate clustering via core-sets

  2002cited by this paper
• An Impossibility Theorem for Clustering

  2002cited by this paper
• A local search approximation algorithm for k-means clustering

  2002cited by this paper
• A new greedy approach for facility location problems

  2002cited by this paper
• Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning

  2002cited by this paper
• A Structured Family of Clustering and Tree Construction Methods

  2001cited by this paper
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

  2001cited by this paper
• Local search heuristic for k-median and facility location problems

  2001cited by this paper
• Learning mixtures of arbitrary gaussians

  2001cited by this paper
• Smooth Boosting and Learning with Malicious Noise

  2001cited by this paper
• Approximation algorithms for the Label-CoverMAX and Red-Blue Set Cover problems

  2000influential reference
• On the red-blue set cover problem

  2000cited by this paper
• Polynomial time approximation schemes for geometric k-clustering

  2000cited by this paper
• Noise-tolerant learning, the parity problem, and the statistical query model

  2000cited by this paper
• Learning mixtures of Gaussians

  1999cited by this paper
• A constant-factor approximation algorithm for the k-median problem (extended abstract)

  1999cited by this paper
• Statistical learning theory

  1998cited by this paper
• Greedy strikes back: improved facility location algorithms

  1998cited by this paper
• Approximation schemes for Euclidean k-medians and related problems

  1998influential reference
• Normalized cuts and image segmentation

  1997cited by this paper
• A decision-theoretic generalization of on-line learning and an application to boosting

  1997cited by this paper
• A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions

  1996influential reference
• Tracking the Best Disjunction

  1995influential reference
• Learning with unreliable boundary queries

  1995cited by this paper
• Cryptographic limitations on learning Boolean formulae and finite automata

  1994cited by this paper
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution

  1994cited by this paper
• Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract)

  1994influential reference
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis

  1994cited by this paper
• An Introduction to Computational Learning Theory

  1994cited by this paper
• Learning sparse multivariate polynomials over a field with queries and counterexamples

  1993cited by this paper
• An O(nlog log n) learning algorithm for DNF under the uniform distribution

  1992cited by this paper
• Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications

  1992influential reference
• Learning decision trees using the Fourier spectrum

  1991cited by this paper
• Redundant noisy attributes, attribute errors, and linear-threshold learning using winnow

  1991influential reference
• A Markovian extension of Valiant's learning model

  1990influential reference

• Differentially Private Algorithms for Clustering with Stability Assumptions

  2021cites this paper
• Private k-Means Clustering with Stability Assumptions

  2020influential citation
• Locally Private k-Means Clustering

  2019cites this paper