Structures of polyhedra determined by submodular functions on crossing families

The present paper shows that for any submodular functionf on a crossing family with , if the polyhedron is nonempty, then there exist a unique distributive lattice with and a unique submodular function with such thatB(f) coincides with the base polyhedron associated with the submodular system . Here, iff is integer-valued, thenf ₁ is also integer-valued. Based on this fact, we also show the relationship between the independent-flow problem considered by the author and the minimum cost flow problem considered by J. Edmonds and R. Giles.     

Polyhedra related to integer-convex polynomial systems

This paper deals with the reformulation of a polynomial integer program. For deducing a linear integer relaxation of such a program a class of polyhedra that are associated with nonlinear functions is introduced. A characterization of the family of polynomials for which our approach leads to an equivalent linear integer program is given. Finally the family of so-called integer-convex polynomials is defined, and polyhedra related to such a polynomial are investigated. Supported by DFG-Forschergruppe FOR-468 Received: April, 2004     

A characterization of network representable polymatroids

Meggido [1974] showed that the maximum flow through sets of sources in a multiple sink flow network is a polymatroidal function. Recently, Federgruen and Groenevelt [1985], [1986] have considered polymatroids that can be represented by a multiple source flow network and have improved the runnung time of an important scheduling application.We give a characterization of network representability and relate representable polymatroids to the theory of gammoids.

---

Zusammenfassung Meggido [1974] hat gezeigt, daß ein maximaler Fluß durch ein Netzwerk mit mehrfachen Senken eine polymatroidale Funktion beschreibt. Federgruen und Groenvelt [1985], [1986] haben kürzlich solche Polymatroide betrachtet, die durch Flüsse in derartigen Netzwerken repräsentiert werden können und haben so die Laufzeit einer wichtigen Schedulinganwendung verbessern können.Wir geben eine Charakterisierung von Funktionen, die durch derartige Netzflußnetzwerke realisierbar sind. Dabei stellen wir eine Verbindung her zwischen Repräsentierbarkeit und Gammoidtheorie.

     

On the subdifferential of a submodular function

The author recently introduced a concept of a subdifferential of a submodular function defined on a distributive lattice. Each subdifferential is an unbounded polyhedron. In the present paper we determine the set of all the extreme points and rays of each subdifferential and show the relationship between subdifferentials of a submodular function and subdifferentials, in an ordinary sense of convex analysis, of Lovász's extension of the submodular function. Furthermore, for a modular function on a distributive lattice we give an algorithm for determining which subdifferential contains a given vector and finding a nonnegative linear combination of extreme vectors of the subdifferential which expresses the given vector minus the unique extreme point of the subdifferential.     

On the complexity of submodular function minimisation on diamonds

Let (L;?,?) be a finite lattice and let n be a positive integer. A function f:Lⁿ→R is said to be submodular if for all . In this article we study submodular functions when L is a diamond. Given oracle access to f we are interested in finding such that 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→Z and an integer m such that , there is a proof of this fact which can be verified in time polynomial in n and ; and

• • 

  a pseudopolynomial-time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular f:Ln→Z one can find in time bounded by a polynomial in n and .

     

Integral decomposition in polyhedra

We say that a polyhedronP satisfies weak integral decomposition if whenever an integral vector is the sum ofk vectors inP it is also the sum ofk integral vectors inP. This property is related to rounding results for packing and covering problems. We study the property and two related properties, and give results concerning integral polymatroids, totally unimodular matrices and network flows, pairs of strongly-base-orderable matroids, and branchings in directed graphs.     

On Factorizations of Smooth Nonnegative Matrix-Values Functions and on Smooth Functions with Values in Polyhedra

We discuss the possibility to represent smooth nonnegative matrix-valued functions as finite linear combinations of fixed matrices with positive real-valued coefficients whose square roots are Lipschitz continuous. This issue is reduced to a similar problem for smooth functions with values in a polyhedron. The work was partially supported by NSF Grant DMS-0653121.     

On the involutions fixing the class of a lattice

With any integral lattice Λ in n-dimensional Euclidean space we associate an elementary abelian 2-group I(Λ) whose elements represent parts of the dual lattice that are similar to Λ. There are corresponding involutions on modular forms for which the theta series of Λ is an eigenform; previous work has focused on this connection. In the present paper I(Λ) is considered as a quotient of some finite 2-subgroup of . We establish upper bounds, depending only on n, for the order of I(Λ), and we study the occurrence of similarities of specific types.     

The area of empty axis-parallel boxes amidst 2-dimensional lattice points

The dispersion of a point set in the unit square is the area of the largest empty axis-parallel box. In this paper we are interested in the dispersion of lattices in the plane, that is, the supremum of the area of the empty axis-parallel boxes amidst the lattice points. We introduce a framework with which to study this based on the continued fractions expansions of the lattice generators. We give necessary and sufficient conditions under which a lattice has finite dispersion. We obtain an exact formula for the dispersion of the lattices associated to subrings of the ring of integers of quadratic fields. We have tight bounds for the dispersion of a lattice based on the largest continued fraction coefficient of the generators, accurate to within one half. We provide an equivalent formulation of Zaremba's conjecture. Using this framework we are able to give very short proofs of previous results.     

(1,k)-configurations and facets for packing problems

A new class of facets for knapsack polytopes is obtained. This class of inequalities is shown to define a polytope with zero–one vertices only. A combinatorial inequality is obtained from Fulkerson's max—max inequality.     

A note on maximizing a submodular set function subject to a knapsack constraint

In this paper, we obtain an (1−e⁻¹)-approximation algorithm for maximizing a nondecreasing submodular set function subject to a knapsack constraint. This algorithm requires O(n⁵) function value computations.     

Distribution of lattice orbits on homogeneous varieties

Given a lattice Γ in a locally compact group G and a closed subgroup H of G, one has a natural action of Γ on the homogeneous space V = H\ G. For an increasing family of finite subsets {Γ _T : T > 0}, a dense orbit υ· Γ, υ∈V and compactly supported function φ on V, we consider the sums . Understanding the asymptotic behavior of S _φ,υ (T) is a delicate problem which has only been considered for certain very special choices of H,G and {Γ _T }. We develop a general abstract approach to the problem, and apply it to the case when G is a Lie group and either H or G is semisimple. When G is a group of matrices equipped with a norm, we have where G _T = {g ∈G: ||g|| < T} and Γ _T = G _T ∩ Γ. We also show that the asymptotics of S _{φ, υ} (T) is governed by where ν is an explicit limiting density depending on the choice of υ and || · ||. Submitted: March 2005 Revision: April 2006 Accepted: June 2006     

Geometric lattice actions, entropy and fundamental groups

Let be a lattice in a noncompact simple Lie Group G, where . Suppose acts analytically and ergodically on a compact manifold M preserving a unimodular rigid geometric structure (e.g. a connection and a volume). We show that either the action is isometric or there exists a "large image" linear representation of . Under an additional assumption on the dynamics of the action, we associate to a virtual arithmetic quotient of full entropy. Received: December 14, 2000     

On the Singularities of Fractionalized Potential Functions

The singularities of harmonic functions generated under the action of an integral transform with a fractionalized kernel are studied. A simple relationship arises connecting pairs of singularities.     

An analysis of approximations for maximizing submodular set functions—I

LetN be a finite set andz be a real-valued function defined on the set of subsets ofN that satisfies z(S)+z(T)z(ST)+z(ST) for allS, T inN. Such a function is called submodular. We consider the problem max_SN{a(S):|S|K,z(S) submodular}.Several hard combinatorial optimization problems can be posed in this framework. For example, the problem of finding a maximum weight independent set in a matroid, when the elements of the matroid are colored and the elements of the independent set can have no more thanK colors, is in this class. The uncapacitated location problem is a special case of this matroid optimization problem.We analyze greedy and local improvement heuristics and a linear programming relaxation for this problem. Our results are worst case bounds on the quality of the approximations. For example, whenz(S) is nondecreasing andz(0) = 0, we show that a greedy heuristic always produces a solution whose value is at least 1 –[(K – 1)/K] ^K times the optimal value. This bound can be achieved for eachK and has a limiting value of (e – 1)/e, where e is the base of the natural logarithm.On leave of absence from Cornell University and supported, in part, by NSF Grant ENG 75-00568.Supported, in part, by NSF Grant ENG 76-20274.     

Optimization over the polyhedron determined by a submodular function on a co-intersecting family

A greedy algorithm solves the problem of maximizing a linear objective function over the polyhedron (called the submodular polyhedron) determined by a submodular function on a distributive lattice or a ring family. We generalize the problem by considering a submodular function on a co-intersecting family and give an algorithm for solving it. Here, simple-minded greedy augmentations do not work any more and some complicated augmentations with multiple exchanges are required. We can find an optimal solution by at most 1/2n(n – 1) augmentations, wheren is the number of the variables and we assume a certain oracle for computing multiple exchange capacities.     

On an inverse problem of entropy othimization and related questions

In a fundamental paper Arov and Krein studied entropy minimization problems over a set of matrix-valued Schur functions which arises from a fractional linear transformation the generating matrix-valued function of which is a j_pq -inner function.Our paper handles the corresponding inverse problem: If a p x q Schur function f is given, then the problem is to determine all j_pq -inner functions for which f turns out to be the associatedentropy-minimal function     

Lie algebras whose lattice of ideals is closely related with a subspace lattice

Relationships between the structure of a Lie algebra and that of its lattice of ideals is studied for those Lie algebras whose ideal lattice is very close to that of an almost-abelian Lie algebra. It is shown here that if the base field is algebraically closed, finite or the real one, for any n ≥3 the only solvable Lie algebra whose lattice of ideals is isomorphic to that of the (n+l)-dimensional almost-abelian Lie algebra is itself.     

Z-连续格的函数空间

若 Z为并完备的子集系统 ,且 IZ( L)关于集合的包含关系构成完备格 ,则 :( 1 ) Z-连续格的函数空间仍为 Z-连续的 ;( 2 )对于 Z-连续格范畴 ZL ,定义了一函子 F:ZL× ZL→ ZL.