The path partition problem and related problems in bipartite graphs

We prove that it is NP-complete to decide whether a bipartite graph of maximum degree three on nk vertices can be partitioned into n paths of length k. Finally, we propose some approximation and inapproximation results for several related problems.     

A note on the generalized min-sum set cover problem

In this paper, we consider the generalized min-sum set cover problem, introduced by Azar, Gamzu, and Yin (STOC 2009). Bansal, Gupta, and Krishnaswamy (SODA 2010) give a 485-approximation algorithm for the problem. We are able to alter their algorithm and analysis to obtain a 28-approximation algorithm, improving the performance guarantee by an order of magnitude. We use concepts from α-point scheduling to obtain our improvements.     

Matching polynomials for chains of cycles

Došli? and Måløy (2010) [2] obtained the extremal 6-cactus chains with respect to the number of matchings and of independent sets. Motivated by the prior paper, in this paper we give recurrences for matching polynomials of ortho-chains and meta-chains, and show that they are the h-cactus chains with the most matchings.     

On the spectral characterization of some unicyclic graphs

Let H(n;q,n₁,n₂) be a graph with n vertices containing a cycle C_q and two hanging paths P_n1 and P_n2 attached at the same vertex of the cycle. In this paper, we prove that except for the A-cospectral graphs H(12;6,1,5) and H(12;8,2,2), no two non-isomorphic graphs of the form H(n;q,n₁,n₂) are A-cospectral. It is proved that all graphs H(n;q,n₁,n₂) are determined by their L-spectra. And all graphs H(n;q,n₁,n₂) are proved to be determined by their Q-spectra, except for graphs with a being a positive even number and with b≥4 being an even number. Moreover, the Q-cospectral graphs with these two exceptions are given.     

On the stability index for weighted composition operators

Let ?>0. A continuous linear operator T:C(X)?C(Y) is said to ?-preserve disjointness if ‖(Tf)(Tg)‖_∞≤?, whenever f,g∈C(X) satisfy ‖f‖_∞=‖g‖_∞=1 and fg≡0. In this paper we continue our study of the minimal interval where the possible maximal distance from a norm one operator which ?-preserves disjointness to the set of weighted composition maps may lie. We provide sharp bounds for both the finite and the infinite case, which turn out to be completely different.     

Duality theory and propagation rules for higher order nets

Higher order nets and sequences are used in quasi-Monte Carlo rules for the approximation of high dimensional integrals over the unit cube. Hence one wants to have higher order nets and sequences of high quality.In this paper we introduce a duality theory for higher order nets whose construction is not necessarily based on linear algebra over finite fields. We use this duality theory to prove propagation rules for such nets. This way we can obtain new higher order nets (sometimes with improved quality) from existing ones. We also extend our approach to the construction of higher order sequences.     

Archimedean copulas in finite and infinite dimensions—with application to ruin problems

In this paper we discuss the link between Archimedean copulas and L₁ Dirichlet distributions for both finite and infinite dimensions. With motivation from the recent papers Weng et al. (2009) and Albrecher et al. (2011) we apply our results to certain ruin problems.     

On the demand pooling anomaly in inventory theory

The demand pooling anomaly of inventory theory of type F amounts to a kind of restricted order relation between the individual demands (assumed to be independent) and their average. In this paper, we present some sufficient conditions for the type F anomaly not to occur for two i.i.d. demands; furthermore we provide an asymptotic result showing whether this anomaly occurs for large n for a class of distributions containing all distributions with finite mean.     

Zero location and asymptotic behavior for extremal polynomials with non-diagonal Sobolev norms

In this paper we are going to study the zero location and asymptotic behavior of extremal polynomials with respect to a non-diagonal Sobolev norm in the worst case, i.e., when the quadratic form is allowed to degenerate. The orthogonal polynomials with respect to this Sobolev norm are a particular case of those extremal polynomials. The multiplication operator by the independent variable is the main tool in order to obtain our results.     

Modelling and management of longevity risk: Approximations to survivor functions and dynamic hedging

This paper looks at the development of dynamic hedging strategies for typical pension plan liabilities using longevity-linked hedging instruments. Progress in this area has been hindered by the lack of closed-form formulae for the valuation of mortality-linked liabilities and assets, and the consequent requirement for simulations within simulations. We propose the use of the probit function along with a Taylor expansion to approximate longevity-contingent values. This makes it possible to develop and implement computationally efficient, discrete-time delta hedging strategies using q-forwards as hedging instruments.The methods are tested using the model proposed by Cairns et al. (2006a) (CBD). We find that the probit approximations are generally very accurate, and that the discrete-time hedging strategy is very effective at reducing risk.     

Convergence of SSOR methods for linear complementarity problems

In this paper, by applying the SSOR splitting, we propose two new iterative methods for solving the linear complementarity problem LCP (M,q). Convergence results for these two methods are presented when M is an H-matrix (and also an M-matrix). Finally, two numerical examples are given to show the efficiency of the presented methods.     

Linear-time certifying algorithms for near-graphical sequences

A sequence 〈d₁,d₂,…,d_n〉 of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph G on n vertices whose ith vertex has degree d_i, for 1≤i≤n. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.If H=(V,E) is a graph and g and f are integer-valued functions on the vertex set V, then a (g,f)-factor of H is a subgraph G=(V,F) of H whose degree at each vertex v∈V lies in the interval [g(v),f(v)]. Thus, a (0,1)-factor is just a matching of H and a (1, 1)-factor is a perfect matching of H. If H is complete then a (g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals 〈[g(v₁),f(v₁)],[g(v₂),f(v₂)],…,[g(v_n),f(v_n)]〉.Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient (g,f)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient (g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös-Gallai characterization of (f,f)-factors in complete graphs) at no additional cost.     

Tensor products of Sobolev–Besov spaces and applications to approximation from the hyperbolic cross

Besov as well as Sobolev spaces of dominating mixed smoothness are shown to be tensor products of Besov and Sobolev spaces defined on R. Using this we derive several useful characterizations from the one-dimensional case to the d-dimensional situation. Finally, consequences for hyperbolic cross approximations, in particular for tensor product splines, are discussed.     

Approximate duality for vector quasi-equilibrium problems and applications

In this paper, we introduce new versions of ?-dual problems of a vector quasi-equilibrium problem with set-valued maps, and we give an ?-duality result between approximate solutions of the primal and dual problems. As the first application of the main result, we obtain an ?-duality for a vector quasi-equilibrium problem whose ?-solutions are understood in the sense of proper efficiency. The second application is devoted to an?-duality for a vector optimization problem with set-valued maps.     

Sensitivity of risk measures with respect to the normal approximation of total claim distributions

A simple and commonly used method to approximate the total claim distribution of a (possibly weakly dependent) insurance collective is the normal approximation. In this article, we investigate the error made when the normal approximation is plugged in a fairly general distribution-invariant risk measure. We focus on the rate of convergence of the error relative to the number of clients, we specify the relative error’s asymptotic distribution, and we illustrate our results by means of a numerical example. Regarding the risk measure, we take into account distortion risk measures as well as distribution-invariant coherent risk measures.     

Set systems without a 3-simplex

A 3-simplex is a collection of four sets A₁,…,A₄ with empty intersection such that any three of them have nonempty intersection. We show that the maximum size of a set system on n elements without a 3-simplex is for all n≥1, with equality only achieved by the family of sets containing a given element or of size at most 2. This extends a result of Keevash and Mubayi, who showed the conclusion for n sufficiently large.     

Colorings of k-balanced matrices and integer decomposition property of related polyhedra

We show that a class of polyhedra, arising from certain 0,1 matrices introduced by Truemper and Chandrasekaran, has the integer decomposition property. This is accomplished by proving certain coloring properties of these matrices.     

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a treet-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a treet-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t≥4 and is linearly solvable for t≤2. The case t=3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a−b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners. This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed.