Carathéodory, Helly, and Radon Numbers for Sublattice and Related Convexities

References

• Amenta N, Bern M, Eppstein D, Teng S-H (2000) Regression depth and center points. Discrete Comput. Geometry 23(3):305–323.Crossref, Google Scholar
• Averkov G, Weismantel R (2012) Transversal numbers over subsets of linear spaces. Adv. Geometry 12(1):19–28.Crossref, Google Scholar
• Balandraud E, Queyranne M, Tardella F (2017) Largest minimal inversion-complete and pair-complete sets of permutations. Combinatorica, ePub ahead of print February 21, http://doi.org/10.1007/s00493-016-3426-6.Crossref, Google Scholar
• Bárány I (1982) A generalization of Carathédory’s theorem. Discr. Math. 40(2-3):141–152.Crossref, Google Scholar
• Bárány I, Matoušek J (2003) A fractional Helly theorem for convex lattice sets. Adv. Math. 174(2):227–235.Crossref, Google Scholar
• Barvinok A (2002) A Course in Convexity, Graduate Studies in Mathematics, Vol. 54 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• Bell DE (1977) A theorem concerning the integer lattice. Stud. Appl. Math. 56(2):187–188.Crossref, Google Scholar
• Bezdek K, Blokhuis A (2003) The Radon number of the three-dimensional integer lattice. Discrete Comput. Geom. 30(2):181–184.Crossref, Google Scholar
• Birkhoff G (1937) Rings of sets. Duke Math. J. 3(3):443–454.Crossref, Google Scholar
• Birkhoff G (1967) Lattice Theory, 3rd ed. American Mathematical Society Colloquium Publications, Vol. 25 (American Mathematical Society, Providence, RI).Google Scholar
• Boltyanski V, Martini H (2001) Carathéodory’s theorem and H-convexity. J. Combin. Theory Ser. A 93(2):292–309.Crossref, Google Scholar
• Boltyanski V, Martini H, Soltan PS (1997) Excursions Into Combinatorial Geometry, Universitext (Springer, Berlin).Crossref, Google Scholar
• Boltyanski VG (1976) Helly’s theorem for H-convex sets. Sov. Math., Dokl. 17:78–81.Google Scholar
• Boros E, Gurvich V, Liu Y (2005) Comparison of convex hulls and box hulls. Ars Combinatoria 77:193–204.Google Scholar
• Briec W, Horvath C (2004) 𝔹-convexity. Optimization 53(2):103–127.Crossref, Google Scholar
• Buchbinder N, Feldman M, Naor J, Schwartz R (2012) A tight linear time (1/2)-approximation for unconstrained submodular maximization. Proc. 53rd Annual IEEE Sympos. Foundations Comput. Sci. FOCS ’12 (IEEE Computer Society, Washington, DC), 649–658.Crossref, Google Scholar
• Butkovič P (2003) Max-algebra: The linear algebra of combinatorics? Linear Algebra Appl. 367:313–335.Crossref, Google Scholar
• Calder JR (1971) Some elementary properties of interval convexities. J. London Math. Soc. s2-3(3):422–428.Crossref, Google Scholar
• Carathéodory C (1907) Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen. Math. Ann. 64(1):95–115.Crossref, Google Scholar
• Chekuri C, Gupta S, Quanrud K (2015) Streaming algorithms for submodular function maximization. Automata, Languages, and Programming. Lecture Notes in Computer Science, Vol. 9134 (Springer, Berlin), 318–330.Crossref, Google Scholar
• Clarkson KL, Eppstein D, Miller GL, Sturtivant C, Teng S-H (1996) Approximating center points with iterated Radon points. Internat. J. Comput. Geom. Appl. 6(3):357–377.Crossref, Google Scholar
• Danzer L, Grünbaum B, Klee V (1963) Helly’s theorem and its relatives. Proc. Sympos. Pure Math., Vol. VII (American Mathematical Society, Providence, RI), 101–180.Crossref, Google Scholar
• Davey BA, Priestley HA (1990) Introduction to Lattices and Order (Cambridge University Press, Cambridge, UK).Google Scholar
• Develin M, Sturmfels B (2004) Tropical convexity. Doc. Math. 9:1–27.Google Scholar
• Doignon J-P (1973) Convexity in cristallographical lattices. J. Geometry 3(1):71–85.Crossref, Google Scholar
• Duchet P (1987) Convexity in combinatorial structures. Frolík Z, Souček V, Fabián MJ, eds. Proc. 14th Winter School on Abstract Anal. (Circolo Matematico di Palermo, Palermo, Italy), 261–293.Google Scholar
• Eckhoff J (1969) Der Satz von Radon in konvexen Produktstrukturen. II. Monatsh. Math. 73(1):7–30.Crossref, Google Scholar
• Eckhoff J (1993) Helly, Radon, and Carathéodory type theorems. Handbook of Convex Geometry, Vols. A, B (North-Holland, Amsterdam), 389–448.Crossref, Google Scholar
• Eckhoff J (2000) The partition conjecture. Discrete Math. 221(1-3):61–78.Crossref, Google Scholar
• Edmonds J (2001) Redundancy and Helly. Eur. J. Combin. 22(5):679–685.Crossref, Google Scholar
• Favati P, Tardella F (1990) Convexity in nonlinear integer programming. Ricerca Operativa 53:3–44.Google Scholar
• Fujishige S (2005) Submodular Functions and Optimization, 2nd ed. (Elsevier, Amsterdam).Google Scholar
• Fujishige S, Murota K (2000) Notes on L-/M-convex functions and the separation theorems. Math. Program. Ser. A 88(1):129–146.Crossref, Google Scholar
• Fujito T (2000) Approximation algorithms for submodular set cover with applications. IEICE Trans. Inf. Syst. E83-D(3):480–487.Google Scholar
• Gaubert S, Meunier F (2010) Carathéodory, Helly and the others in the max-plus world. Discrete Comput. Geom. 43(3):648–662.Crossref, Google Scholar
• Gaubert S, Sergeev S (2008) Cyclic projectors and separatioin theorems in idempotent convex geometry. J. Math. Sci. 155(6):815–829.Crossref, Google Scholar
• Gottschalk C, Peis B (2015) Submodular function maximization on the bounded integer lattice. Sanità L, Skutella M, eds. Approximation and Online Algorithms (Springer, Cham, Switzerland), 133–144.Crossref, Google Scholar
• Granot F, Veinott AF Jr (1985) Substitutes, complements and ripples in network flows. Math. Oper. Res. 10(1):471–497.Link, Google Scholar
• Granot F, McCormick ST, Queyranne M, Tardella F (2012) Structural and algorithmic properties for parametric minimum cuts. Math. Programming 135(1):337–367.Crossref, Google Scholar
• Helly E (1923) Über Mengen konvexer Körper mit gemeinschaftlichen Punkten. Deutsche Math.-Ver. 32:175–176.Google Scholar
• Jamison-Waldner RE (1982) A perspective on abstract convexity: Classifying alignments by varieties. Kay DC, Breen M, eds. Convexity and Related Combinatorial Geometry, Lecture Notes in Pure and Appl. Math., Vol. 76 (Marcel Dekker, New York), 113–150.Google Scholar
• Kay DC, Womble EW (1971) Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers. Pacific J. Math. 38(2):471–485.Crossref, Google Scholar
• Lee J, Sviridenko M, Vondrák J (2010) Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4):795–806.Link, Google Scholar
• Levi FW (1951) On Helly’s theorem and the axioms of convexity. J. Indian Math. Soc. (N.S.) Part A. 15:65–76.Google Scholar
• Lovász L (1983) Submodular functions and convexity. Bachem A, Grötschel M, Korte B, eds. Mathematical Programming—The State of the Art (Springer, Berlin), 235–257.Crossref, Google Scholar
• McCormick ST (2006) Submodular function minimization. Aardal K, Nemhauser GL, Weismantel R, eds. Handbook of Discrete Optimization (North-Holland, Amsterdam), 321–391.Google Scholar
• Milgrom P, Shannon C (1994) Monotone comparative statics. Econometrica 62(1):157–180.Crossref, Google Scholar
• Murota K (2003) Discrete Convex Analysis, SIAM Monographs on Discrete Mathematics and Applications 10 (SIAM, Philadelphia).Crossref, Google Scholar
• Murota K, Shioura A (2000) Extension of M-convexity and L-convexity to polyhedral convex functions. Adv. Appl. Math. 25(4):352–427.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization (John Wiley & Sons, New York).Crossref, Google Scholar
• Onn S (1991) On the geometry and computational complexity of Radon partitions in the integer lattice. SIAM J. Discrete Math. 4(3):436–446.Crossref, Google Scholar
• Queyranne M, Tardella F (2006) Bimonotone linear inequalities and sublattices of ℝn. Linear Algebra Appl. 413(1):100–120.Crossref, Google Scholar
• Queyranne M, Tardella F (2008) Sublattices of product spaces: Hulls, representations and counting. Discrete Math. 308(9):1508–1523.Crossref, Google Scholar
• Rado R (1946) A theorem on general measure. J. London Math. Soc. s1-21(4):291–300.Crossref, Google Scholar
• Radon J (1921) Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten. Math. Ann. 83(1–2):113–115.Crossref, Google Scholar
• Reay JR (1970) Carathéodory theorems in convex product structures. Pacific J. Math. 35(1):227–230.Crossref, Google Scholar
• Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Scarf HE (1977) An observation on the structure of production sets with indivisibilities. Proc. Natl. Acad. Sci. USA 74(9):3637–3641.Crossref, Google Scholar
• Sierksma G (1975) Carathéodory and Helly-numbers of convex-product-structures. Pacific J. Math. 61(1):275–282.Crossref, Google Scholar
• Sierksma G (1977) Relationships between Carathéodory, Helly, Radon and exchange numbers of convexity spaces. Nieuw Arch. Wisk. (3) 25(2):115–132.Google Scholar
• Sierksma G (1982) Generalizations of Helly’s theorem; open problems. Kay DC, Breen M, eds. Convexity and Related Combinatorial Geometry, Lecture Notes in Pure and Appl. Math., Vol. 76 (Marcel Dekker, New York), 173–192.Google Scholar
• Soltan VP (1976) Certain questions of the abstract theory of convexity. Dokl. Akad. Nauk SSSR 228(2):310–313.Google Scholar
• Soma T, Yoshida Y (2016) Maximizing monotone submodular functions over the integer lattice. Louveaux Q, Skutella M, eds. Proc. 18th Internat. Conf. Integer Programming and Combinatorial Optimization, IPCO ’16 (Springer, Berlin), 325–336.Crossref, Google Scholar
• Topkis DM (1976) The structure of sublattices of the product of n lattices. Pacific J. Math. 65(2):525–532.Crossref, Google Scholar
• Topkis DM (1978) Minimizing a submodular function on a lattice. Oper. Res. 26(2):305–321.Link, Google Scholar
• Topkis DM (1998) Supermodularity and Complementarity (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• van de Vel MLJ (1993) Theory of Convex Structures, North-Holland Mathematical Library, Vol. 50 (North-Holland, Amsterdam).Google Scholar
• Vapnik V, Chervonenkis A (1971) On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability Appl. 16(2):264–280.Crossref, Google Scholar
• Veinott AF Jr (1989) Representation of general and polyhedral subsemilattices and sublattices of product spaces. Linear Algebra Appl. 114/115:681–704.Crossref, Google Scholar
• Veinott AF Jr (1989) Lattice Programming, Mathematical Sciences Lecture Series (Johns Hopkins University, Baltimore).Google Scholar
• Veinott AF Jr (1992) Lattice Programming: Qualitative Optimization and Equilibria. Stanford University, Mimeo.Google Scholar