The complexity of computing medians of relations.

MaRDI QIDQ2766482zbMATH OpenFDO

Authors Yoshiko Wakabayashi

Publication date 28 January 2002

Published in Resenhas do Instituto do Matemática e Estatística da Universidade de São Paulo (Search for Journal in Brave)

Mathematics Subject Classification ID

Social choice (91B14) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the computation of median linear orders, of median complete preorders and of median weak orders
• Complexity results for extensions of median orders to different types of remoteness
• scientific article; zbMATH DE number 3980481
• NP-hardness results for the aggregation of linear orders into median orders
• NP-hardness of the computation of a median equivalence relation in classification (Régnier's problem)

Cited in

(20)

• A note on clustering aggregation for binary clusterings
• A randomized PTAS for the minimum consensus clustering with a fixed number of clusters
• Voting procedures, complexity of
• On the approximation of correlation clustering and consensus clustering
• NP-hardness results for the aggregation of linear orders into median orders
• NP-hardness of the computation of a median equivalence relation in classification (Régnier's problem)
• scientific article; zbMATH DE number 3980481 (Why is no real title available?)
• On the computation of median linear orders, of median complete preorders and of median weak orders
• Application of the ``descent with mutations metaheuristic to a clique partitioning problem
• On the parameterized complexity of consensus clustering
• An updated survey on the linear ordering problem for weighted or unweighted tournaments
• Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem
• Average parameterization and partial kernelization for computing medians
• A survey on the linear ordering problem for weighted or unweighted tournaments
• Complexity results for extensions of median orders to different types of remoteness
• Core potentials: the consensus segmentation conjecture
• Aggregation of partial rankings, \(p\)-ratings and top-\(m\) lists
• Binary relations: Finite characterizations and computational complexity
• Ranking data with ordinal labels: optimality and pairwise aggregation
• Noising methods for a clique partitioning problem

Describes a project that uses

Uses Software

• LOLIB

This page was built for publication: The complexity of computing medians of relations.

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