2009/04/21 by Fredrik Kuivinen, Kuivinen, Fredrik · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.0904.3183
31 pages, 2 figures
arxiv created 2009/04/21 · openalex publication_date 2009/04/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let (L; \sqcap, \sqcup) be a finite lattice and let n be a positive integer. A function f : Ln → ℝ is said to be submodular if f(\tupa \sqcap \tupb) + f(\tupa \sqcup \tupb) ≤ f(\tupa) + f(\tupb) for all \tupa, \tupb ∈ Ln. In this paper we study submodular functions when L is a diamond. Given oracle access to f we are interested in finding \tupx ∈ Ln such that f(\tupx) = min_\tupy ∈ Ln f(\tupy) as efficiently as possible. We establish a min--max theorem, which states that the minimum of the submodular function is equal to the maximum of a certain function defined over a certain polyhedron; and a good characterisation of the minimisation problem, i.e., we show that given an oracle for computing a submodular f : Ln → ℤ and an integer m such that min_\tupx ∈ Ln f(\tupx) = m, there is a proof of this fact which can be verified in time polynomial in n and max_\tupt ∈ Ln log |f(\tupt)|; and a pseudo-polynomial time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular f : Ln → ℤ one can find min_\tupt ∈ Ln f(\tupt) in time bounded by a polynomial in n and max_\tupt ∈ Ln |f(\tupt)|.