Diversity in Kemeny Rank Aggregation: A Parameterized Approach
- URL: http://arxiv.org/abs/2105.09413v1
- Date: Wed, 19 May 2021 21:50:03 GMT
- Title: Diversity in Kemeny Rank Aggregation: A Parameterized Approach
- Authors: Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de
Oliveira Oliveira, Petra Wolf
- Abstract summary: A recent trend in artificial intelligence, called solution diversity, has focused on the development of notions of optimality.
In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation.
Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered.
- Score: 3.6603644500568806
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In its most traditional setting, the main concern of optimization theory is
the search for optimal solutions for instances of a given computational
problem. A recent trend of research in artificial intelligence, called solution
diversity, has focused on the development of notions of optimality that may be
more appropriate in settings where subjectivity is essential. The idea is that
instead of aiming at the development of algorithms that output a single optimal
solution, the goal is to investigate algorithms that output a small set of
sufficiently good solutions that are sufficiently diverse from one another. In
this way, the user has the opportunity to choose the solution that is most
appropriate to the context at hand. It also displays the richness of the
solution space.
When combined with techniques from parameterized complexity theory, the
paradigm of diversity of solutions offers a powerful algorithmic framework to
address problems of practical relevance. In this work, we investigate the
impact of this combination in the field of Kemeny Rank Aggregation, a
well-studied class of problems lying in the intersection of order theory and
social choice theory and also in the field of order theory itself. In
particular, we show that the Kemeny Rank Aggregation problem is fixed-parameter
tractable with respect to natural parameters providing natural formalizations
of the notions of diversity and of the notion of a sufficiently good solution.
Our main results work both when considering the traditional setting of
aggregation over linearly ordered votes, and in the more general setting where
votes are partially ordered.
Related papers
- Learning Joint Models of Prediction and Optimization [56.04498536842065]
Predict-Then-Then framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving.
This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by joint predictive models.
arXiv Detail & Related papers (2024-09-07T19:52:14Z) - Illuminating the Diversity-Fitness Trade-Off in Black-Box Optimization [9.838618121102053]
In real-world applications, users often favor structurally diverse design choices over one high-quality solution.
This paper presents a fresh perspective on this challenge by considering the problem of identifying a fixed number of solutions with a pairwise distance above a specified threshold.
arXiv Detail & Related papers (2024-08-29T09:55:55Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods.
Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem.
As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
arXiv Detail & Related papers (2023-10-08T23:39:38Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks.
One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver.
This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
arXiv Detail & Related papers (2023-01-28T01:50:42Z) - A machine learning framework for neighbor generation in metaheuristic
search [4.521119623956821]
We propose a general machine learning framework for neighbor generation in metaheuristic search.
We validate our methodology on two metaheuristic applications.
arXiv Detail & Related papers (2022-12-22T01:58:04Z) - Computing High-Quality Solutions for the Patient Admission Scheduling
Problem using Evolutionary Diversity Optimisation [10.609857097723266]
We adapt the evolutionary diversity optimisation for a real-world problem, namely patient admission scheduling.
We introduce an evolutionary algorithm to achieve structural diversity in a set of solutions subjected to the quality of each solution.
arXiv Detail & Related papers (2022-07-28T14:26:45Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
We present an end-to-end method to learn the proximal operator across non-family problems.
We show that for weakly-ized objectives and under mild conditions, the method converges globally.
arXiv Detail & Related papers (2022-01-28T05:53:28Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA)
We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$.
When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
arXiv Detail & Related papers (2021-10-18T14:00:22Z) - Preference learning along multiple criteria: A game-theoretic
perspective [97.94912276610002]
We generalize the notion of a von Neumann winner to the multi-criteria setting by taking inspiration from Blackwell's approachability.
Our framework allows for non-linear aggregation of preferences across criteria, and generalizes the linearization-based approach from multi-objective optimization.
We show that the Blackwell winner of a multi-criteria problem instance can be computed as the solution to a convex optimization problem.
arXiv Detail & Related papers (2021-05-05T03:23:11Z) - PAMELI: A Meta-Algorithm for Computationally Expensive Multi-Objective
Optimization Problems [0.0]
The proposed algorithm is based on solving a set of surrogate problems defined by models of the real one.
Our algorithm also performs a meta-search for optimal surrogate models and navigation strategies for the optimization landscape.
arXiv Detail & Related papers (2021-03-19T11:18:03Z) - Optimistic variants of single-objective bilevel optimization for
evolutionary algorithms [6.788217433800101]
A partial partial evolutionary approach has been proposed to solve the benchmark problems and have outstanding results.
A new variant has also been proposed to the commonly used convergence approaches, i.e. optimistic and pessimistic.
The experimental results demonstrate the algorithm converges differently to optimum solutions with the optimistic variants.
arXiv Detail & Related papers (2020-08-22T23:12:07Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.