Sorting noisy data with partial information

DOI10.1145/2422436.2422492MaRDI QIDQ2986898zbMATH OpenOpenAlexFDO

Authors Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Publication date 16 May 2017

Published in Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2422436.2422492

zbMATH Keywords

approximation algorithmaverage-case analysisminimum feedback arc setsemi-random model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Noisy sorting without resampling
• Approximation algorithms for semi-random partitioning problems
• Aggregating inconsistent information: ranking and clustering
• Feedback arc set problem in bipartite tournaments
• Feedback Arc Set Problem in Bipartite Tournaments

Cites work

• A model of interactive teaching
• A theory of goal-oriented communication
• A theory of the learnable
• Algorithmic Learning Theory
• Derandomizing polynomial identity tests means proving circuit lower bounds
• scientific article; zbMATH DE number 3154781 (Why is no real title available?)
• scientific article; zbMATH DE number 67625 (Why is no real title available?)
• scientific article; zbMATH DE number 67631 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Learning from different teachers
• Measuring teachability using variants of the teaching dimension
• Models of cooperative teaching and learning
• Occam's razor
• On specifying Boolean functions by labelled examples
• On the complexity of teaching
• On the limits of efficient teachability
• On the power of inductive inference from good examples
• Pseudorandom generators for space-bounded computation
• Recent Developments in Algorithmic Teaching
• Teachability in computational learning
• Teaching a smarter learner.
• Teaching Randomized Learners

Cited in

(9)

• Approximate minimum selection with unreliable comparisons
• A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis
• Approximation algorithm for min-max correlation clustering problem with outliers
• Approximation algorithms for the lower bounded correlation clustering problem
• Sorting from Noisier Samples
• Optimally sorting evolving data
• Partitioning well-clustered graphs: spectral clustering works!
• scientific article; zbMATH DE number 7650100 (Why is no real title available?)
• Approximate selection with unreliable comparisons in sublinear time

This page was built for publication: Sorting noisy data with partial information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986898)