Ranking with Partitioning

• URL: http://arxiv.org/abs/2605.02874v1
• Date: Mon, 04 May 2026 17:47:07 GMT
• Title: Ranking with Partitioning
• Abstract summary: We treat the position of a special subset of items in an ordinal ranking through a collection of optimization problems.<n>The objective for these problems is to either maximize or minimize the absolute or relative rank of the special subset.<n>We classify the computational complexity of all four problems, mostly finding worst-case hardness, then find exact and approximate solutions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• COMPACT: Spectral Adjustment Scores from a Complete and Irreducible Causal Criterion [1.8275108630751837]
  Propensity scores can simplify adjustment by reducing high-dimensional covariates to a scalar with binary treatment.<n>Under faithfulness, we identify the largest set of unconditional and conditional dependence relations whose truth is invariant to whether treatment causes the outcome, leaving treatment-effect estimation to the downstream analysis.<n>We show that sufficiently informative proxies can recover this span without direct observation of the adjustment variables, characterize the resulting estimation and causal errors, and establish validity for the complete procedure.
  arXiv  Detail & Related papers  (2026-08-10T23:22:20Z)
• Ranking-and-Selection with Multiple Correct Answers and Non-Answerable Estimates [3.184862162193667]
  We study fixed-precision ranking-and-selection in structured settings where the answer may be non-unique.<n>This phenomenon arises naturally in problems such as multi-fidelity ranking-and-selection and identifying a Condorcet winner from pairwise comparisons.<n>We propose a unified framework based on answer-wise acceptance sets, restricted generalized likelihood ratio stopping, and an answer-pitfall decomposition that yields a max-max-min characteristic value.
  arXiv  Detail & Related papers  (2026-06-20T05:29:31Z)
• Deconfounding Scores and Representation Learning for Causal Effect Estimation with Weak Overlap [75.41420283374737]
  Overlap is a key condition for causal treatment effect estimation.<n>We propose a class of feature representations called deconfounding scores.<n>We show that prognostic scores are overlap-optimal within this class.
  arXiv  Detail & Related papers  (2026-04-01T12:19:42Z)
• Score-based Greedy Search for Structure Identification of Partially Observed Linear Causal Models [34.09555821357439]
  We propose the first score-based greedy search method for the identification of structure involving latent variables with identifiability guarantees.<n>We then design Latent variable Greedy Equivalence Search (LGES), a greedy search algorithm for this class of model with well-defined operators.
  arXiv  Detail & Related papers  (2025-10-05T21:50:17Z)
• A consensus set for the aggregation of partial rankings: the case of the Optimal Set of Bucket Orders Problem [46.752018687842344]
  In rank aggregation problems (RAP), the solution is usually a consensus ranking that generalizes a set of input orderings.<n>We propose to provide, as the solution to an RAP, a set of rankings to better explain the preferences expressed in the input orderings.
  arXiv  Detail & Related papers  (2025-02-19T14:32:16Z)
• Partial Optimality in Cubic Correlation Clustering [6.372499127940625]
  Certifying optimality is NP-hard and practically hampered already by the complexity of the problem statement. Here, we focus on establishing partial optimality conditions for the special case of complete graphs and cubic objective functions. In addition, we define and implement algorithms for testing these conditions and examine their effect numerically, on two datasets.
  arXiv  Detail & Related papers  (2023-02-09T15:25:52Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Deconfounding Scores: Feature Representations for Causal Effect Estimation with Weak Overlap [140.98628848491146]
  We introduce deconfounding scores, which induce better overlap without biasing the target of estimation. We show that deconfounding scores satisfy a zero-covariance condition that is identifiable in observed data. In particular, we show that this technique could be an attractive alternative to standard regularizations.
  arXiv  Detail & Related papers  (2021-04-12T18:50:11Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  We study oracle complexity of gradient based methods for approximation problems. We focus on instance-dependent complexity instead of worst case complexity. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation.
  arXiv  Detail & Related papers  (2020-06-08T09:25:47Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)
• SetRank: A Setwise Bayesian Approach for Collaborative Ranking from Implicit Feedback [50.13745601531148]
  We propose a novel setwise Bayesian approach for collaborative ranking, namely SetRank, to accommodate the characteristics of implicit feedback in recommender system. Specifically, SetRank aims at maximizing the posterior probability of novel setwise preference comparisons. We also present the theoretical analysis of SetRank to show that the bound of excess risk can be proportional to $sqrtM/N$.
  arXiv  Detail & Related papers  (2020-02-23T06:40:48Z)

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.