Partially ordered knapsack and applications to scheduling

In the partially ordered knapsack problem (POK) we are given a set N of items and a partial order ?_P on N. Each item has a size and an associated weight. The objective is to pack a set N^′⊆N of maximum weight in a knapsack of bounded size. N^′ should be precedence-closed, i.e., be a valid prefix of ?_P. POK is a natural generalization, for which very little is known, of the classical Knapsack problem. In this paper we present both positive and negative results. We give an FPTAS for the important case of a two-dimensional partial order, a class of partial orders which is a substantial generalization of the series-parallel class, and we identify the first non-trivial special case for which a polynomial-time algorithm exists. Our results have implications for approximation algorithms for scheduling precedence-constrained jobs on a single machine to minimize the sum of weighted completion times, a problem closely related to POK.     

Unary Semigroups with an Associate Subgroup

A subgroup H of a regular semigroup S is said to be an associate subgroup of S if for every s ∈ S, there is a unique associate of s in H. An idempotent z of S is said to be medial if czc = c, for every c product of idempotents of S. Blyth and Martins established a structure theorem for semigroups with an associate subgroup whose identity is a medial idempotent, in terms of an idempotent generated semigroup, a group and a single homomorphism. Here, we construct a system of axioms which characterize these semigroups in terms of a unary operation satisfying those axioms. As a generalization of this class of semigroups, we characterize regular semigroups S having a subgroup which is a transversal of a congruence on S.     

The Yoneda Algebra of a 𝒦2 Algebra Need not be Another 𝒦2 Algebra

The Yoneda algebra of a Koszul algebra or a D-Koszul algebra is Koszul. 𝒦₂ algebras are a natural generalization of Koszul algebras, and one would hope that the Yoneda algebra of a 𝒦₂ algebra would be another 𝒦₂ algebra. We show that this is not necessarily the case by constructing a monomial 𝒦₂ algebra for which the corresponding Yoneda algebra is not 𝒦₂.     

Positive Lyapunov exponent for generic one-parameter families of unimodal maps

Letf _{a a∈A} be a C² one-parameter family of non-flat unimodal maps of an interval into itself anda* a parameter value such that

1. f_a* satisfies the Misiurewicz Condition,
2. f_a* satisfies a backward Collet-Eckmann-like condition,
3. the partial derivatives with respect tox anda of f _a ⁿ (x), respectively at the critical value and ata*, are comparable for largen.

Thena* is a Lebesgue density point of the set of parameter valuesa such that the Lyapunov exponent of f_a at the critical value is positive, and f_a admits an invariant probability measure absolutely continuous with respect to the Lebesgue measure. We also show that given f_a* satisfying (a) and (b), condition (c) is satisfied for an open dense set of one-parameter families passing through f_a*.     

A First Order Sufficient Condition for Optimality in Nonsmooth Optimization

We derive a simple sufficient condition for a point a∈S?X be a local minimum of f: X → R on S. This condition is of the first order in its nature and takes into account the derivative (or some generalization of it) in a neighborhood of a. Applications like a sufficient condition for (a, b)∈ S × T ? X × Y be a saddle-point of a bivariate function f: X × Y ? R are also proposed.     

A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set {1,2,…,n}, the local direction of each edge (ij) is from i to j if i<j. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence λ=e₁¹e₂²… of a tree on the vertex set {1,2,…,n} is a partition of n−1. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a q-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.     

EDGE SUBDIVISIONS OF A GIVEN GEODETIC BLOCK PRESERVING ITS PROPERTY TO BE GEODETIC

1IntroductionInthispaperweshallconsideronlyundirected2-connectedsimplegraphs,i.e,graphsthatareloopless,finite,undirectedandwithoutmultipleedges.AgraphGissaidtobegeodeticifanypairofpointsofGarejoinedbyauniquepathofshortestlength,i.e,aulliquedistancepath[1].A2-connectedgeodeticgraphiscalledageodeticblock.Agrapllisgeodeticiffeachofitsblocksisgeodetic(seeStempleandWatkins['l).Obviously,oddcycle,tree,completegrapharegeodeticgraph,wecallthemthetrivialgeodeticgraph.Nowweonlycollsidertilenontrivial…     

Algorithms for finding distance-edge-colorings of graphs

For a bounded integer ℓ, we wish to color all edges of a graph G so that any two edges within distance ℓ have different colors. Such a coloring is called a distance-edge-coloring or an ℓ-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.     

CH, a problem of Rolewicz and bidiscrete systems

We give a construction under CH of a non-metrizable compact Hausdorff space K such that any uncountable ‘nice’ semi-biorthogonal sequence in C(K) must be of a very specific kind. The space K has many nice properties, such as being hereditarily separable, hereditarily Lindelöf and a 2-to-1 continuous preimage of a metric space, and all Radon measures on K are separable. However K is not a Rosenthal compactum.We introduce the notion of a bidiscrete system in a compact space K. These are subsets of K² which determine biorthogonal systems of a special kind in C(K) that we call nice. We note that for every infinite compact Hausdorff space K, the space C(K) has a bidiscrete system and hence a nice biorthogonal system of size d(K), the density of K.     

On the Location of Pseudozeros of a Complex Interval Polynomial

Given a univariate complex interval polynomial F, we provide a rigorous method for deciding whether there exists a pseudozero of F in a prescribed closed complex domain D. Here a pseudozero of F is defined to be a zero of some polynomial in F. We use circular intervals and assume that the boundary C of D is a simple curve and that C is the union of a finite number of arcs, each of which is represented by a rational function. When D is not bounded, we assume further that all the polynomials in F are of the same degree. Examples of such domains are the outside of an open disk and a half-plane with boundary. Our decision method uses the representation of C and the property that a polynomial in F is of degree 1 with respect to each coefficient regarded as a variable.      

Straight Rings

A (commutative integral) domain is called a straight domain if A ? B is a prime morphism for each overring B of A; a (commutative unital) ring A is called a straight ring if A/P is a straight domain for all P ∈ Spec(A). A domain is a straight ring if and only if it is a straight domain. The class of straight rings sits properly between the class of locally divided rings and the class of going-down rings. An example is given of a two-dimensional going-down domain that is not a straight domain. The classes of straight rings, of locally divided rings, and of going-down rings coincide within the universe of seminormal weak Baer rings (for instance, seminormal domains). The class of straight rings is stable under formation of homomorphic images, rings of fractions, and direct limits. The “straight domain" property passes between domains having the same prime spectrum. Straight domains are characterized within the universe of conducive domains. If A is a domain with a nonzero ideal I and quotient field K, characterizations are given for A ? (I: _K I) to be a prime morphism. If A is a domain and P ∈ Spec(A) such that A _P is a valuation domain, then the CPI-extension C(P) := A + PA _P is a straight domain if and only if A/P is a straight domain. If A is a going-down domain and P ∈ Spec(A), characterizations are given for A ? C(P) to be a prime morphism. Consequences include divided domain-like behavior of arbitrary straight domains.     

Transitive partial actions of groups

J. Kellendonk and M. V. Lawson established that each partial action of a group G on a set Y can be extended to a global action of G on a set Y _G containing a copy of Y. In this paper we classify transitive partial group actions. When G is a topological group acting on a topological space Y partially and transitively we give a condition for having a Hausdorff topology on Y _G such that the global group action of G on Y _G is continuous and the injection Y into Y _G is an open dense equivariant embedding.      

On the completion of a partial integral matrix to a unimodular matrix

We prove that if a partial integral matrix has a free diagonal then this matrix can be completed to a unimodular matrix. Such a condition is necessary in a general sense. Consequently if an n × n (n ? 2) partial integral matrix has 2n − 3 prescribed entries and any n entries of these do not constitute a row or a column then it can be completed to a unimodular matrix. This improves a recent result of Zhan.     

Convexity properties of gradient maps

We consider the action of a real reductive group G on a Kähler manifold Z which is the restriction of a holomorphic action of a complex reductive group H. We assume that the action of a maximal compact subgroup U of H is Hamiltonian and that G is compatible with a Cartan decomposition of H. We have an associated gradient map μp:Z→p where g=k⊕p is the Cartan decomposition of g. For a G-stable subset Y of Z we consider convexity properties of the intersection of μp(Y) with a closed Weyl chamber in a maximal abelian subspace a of p. Our main result is a Convexity Theorem for real semi-algebraic subsets Y of Z=P(V) where V is a unitary representation of U.     

Global convergence of a class of non-interior point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems

We propose a class of non-interior point algorithms for solving the complementarity problems(CP): Find a nonnegative pair (x,y)∈ℝ ²ⁿ satisfying y=f(x) and x _i y _i =0 for every i∈{1,2,...,n}, where f is a continuous mapping from ℝ ⁿ to ℝ ⁿ . The algorithms are based on the Chen-Harker-Kanzow-Smale smoothing functions for the CP, and have the following features; (a) it traces a trajectory in ℝ ³ⁿ which consists of solutions of a family of systems of equations with a parameter, (b) it can be started from an arbitrary (not necessarily positive) point in ℝ ²ⁿ in contrast to most of interior-point methods, and (c) its global convergence is ensured for a class of problems including (not strongly) monotone complementarity problems having a feasible interior point. To construct the algorithms, we give a homotopy and show the existence of a trajectory leading to a solution under a relatively mild condition, and propose a class of algorithms involving suitable neighborhoods of the trajectory. We also give a sufficient condition on the neighborhoods for global convergence and two examples satisfying it. Received April 9, 1997 / Revised version received September 2, 1998? Published online May 28, 1999     

On the identric and logarithmic means

Summary Leta, b > 0 be positive real numbers. The identric meanI(a, b) of a andb is defined byI = I(a, b) = (1/e)(b ^b /a ^a ) ^1/(b–a) , fora b, I(a, a) = a; while the logarithmic meanL(a, b) ofa andb isL = L(a, b) = (b – a)/(logb – loga), fora b, L(a, a) = a. Let us denote the arithmetic mean ofa andb byA = A(a, b) = (a + b)/2 and the geometric mean byG =G(a, b) = . In this paper we obtain some improvements of known results and new inequalities containing the identric and logarithmic means. The material is divided into six parts. Section 1 contains a review of the most important results which are known for the above means. In Section 2 we prove an inequality which leads to some improvements of known inequalities. Section 3 gives an application of monotonic functions having a logarithmically convex (or concave) inverse function. Section 4 works with the logarithm ofI(a, b), while Section 5 is based on the integral representation of means and related integral inequalities. Finally, Section 6 suggests a new mean and certain generalizations of the identric and logarithmic means.     

Sets in a euclidean space which are not a countable union of convex subsets

We prove that if a closed planar setS is not a countable union of convex subsets, then exactly one of the following holds:

On Euclidean distance matrices

If A is a real symmetric matrix and P is an orthogonal projection onto a hyperplane, then we derive a formula for the Moore-Penrose inverse of PAP. As an application, we obtain a formula for the Moore-Penrose inverse of an Euclidean distance matrix (EDM) which generalizes formulae for the inverse of a EDM in the literature. To an invertible spherical EDM, we associate a Laplacian matrix (which we define as a positive semidefinite n × n matrix of rank n − 1 and with zero row sums) and prove some properties. Known results for distance matrices of trees are derived as special cases. In particular, we obtain a formula due to Graham and Lovász for the inverse of the distance matrix of a tree. It is shown that if D is a nonsingular EDM and L is the associated Laplacian, then D⁻¹ − L is nonsingular and has a nonnegative inverse. Finally, infinitely divisible matrices are constructed using EDMs.     

Netlike partial cubes II. Retracts and netlike subgraphs

First we show that the class of netlike partial cubes is closed under retracts. Then we prove, for a subgraph G of a netlike partial cube H, the equivalence of the assertions: G is a netlike subgraph of H; G is a hom-retract of H; G is a retract of H. Finally we show that a non-trivial netlike partial cube G, which is a retract of some bipartite graph H, is also a hom-retract of H if and only if G contains at most one convex cycle of length greater than 4.     

Bimodule herds

The notion of a bimodule herd is introduced and studied. A bimodule herd consists of a B-A bimodule, its formal dual, called a pen, and a map, called a shepherd, which satisfies unitality and coassociativity conditions. It is shown that every bimodule herd gives rise to a pair of corings and coactions. If, in addition, a bimodule herd is tame i.e. it is faithfully flat and a progenerator, or if it is a progenerator and the underlying ring extensions are split, then these corings are associated to entwining structures; the bimodule herd is a Galois comodule of these corings. The notion of a bicomodule coherd is introduced as a formal dualisation of the definition of a bimodule herd. Every bicomodule coherd defines a pair of (non-unital) rings. It is shown that a tame B-A bimodule herd defines a bicomodule coherd, and sufficient conditions for the derived rings to be isomorphic to A and B are discussed. The composition of bimodule herds via the tensor product is outlined. The notion of a bimodule herd is illustrated by the example of Galois co-objects of a commutative, faithfully flat Hopf algebra.