Complexity results for extensions of median orders to different types of remoteness

Olivier Hudry ()

Annals of Operations Research, 2015, vol. 225, issue 1, 123 pages

Abstract: Given a finite set X and a collection Π=(R 1 ,R 2 ,…,R v ) of v binary relations defined on X and given a remoteness ρ, a relation R is said to be a central relation of Π with respect to ρ if it minimizes the remoteness ρ(Π,R) from Π. The remoteness ρ is based on the symmetric difference distance δ(R i ,R) between R and the binary relations R i of Π (1≤i≤v), which measures the number of disagreements between R i and R. Usually, the considered remoteness between Π and a relation R is the remoteness ρ 1 (Π,R) given by the sum of the distances δ(R i ,R) over i, and thus measures the total number of disagreements between Π and R or, divided by v, provides the (arithmetical) mean number of disagreements between Π and R. The computation of a central relation with respect to ρ 1 is often an NP-hard problem when the central relation is required to fulfill structural properties like transitivity. In this paper, we investigate other types of remoteness ρ, for instance the sum of the pth power of the δ(R i ,R)’s for any integer p, the maximum of the δ(R i ,R)’s, the minimum of the δ(R i ,R)’s, and different kinds of means of the δ(R i ,R)’s, or their weighted versions. We show that for many definitions of the remoteness, including the previous ones, the computation of a central relation with respect to ρ remains an NP-hard problem, even when the number v of relations is given, for any value of v greater than or equal to 1. Copyright Springer Science+Business Media New York 2015

Keywords: Complexity; NP-completeness; Aggregation of preferences; Remoteness; Symmetric difference distance; Median relation; Median order; Binary relations; Complete preorder; Weak order; Linear order; Tournament; Slater’s problem; Kemeny’s problem (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-013-1342-3 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:225:y:2015:i:1:p:111-123:10.1007/s10479-013-1342-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-013-1342-3

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().