Exploring the median of permutations problem

DOI10.1016/J.JDA.2018.11.007MaRDI QIDQ1711664zbMATH OpenOpenAlexFDO

Authors Robin Milosz, Sylvie Hamel

Publication date 18 January 2019

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2018.11.007

zbMATH Keywords

simulated annealinginteger linear programmingbranch-and-boundspace reductionKendall-\(\tau\) distancemedian of permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Medians of an odd number of permutations
• Medians of Permutations: Building Constraints
• Median of 3 permutations, 3-cycles and 3-hitting set problem
• Space reduction constraints for the median of permutations problem
• scientific article; zbMATH DE number 1045817
• scientific article; zbMATH DE number 26585
• A solution to one of Knuth's permutation problems
• The matroid median problem

Cites work

• scientific article; zbMATH DE number 5485441 (Why is no real title available?)
• scientific article; zbMATH DE number 4076317 (Why is no real title available?)
• scientific article; zbMATH DE number 3047450 (Why is no real title available?)
• A NEW MEASURE OF RANK CORRELATION
• A new rank correlation coefficient with application to the consensus ranking problem
• Aggregating inconsistent information: ranking and clustering
• Average parameterization and partial kernelization for computing medians
• Deterministic pivoting algorithms for constrained ranking and clustering problems
• Efficient algorithms using subiterative convergence for Kemeny ranking problem
• Equation of state calculations by fast computing machines
• Experiments with Kemeny ranking: What works when?
• Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament
• Graph Drawing
• Heuristic, branch-and-bound solver and improved space reduction for the median of permutations problem
• Medians of Permutations: Building Constraints
• Medians of an odd number of permutations
• NON-NULL RANKING MODELS. I
• Optimization by simulated annealing
• Parameterized enumeration of (locally-) optimal aggregations
• Rank aggregation: together we're strong
• Reducibility among combinatorial problems
• \(k\)-majority digraphs and the hardness of voting with a constant number of voters

Cited in

(10)

• Space reduction constraints for the median of permutations problem
• Automedian sets of permutations: direct sum and shuffle
• Medians of Permutations: Building Constraints
• Medians of an odd number of permutations
• A New Binary Programming Formulation and Social Choice Property for Kemeny Rank Aggregation
• Heuristic, branch-and-bound solver and improved space reduction for the median of permutations problem
• Average parameterization and partial kernelization for computing medians
• Approximate Condorcet partitioning: solving large-scale rank aggregation problems
• Median of 3 permutations, 3-cycles and 3-hitting set problem
• Average parameterization and partial kernelization for computing medians

Describes a project that uses

Uses Software

• PrefLib
• CPLEX

This page was built for publication: Exploring the median of permutations problem

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