Interval Obligation Rules and Related Results

Osman Palancı; Sırma Zeynep Alparslan Gök; Gerhald Wilhelm Weber

Authors

Osman Palancı Suleyman Demirel University
Sırma Zeynep Alparslan Gök Suleyman Demirel University
Gerhald Wilhelm Weber Middle East Technical University

Abstract

In this study, we extend the well-known obligation rules by using interval calculus. We introduce interval obligation rules for minimum interval cost spanning tree (micst) situations. It turns out that the interval obligation rule and the interval Bird rule are equal under suitable conditions. Further, we show that such rules are interval cost monotonic and induce population monotonic interval allocation schemes (pmias). Some examples of pmias and interval obligation rules for micst situations are also given.

Keywords:

Graphs and networks, minimum cost spanning tree situations, interval data, obligation rules, population monotonic allocation scheme

Downloads

Download data is not yet available.

References

Alparslan Gök, S. Z. (2009). Cooperative interval games, PhD Dissertation Thesis, Institute of Applied Mathematics, Middle East Technical University.

Alparslan Gök, S. Z. (2010). Cooperative Interval Games: Theory and Applications, LAPLambert Academic Publishing house, Germany, (PROJECT-ID:5124, ISBN–NR: 978–3–8383–3430–1).

Alparslan Gök, S. Z., Branzei, R., Tijs, S. (2009a). Convex Interval Games. Journal of Applied Mathematics and Decision Sciences, Vol. 2009, Article ID 342089, 14 pages.

Alparslan Gök, S. Z., Branzei, R., Tijs, S. (2011). Big Boss Interval Games. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems (IJUFKS), 19(1), 135–149

Alparslan Gök, S. Z., Miquel, S., Tijs, S. (2009b). Cooperation under interval uncertainty. Mathematical Methods of Operations Research, 69(1), 99–109.

Alparslan Gök, S. Z., Palancı , O., Olgun M. O. (2014). Cooperative interval games: mountain situations with interval data. Journal of Computational and Applied Mathematics, 259(2014), 622–632.

Barzily, Z., Volkovich, Z., Aktake-Öztürk, B., Weber, G.-W. (2009). On a Minimal Spanning Tree Approach in the Cluster Validation Problem. INFORMATICA, 20(2), 187–202.

Bird, C. G. (1976). On cost allocation for a spanning tree: a game theoretic approach. Networks, 6, 335–350.

Borůvka, O. (1926). Contribution to the solution of a problem of economical construction of electrical networks. Elektronickı Obzor, 15, 153–154.

Claus, A., Kleitman, D. J. (1973). Cost allocation for a spanning tree. Networks, 3, 289–304.

Diestel, R., (2000). Graph Theory. Springer-Verlag.

Dijkstra, E. W. (1959). A note on two problems in connection with graphs. Numerische Mathematik, 1, 269–271.

Graham, R. L., Hell, P. (1985). On the history of the minimum spanning tree problem. Annals of the History of Computing, 7, 43–57.

Janiak, A., Kasperski, A., (2008). The minimum spanning tree problem with fuzzy costs. Fuzzy Optimization and Decision Making, 7, 105–18.

Kirzhner, V., Volkovich, Z., Ravve, E., Weber, G.-W. (2012). An Estimate of the Target Function Optimum for the Network Steiner Problem. Institute of Applied Mathematics, Preprint number 2012-20.

Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. American Math. Soc., 7, 48–50.

Montemanni, R. (2006). A Benders decomposition approach for the robust spanning tree problem with interval data. European Journal of Operational Research, 174, 1479–90.

Moore, R. (1995). Methods and applications of interval analysis, SIAM Studies in Applied Mathematics.

Moretti, S., Alparslan Gök, S. Z., Branzei, R., Tijs, S. (2011). Connection Situations under Uncertainty and Cost Monotonic Solutions. Computers and Operations Research, 38(11), 1638–1645.

Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell Systems Techn. J., 36, 1389–1401.

Suijs, J. (2003). Cost allocation in spanning network enterprises with stochastic connection costs. Games and Economic Behavior, 42, 156–171.

Tijs, S. (2003). Introduction to Game Theory. Hindustan Book Agency, India.

Tijs, S., Branzei, R., Moretti, S., Norde, H. (2006). Obligation rules for minimum cost spanning tree situations and their monotonicity properties. European Journal of Operational Research, 175, 121–34.

University of Waterloo, Combinatorics & Optimization, Discrete Optimization research group, http://math.uwaterloo.ca/combinatorics-and-optimization/research/areas/discreteoptimization.

Yaman, H., Karasan, O. E., Pinar, M. (1999). Minimum Spanning Tree Problem with Interval Data, Technical Report 9909, Bilkent University, Ankara, Turkey.

Yaman, H., Karasan, O. E., Pinar, M. (2001). The robust spanning tree problem with interval data. Operations Research Letters, 29, 31–40.