Approximations of arbitrary relations by partial orders. (English) Zbl 1448.68418
Summary: The problem of optimal quantitative approximation of an arbitrary binary relation by a partial order is discussed and some solutions are provided. It is shown that even for a very simple quantitative measure the problem is NP-hard. Some quantitative metrics are also applied for known property-driven approximations by partial orders. Some relationship to Rough Sets is discussed.
MSC:
| 68T37 | Reasoning under uncertainty in the context of artificial intelligence |
| 03E20 | Other classical set theory (including functions, relations, and set algebra) |
| 03E72 | Theory of fuzzy sets, etc. |
| 06A07 | Combinatorics of partially ordered sets |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Software:
Stony BrookReferences:
| [1] | Bogobowicz, A. D.; Janicki, R., On approximation of relations by generalized closures and generalized kernels, (Lecture Notes in Artificial Intelligence, vol. 9920, (2016), Springer), 120-130 · Zbl 1398.68528 |
| [2] | Chen, J.; Liu, Y.; Lu, S.; O’sullivan, B.; Razgon, I., A fixed parameter algorithm for the directed feedback vertex set problem, J. ACM, 55, 5, 1-19, (2008) · Zbl 1325.68104 |
| [3] | Cormen, T. H.; Leiserson, C. E.; Rivest, D. L.; Stein, C., Introduction to algorithms, (2001), MIT Press · Zbl 1047.68161 |
| [4] | Deza, M. M.; Deza, E., Encyclopedia of distances, (2012), Springer Berlin |
| [5] | (Diekert, V.; Rozenberg, G., The Book of Traces, (1995), World Scientific Singapore) |
| [6] | Eades, P.; Lin, X.; Smyth, W. F., A fast and effective heuristic for the feedback arc set problem, Inf. Process. Lett., 47, 319-323, (1993) · Zbl 0787.68078 |
| [7] | Fishburn, P. C., Interval orders and interval graphs, (1985), J. Wiley New York · Zbl 0568.05047 |
| [8] | French, S., Decision theory, (1986), Ellis Horwood New York |
| [9] | Hassin, R.; Rubinstein, S., Approximations for the maximum acyclic subgraph problem, Inf. Process. Lett., 51, 3, 133-140, (1994) · Zbl 0942.68644 |
| [10] | Jaccard, P., Étude comparative de la distribution florale dans une portion des alpes et des jura, Bull. Soc. Vaud. Sci. Nat., 37, 547-549, (1901) |
| [11] | Janicki, R., Pairwise comparisons based non-numerical ranking, Fundam. Inform., 94, 2, 197-217, (2009) · Zbl 1192.68671 |
| [12] | Janicki, R., Approximations of arbitrary binary relations by partial orders. classical and rough set models, (Transactions on Rough Sets 13, (2011)), 17-38 · Zbl 1316.03026 |
| [13] | Janicki, R., Property-driven rough sets approximations of relations, (Skowron, A.; Suraj, Z., Rough Sets and Intelligent Systems - Professor Zdzisław Pawlak in Memoriam, Intelligent Systems Reference Library, vol. 42, (2013), Springer), 333-357 · Zbl 1308.68115 |
| [14] | Janicki, R., On optimal approximations of arbitrary relations by partial orders, (Lecture Notes in Artificial Intelligence, vol. 9920, (2016), Springer), 107-119 · Zbl 1398.68540 |
| [15] | Janicki, R.; Koczkodaj, W. W., Weak order approach to group ranking, Comput. Math. Appl., 32, 2, 51-59, (1996) · Zbl 0862.90011 |
| [16] | Janicki, R.; Lenarčič, A., Optimal approximations with rough sets and similarities in measure spaces, Int. J. Approx. Reason., 71, 1-14, (2016) · Zbl 1352.68245 |
| [17] | Janicki, R.; Zhai, Y., On a pairwise comparison based consistent non-numerical ranking, Log. J. IGPL, 20, 4, 667-676, (2012) · Zbl 1264.91055 |
| [18] | Karp, M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations, (1972), Plenum New York), 85-103 · Zbl 1467.68065 |
| [19] | Kemeny, J. G., Mathematics without numbers, Daedalus, 88, 571-591, (1959) |
| [20] | Kleijn, J.; Koutny, M., Formal languages and concurrent behaviour, Stud. Comput. Intell., 113, 125-182, (2008) · Zbl 1155.68043 |
| [21] | Kuratowski, K.; Mostowski, A., Set theory, (1976), North Holland · Zbl 0337.02034 |
| [22] | Marczewski, E.; Steinhaus, H., On a certain distance of sets and corresponding distance of functions, Colloq. Math., 4, 319-327, (1958) · Zbl 0089.03502 |
| [23] | Pawlak, Z., Rough sets, (1991), Kluwer Dordrecht · Zbl 0604.90084 |
| [24] | Rosen, K. H., Discrete mathematics and its applications, (1999), McGraw-Hill New York |
| [25] | Schröder, E., Algebra der logik, (1895), Teuber Leipzig · JFM 26.0074.01 |
| [26] | Skiena, S., The algorithm design manual, (2010), Springer · Zbl 1149.68081 |
| [27] | Skowron, A.; Stepaniuk, J., Tolerance approximation spaces, Fundam. Inform., 27, 245-253, (1996) · Zbl 0868.68103 |
| [28] | Tversky, A., Features of similarity, Psychol. Rev., 84, 4, 327-352, (1977) |
| [29] | Yao, Y. Y., Two views of the theory of rough sets in finite universes, Int. J. Approx. Reason., 15, 291-317, (1996) · Zbl 0935.03063 |
| [30] | Yao, Y. Y.; Wang, T., On rough relations: an alternative formulations, (Lecture Notes in Artificial Intelligence, vol. 1711, (1999), Springer), 82-91 · Zbl 0951.03046 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
