×

Unique sink orientations of grids. (English) Zbl 1203.68124

Summary: We introduce unique sink orientations of grids as digraph models for many well-studied problems, including linear programming over products of simplices, generalized linear complementarity problems over P-matrices (PGLCP), and simple stochastic games.
We investigate the combinatorial structure of such orientations and develop randomized algorithms for finding the sink. We show that the orientations arising from PGLCP satisfy the Holt-Klee condition known to hold for polytope digraphs, and we give the first expected linear-time algorithms for solving PGLCP with a fixed number of blocks.

MSC:

68R10 Graph theory (including graph drawing) in computer science

Software:

Miniball; OEIS
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Adler, I., Saigal, R.: Long monotone paths in abstract polytopes. Math. Oper. Res. 1(1), 89–95 (1976) · Zbl 0457.90047 · doi:10.1287/moor.1.1.89
[2] Björklund, H., Sandberg, S., Vorobyov, S.: Randomized subexponential algorithms for parity games. Technical Report TR-2003-019, Department of Information Technology, Uppsala University (2003) · Zbl 1035.68134
[3] Björklund, H., Sandberg, S., Vorobyov, S.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. In: Proc. 29th International Symposium on Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science, vol. 3153, pp. 673–685. Springer, Berlin (2004) · Zbl 1097.91020
[4] Blind, R., Mani-Levitska, P.: On puzzles and polytope isomorphisms. Aequ. Math. 34, 287–297 (1987) · Zbl 0634.52005 · doi:10.1007/BF01830678
[5] Chazelle, B., Matoušek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms 21, 579–597 (1996) · Zbl 0864.68040 · doi:10.1006/jagm.1996.0060
[6] Chvátal, V.: Linear Programming. Freeman, New York (1983) · Zbl 0537.90067
[7] Clarkson, K.L.: Las Vegas algorithms for linear and integer programming. J. ACM 42, 488–499 (1995) · Zbl 0885.65063 · doi:10.1145/201019.201036
[8] Condon, A.: On algorithms for simple stochastic games. In: Cai, J.-Y. (ed.) Advances in Computational Complexity Theory. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 51–73. American Mathematical Society, Providence (1993) · Zbl 0808.90141
[9] Cottle, R.W., Dantzig, G.B.: A generalization of the linear complementarity problem. J. Comb. Theory 8, 79–90 (1970) · Zbl 0186.23806 · doi:10.1016/S0021-9800(70)80010-2
[10] Cottle, R.W., Pang, J., Stone, R.E.: The Linear Complementarity Problem. Academic, San Diego (1992)
[11] Develin, M.: LP-orientations of cubes and crosspolytopes. Adv. Geom. 4, 459–468 (2004) · Zbl 1067.52012 · doi:10.1515/advg.2004.4.4.459
[12] Ebiefung, A.A.: Existence theory and Q-matrix characterization for the generalized linear complementarity problem. Linear Algebra Appl. 223/224, 155–169 (1995) · Zbl 0835.90100 · doi:10.1016/0024-3795(95)00091-5
[13] Ebiefung, A.A.: Existence theory and Q-matrix characterization for the generalized linear complementarity problem: Revisited. Manuscript (2005) · Zbl 1154.90598
[14] Ewald, G.: Combinatorial Convexity and Algebraic Geometry. Springer, Berlin (1996) · Zbl 0869.52001
[15] Felsner, S., Gärtner, B., Tschirschnitz, F.: Grid orientations, (d,d+2)-polytopes, and arrangements of pseudolines. Discrete Comput. Geom. 34(3), 411–437 (2005) · Zbl 1151.52011 · doi:10.1007/s00454-005-1187-x
[16] Fischer, K., Gärtner, B.: The smallest enclosing ball of balls: combinatorial structure and algorithms. Int. J. Comput. Geom. Appl. 14(4&5), 341–378 (2004) · Zbl 1084.68132 · doi:10.1142/S0218195904001500
[17] Gärtner, B.: The Random-Facet simplex algorithm on combinatorial cubes. Random Struct. Algorithms 20(3), (2002) · Zbl 1017.68159
[18] Gärtner, B., Rüst, L.: Simple stochastic games and P-matrix generalized linear complementarity problems. In: Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT). Lecture Notes in Computer Science, vol. 3623, pp. 209–220. Springer, Berlin (2005) · Zbl 1122.91018
[19] Gärtner, B., Schurr, I.: Linear programming and unique sink orientations. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 749–757, 2006 · Zbl 1192.90121
[20] Gärtner, B., Welzl, E.: Linear programming–randomization and abstract frameworks. In: Proc. 13th Ann. ACM Symp. Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 1046, pp. 669–687. Springer, Berlin (1996) · Zbl 1380.90184
[21] Gärtner, B., Welzl, E.: Explicit and implicit enforcing–randomized optimization. In: Lecture Notes of the Graduate Program Computational Discrete Mathematics. Lecture Notes in Computer Science, vol. 2122, pp. 26–49. Springer, Berlin (2001)
[22] Gärtner, B., Solymosi, J., Tschirschnitz, F., Valtr, P., Welzl, E.: One line and n points. Random Struct. Algorithms 23(4), 453–471 (2003) (preliminary version at STOC 2001) · Zbl 1154.90545 · doi:10.1002/rsa.10099
[23] Gärtner, B., Matoušek, J., Rüst, L., Škovroň, P.: Violator spaces: structure and algorithms. In: Proc. 14th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science. Springer, Berlin (2006)
[24] Gordan, P.: Über die Auflösung linearer Gleichungen mit reellen Coefficienten. Math. Ann. 6, 23–28 (1873) · JFM 05.0095.01 · doi:10.1007/BF01442864
[25] Grädel, E., Thomas, W., Wilke, T.: Automata, Logics, and Infinite Games. Lecture Notes in Computer Science, vol. 2500. Springer, Berlin (2002) · Zbl 1011.00037
[26] Hoke, K.W.: Completely unimodal numberings of a simple polytope. Discrete Appl. Math. 20, 69–81 (1988) · Zbl 0652.90077 · doi:10.1016/0166-218X(88)90042-X
[27] Holt, F., Klee, V.: A proof of the strict monotone 4-step conjecture. In: Chazelle, J., Goodman, J.B., Pollack, R. (eds.) Advances in Discrete and Computational Geometry. Contemporary Mathematics. Am. Math. Soc., Providence (1998)
[28] Kalai, G.: A simple way to tell a simple polytope from its graph. J. Comb. Theory 49, 381–383 (1988) · Zbl 0673.05087 · doi:10.1016/0097-3165(88)90064-7
[29] Kalai, G.: Linear programming, the simplex algorithm and simple polytopes. Math. Program. 79, 217–233 (1997) · Zbl 0887.90116
[30] Kalai, G., Kleitman, D.J.: A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull. Am. Math. Soc. 26, 315–316 (1992) · Zbl 0751.52006 · doi:10.1090/S0273-0979-1992-00285-9
[31] Khachiyan, L.G.: Polynomial algorithms in linear programming. USSR Comput. Math. Math. Phys. 20, 53–72 (1980) · Zbl 0459.90047 · doi:10.1016/0041-5553(80)90061-0
[32] Klee, V., Minty, G.J.: How good is the simplex algorithm? In: Shisha, O. (ed.) Inequalities III, pp. 159–175. Academic, San Diego (1972) · Zbl 0297.90047
[33] Kleinschmidt, P., Onn, S.: Signable posets and partitionable simplicial complexes. Discrete Comput. Geom. 15, 443–466 (1996) · Zbl 0853.52010 · doi:10.1007/BF02711519
[34] Ludwig, W.: A subexponential randomized algorithm for the simple stochastic game problem. Inform. Comput. 117, 151–155 (1995) · Zbl 0827.90141 · doi:10.1006/inco.1995.1035
[35] Matoušek, J.: Lower bounds for a subexponential optimization algorithm. Random Struct. Algorithms 5(4), 591–607 (1994) · Zbl 0824.90094 · doi:10.1002/rsa.3240050408
[36] Matoušek, J., Sharir, M., Welzl, E.: A subexponential bound for linear programming. Algorithmica 16, 498–516 (1996) · Zbl 0857.68119 · doi:10.1007/BF01940877
[37] Megiddo, N.: A note on the complexity of P-matrix LCP and computing an equilibrium. Technical Report, IBM Almaden Research Center, San Jose (1988)
[38] Morris, W.D. Jr.: Distinguishing cube orientations arising from linear programs. Manuscript (2002)
[39] Schäfer, U.: A linear complementarity problem with a P-matrix. SIAM Rev. 46(2), 189–201 (2004) · Zbl 1133.90402 · doi:10.1137/S0036144502420083
[40] Schurr, I., Szabó, T.: Jumping doesn’t help in abstract cubes. In: Proc. 11th Conference on Integer Programming and Combinatorial Optimization (IPCO). Lecture Notes in Computer Science, vol. 3509, pp. 225–235. Springer, Berlin (2005) · Zbl 1119.90367
[41] Seidel, R.: Small-dimensional linear programming and convex hulls made easy. Discrete Comput. Geom. 6, 423–434 (1991) · Zbl 0747.90066 · doi:10.1007/BF02574699
[42] Sloane, N.J.A.: Sequence A000522. The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/\(\sim\)njas/sequences/ (2004)
[43] Stickney, A., Watson, L.: Digraph models of Bard-type algorithms for the linear complementarity problem. Math. Oper. Res. 3, 322–333 (1978) · Zbl 0396.90096 · doi:10.1287/moor.3.4.322
[44] Stiemke, E.: Über positive Lösungen homogener linearer Gleichungen. J. Reine Angew. Math. 76, 340–342 (1915) · JFM 45.0168.04
[45] Szabó, T., Welzl, E.: Unique sink orientations of cubes. In: Proc. 42nd IEEE Symp. on Foundations of Comput. Sci., pp. 547–555, 2000
[46] Tschirschnitz, F.: LP-related properties of polytopes with few facets. PhD Thesis, ETH Zürich (2003)
[47] Welzl, E.: Smallest enclosing disks (balls and ellipsoids). In: Maurer, H. (ed.) New Results and New Trends in Computer Science. Lecture Notes in Computer Science, vol. 555, pp. 359–370. Springer, Berlin (1991)
[48] Wiedemann, D.: Unimodal set-functions. Congr. Numer. 50, 165–169 (1985) · Zbl 0619.05043
[49] Ziegler, G.M.: Lectures on Polytopes. Springer, Berlin (1995) · Zbl 0823.52002
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.