Ranking with Partitioning
2026-05-04 • Data Structures and Algorithms
Data Structures and AlgorithmsComputers and Society
AI summaryⓘ
The authors study how the position of a special group of items changes when these items can be grouped based on their similarities in a ranking list. They look at problems where the goal is to either raise or lower the group's rank, measuring how stable or sensitive this rank is under certain rules. They find that these problems are mostly very hard to solve in general but provide exact or approximate solutions for simpler, real-world-inspired cases. One example they use is analyzing sources of greenhouse gas emissions to understand how robust their ranking is.
undirected graphordinal rankingcombinatorial optimizationcomputational complexityapproximation algorithmsadditive measurerobustnesssimilarity graphrank maximizationgreenhouse gas emissions
Authors
Samuel Boardman
Abstract
Given an undirected graph representing similarities between a set of items and an additive measure evaluating the items, we treat the position of a special subset of items in an ordinal ranking through a collection of combinatorial optimization problems in which items may be combined if they are similar. The objective for these problems is to either maximize or minimize the absolute or relative rank of the special subset, with a meta-goal of assessing the robustness of the rank, even in the presence of a well-defined criterion. We classify the computational complexity of all four problems, mostly finding worst-case hardness, then find exact and approximate solutions to special cases and variants of the problems. These structured cases are inspired by several real-world examples and may be used to assess commonly cited facts across disparate domains, as we demonstrate for sources of greenhouse gas emissions that contribute to climate change.