The Computational Complexity of Densest Region Detection

We investigate the computational complexity of the task of detecting dense regions of an unknown distribution from unlabeled samples of this distribution. We introduce a formal learning model for this task that uses a hypothesis class as it “anti-overfitting” mechanism. The learning task in our model can be reduced to a combinatorial optimization problem. We can show that for some constants, depending on the hypothesis class, these problems are NP-hard to approximate to within these constant factors. We go on and introduce a new criterion for the success of approximate optimization geometric problems. The new criterion requires that the algorithm competes with hypotheses only on the points that are separated by some margin ? from their boundaries. Quite surprisingly, we discover that for each of the two hypothesis classes that we investigate, there is a “critical value” of the margin parameter ?. For any value below the critical value the problems are NP-hard to approximate, while, once this value is exceeded, the problems become poly-time solvable.

• Publication year

  2000

• Venue

  Journal of computer and system sciences (Print)

• Publication date

  2000-06-28

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1006/jcss.2001.1797
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• About the authors

  2004cited by this paper
• Some optimal inapproximability results

  2001cited by this paper
• On the difficulty of approximately maximizing agreements

  2000cited by this paper
• Eecient Learning of Linear Perceptrons

  2000influential reference
• On the Di cultyof Approximately Maximizing Agreements

  2000influential reference
• Efficient Learning of Linear Perceptrons

  2000influential reference
• Neural Network Learning: Theoretical Foundations

  1999influential reference
• Parameterized Complexity

  1998cited by this paper
• Learning Distributions by Their Density Levels: A Paradigm for Learning without a Teacher

  1997cited by this paper
• Some optimal inapproximability results

  1997cited by this paper
• Learning distributions by their density-levels - a paradigm for learning without a teacher

  1995cited by this paper
• On the complexity of polyhedral separability

  1988cited by this paper
• Universal Donsker Classes and Metric Entropy

  1987cited by this paper
• On a characterization of operators from lq into a Banach space of type p with some applications to eigenvalue problems

  1982cited by this paper
• Remarques sur un résultat non publié de B. Maurey

  1981cited by this paper
• The Densest Hemisphere Problem

  1978cited by this paper
• Pattern classification and scene analysis

  1974cited by this paper

• Differentially Private Clustering: Tight Approximation Ratios

  2020influential citation
• Maximizing Welfare with Incentive-Aware Evaluation Mechanisms

  2020cites this paper
• A Geometric Model of Opinion Polarization

  2019cites this paper
• Learning to Learn for Small Sample Visual Recognition

  2018cites this paper
• Robust Fitting in Computer Vision: Easy or Hard?

  2018cites this paper
• Guest Editorial: Best of CVPR 2015

  2017cites this paper
• The Maximum Consensus Problem: Recent Algorithmic Advances

  2017cites this paper
• Low-Rank Doubly Stochastic Matrix Decomposition for Cluster Analysis

  2016cites this paper
• Efficient Globally Optimal Consensus Maximisation with Tree Search

  2015cites this paper
• Data quality evaluation and improvement for prognostic modeling using visual assessment based data partitioning method

  2013cites this paper
• A spatial and temporal analysis for long term renewal of water pipes

  2012cites this paper
• A practical decision scheme for the prioritization of water pipe replacement

  2012cites this paper
• Data Quality Assessment Methodology for Improved Prognostics Modeling

  2012cites this paper
• Urban waters : Resource or Risk ?

  2012cites this paper
• Clusterability: A Theoretical Study

  2009cites this paper
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm

  2008cites this paper
• Which Data Sets are ‘Clusterable’? – A Theoretical Study of Clusterability

  2008cites this paper
• Learning Low Density Separators

  2008cites this paper
• A Theoretical Study of Clusterability and Clustering Quality

  2007cites this paper
• Alternative Measures of Computational Complexity with Applications to Agnostic Learning

  2006cites this paper
• On Agnostic Learning with {0, *, 1}-Valued and Real-Valued Hypotheses

  2001cites this paper
• Efficient Learning of Linear Perceptrons

  2000influential citation
• Eecient Learning of Linear Perceptrons

  2000cites this paper
• On the difficulty of approximately maximizing agreements

  2000influential citation