共查询到20条相似文献,搜索用时 31 毫秒
1.
We introduce an inductive definition for two classes of orders. By simple proofs, we show that one corresponds to the interval
orders class and that the other is exactly the semiorders class. 相似文献
2.
I Rabinovitch 《Journal of Combinatorial Theory, Series A》1978,25(1):50-61
The structure of semiorders and interval orders is investigated and various characterizations are given. These ideas are then applied to prove that the dimension of a semiorder is at most 3, to characterize semiorders of dimension 3 and height 2, and to prove Hiraguchi's Theorem. 相似文献
3.
This paper studies an extension of biorders that has a “frontier” between the relation and the absence of relation. This extension
is motivated by a conjoint measurement problem consisting in the additive representation of ordered coverings defined on product
sets of two components. We also investigate interval orders and semiorders with frontier. 相似文献
4.
The purpose of this paper is to study the properties of the linear orders and semiorders at minimum symmetric difference distance from a given interval order on a finite set. 相似文献
5.
Olivier Hudry 《Annals of Operations Research》2008,163(1):63-88
Given a collection Π of individual preferences defined on a same finite set of candidates, we consider the problem of aggregating
them into a collective preference minimizing the number of disagreements with respect to Π and verifying some structural properties.
We study the complexity of this problem when the individual preferences belong to any set containing linear orders and when
the collective preference must verify different properties, for instance transitivity. We show that the considered aggregation
problems are NP-hard for different types of collective preferences (including linear orders, acyclic relations, complete preorders,
interval orders, semiorders, quasi-orders or weak orders), if the number of individual preferences is sufficiently large. 相似文献
6.
George Steiner 《Journal of Graph Theory》1996,21(2):235-241
A digraph is an interval digraph if each vertex can be assigned a source interval and a sink interval on the real line such that there is an edge from u to v if and only if the source interval for u intersects the sink interval for v. A digraph is an indifference digraph or unit interval digraph if and only if such a representation can be constructed in which every source and sink interval has unit length. We present a new characterization and an efficient recognition algorithm for indifference digraphs and generalized semiorders. © 1996 John Wiley & Sons, Inc. 相似文献
7.
A poset P=(X,) is a split semiorder if a unit interval and a distinguished point in that interval can be assigned to each xX so that xy precisely when x's distinguished point precedes y's interval, and y's distinguished point follows x's interval. For each |X|10, we count the split semiorders and identify all posets that are minimal forbidden posets for split semiorders. 相似文献
8.
Alfio Giarlotta 《Order》2014,31(2):239-258
A NaP-preference (necessary and possible preference) on a set A is a pair \({\left(\succsim^{^{_N}}\!,\,\succsim^{^{_P}}\!\right)}\) of binary relations on A such that its necessary component \({\succsim^{^{_N}} \!\!}\) is a partial preorder, its possible component \({\succsim^{^{_P}} \!\!}\) is a completion of \({\succsim^{^{_N}} \!\!}\) , and the two components jointly satisfy natural forms of mixed completeness and mixed transitivity. We study additional mixed transitivity properties of a NaP-preference \({\left(\succsim^{^{_N}}\!,\,\succsim^{^{_P}}\!\right)}\) , which culminate in the full transitivity of its possible component \({\succsim^{^{_P}} \!\!}\) . Interval orders and semiorders are strictly related to these properties, since they are the possible components of suitably transitive NaP-preferences. Further, we introduce strong versions of interval orders and semiorders, which are characterized by enhanced forms of mixed transitivity, and use a geometric approach to compare them to other well known preference relations. 相似文献
9.
A poset P=(X,P) is a split semiorder when there exists a function I thatassigns to each x X a closed interval
of the real line R and a set
of real numbers, with
, suchthat x<y in P if and only if
and
in R. Every semiorder is a split semiorder, and thereare split semiorders which are not interval orders. It is well known thatthe dimension of a semiorder is at most 3. We prove that the dimension of asplit semiorder is at most 6. We note also that some split semiorders havesemiorder dimension at least 3, and that every split semiorder has intervaldimension at most 2. 相似文献
10.
The fractional weak discrepancywdF(P) of a poset P=(V,?) was introduced in Shuchat et al. (2007) [6] as the minimum nonnegative k for which there exists a function f:V→R satisfying (i) if a?b then f(a)+1≤f(b) and (ii) if a∥b then |f(a)−f(b)|≤k. In this paper we generalize results in Shuchat et al. (2006, 2009) [5] and [7] on the range of wdF for semiorders to the larger class of split semiorders. In particular, we prove that for such posets the range is the set of rationals that can be represented as r/s for which 0≤s−1≤r<2s. 相似文献
11.
The Gold Partition Conjecture 总被引:1,自引:1,他引:0
Marcin Peczarski 《Order》2006,23(1):89-95
We present the Gold Partition Conjecture which immediately implies the – Conjecture and tight upper bound for sorting. We prove the Gold Partition Conjecture for posets of width two, semiorders and posets containing at most elements. We prove that the fraction of partial orders on an -element set satisfying our conjecture converges to when approaches infinity. We discuss properties of a hypothetical counterexample. 相似文献
12.
In their paper “The Borda rule and Pareto stability: a comment” published in 1979 by Econometrica, Farkas and Nitzan revealed the “intimate relationship” between the Borda rule and the Pareto criterion. The idea was the following: in a profile of total orders, when there is a candidate who obviously wins under unanimous agreement of the voters, that candidate should be in the choice set. In a profile where there is no obvious winner, the candidates that are the closest to unanimity should be chosen. According to this principle, they defined a choice rule called “closeness to unanimity” and they showed that it is equivalent to the Borda rule. In our paper, we give an equivalent result for a ranking rule. Then we try to obtain similar results when aggregating profiles of tournaments, weak orders, semiorders, fuzzy relations, … and we show that the definition of an obvious winner is no more obvious. 相似文献
13.
The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h
L
(x)–h
L
(y)|≤k, where h
L
(x) is the height of x in L. Tanenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the
problem of characterizing the posets of linear discrepancy 2. We show that this problem is equivalent to finding the posets
with linear discrepancy equal to 3 having the property that the deletion of any point results in a reduction in the linear
discrepancy. Howard determined that there are infinitely many such posets of width 2. We complete the forbidden subposet characterization
of posets with linear discrepancy equal to 2 by finding the minimal posets of width 3 with linear discrepancy equal to 3.
We do so by showing that, with a small number of exceptions, they can all be derived from the list for width 2 by the removal
of specific comparisons.
The first and second authors were supported during this research by National Science Foundation VIGRE grant DMS-0135290. 相似文献
14.
The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h
L
(x) − h
L
(y)| ≤ k, where h
L
(x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed
the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point
reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width
2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique
linear extension that witnesses linear discrepancy 2.
The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290. 相似文献
15.
Peter C. Fishburn 《Order》1999,16(4):335-396
Let M
n
(k) denote the family of posets on n points with k ordered pairs that maximize the number of linear extensions among all such posets. Fishburn and Trotter [2] prove that every poset in M
n
(k) is a semiorder and identifies all semiorders in M
n
(k) for k n. The present paper specifies M
n
(k) for all k 2 n – 3. 相似文献
16.
In this paper we describe the range of values that can be taken by the fractional weak discrepancy of a poset and characterize semiorders in terms of these values. In [6], we defined the fractional weak discrepancy
of a poset to be the minimum nonnegative for which there exists a function satisfying (1) if then and (2) if then . This notion builds on previous work on weak discrepancy in [3, 7, 8]. We prove here that the range of values of the function is the set of rational numbers that are either at least one or equal to for some nonnegative integer . Moreover, is a semiorder if and only if , and the range taken over all semiorders is the set of such fractions .The third author's work was supported in part by a Wellesley College Brachman Hoffman Fellowship. 相似文献
17.
Christopher W. Doble Jean-Paul Doignon Jean-Claude Falmagne Peter C. Fishburn 《Order》2001,18(4):295-311
One of the standard axioms for semiorders states that no three-point chain is incomparable to a fourth point. We refer to asymmetric relations satisfying this axiom as almost connected orders or ac-orders. It turns out that any relation lying between two weak orders, one of which covers the other for inclusion, is an ac-order (albeit of a special kind). Every ac-order is bracketed in a natural way by two weak orders, one the maximum in the set of weak orders included in the ac-order, and the other minimal, but not necessarily the minimum, in the set of weak orders that include the ac-order. The family of ac-orders on a finite set with at least five elements is not well graded (in the sense of Doignon and Falmagne, 1997). However, such a family is both upgradable and downgradable, as every nonempty ac-order contains a pair whose deletion defines an ac-order on the same set, and for every ac-order which is not a chain, there is a pair whose addition gives an ac-order. 相似文献
18.
Let P define a partial order on a set X of cardinalityn. A linear extensionL ofP is a linear order withP G L, and
is the set of all linear extensions ofP.
denotes that subset of
withxLy forx, y X. A linear extension majority (LEM) relationM onX is defined byxMy if
. Similarly,M is defined byxMy if
. An LEM cycle exists if there arex, y, z X withxMyMzMx, and an LEM quasi-cycle exists ifxMyMzMx and the equality part of the definition ofM holds for exactly one pair in the triple. The study shows that no semiorders have LEM cycles or LEM quasi-cycles, and that every interval order has a maximal element under theM relation. LEM cycles and LEM quasi-cycles are also considered for partial orders with specific structures. Simulation is used to determine the relative likelihood with which LEM cycles and LEM quasi-cycles are observed when connected partial orders are generated at random by a specific procedure.Dr. Gehrlein's research was supported through a fellowship from the Center for Advanced Study of the University of Delaware. 相似文献
19.
The fractional weak discrepancywdF(P) of a poset P=(V,?) was introduced in [A. Shuchat, R. Shull, A. Trenk, The fractional weak discrepancy of a partially ordered set, Discrete Applied Mathematics 155 (2007) 2227-2235] as the minimum nonnegative k for which there exists a function satisfying (i) if a?b then f(a)+1≤f(b) and (ii) if a∥b then |f(a)−f(b)|≤k. In this paper we generalize results in [A. Shuchat, R. Shull, A. Trenk, Range of the fractional weak discrepancy function, ORDER 23 (2006) 51-63; A. Shuchat, R. Shull, A. Trenk, Fractional weak discrepancy of posets and certain forbidden configurations, in: S.J. Brams, W.V. Gehrlein, F.S. Roberts (Eds.), The Mathematics of Preference, Choice, and Order: Essays in Honor of Peter C. Fishburn, Springer, New York, 2009, pp. 291-302] on the range of the wdF function for semiorders (interval orders with no induced ) to interval orders with no , where n≥3. In particular, we prove that the range for such posets P is the set of rationals that can be written as r/s, where 0≤s−1≤r<(n−2)s. If wdF(P)=r/s and P has an optimal forcing cycle C with and , then r≤(n−2)(s−1). Moreover when s≥2, for each r satisfying s−1≤r≤(n−2)(s−1) there is an interval order having such an optimal forcing cycle and containing no. 相似文献
20.
Ronald R. Yager 《Fuzzy Optimization and Decision Making》2017,16(1):1-21
We describe the Dempster–Shafer belief structure and provide some of its basic properties. We introduce the plausibility and belief measures associated with a belief structure. We note that these are not the only measures that can be associated with a belief structure. We describe a general approach for generating a class of measures that can be associated with a belief structure using a monotonic function on the unit interval, called a weight generating function. We study a number of these functions and the measures that result. We show how to use weight-generating functions to obtain dual measures from a belief structure. We show the role of belief structures in representing imprecise probability distributions. We describe the use of dual measures, other then plausibility and belief, to provide alternative bounding intervals for the imprecise probabilities associated with a belief structure. We investigate the problem of decision making under belief structure type uncertain. We discuss two approaches to this decision problem. One of which is based on an expected value of the OWA aggregation of the payoffs associated with the focal elements. The second approach is based on using the Choquet integral of a measure generated from the belief structure. We show the equivalence of these approaches. 相似文献