Eigenvector-free solutions to AX = B with PX = XP and X = sX constraints

The matrix equation AX = B with PX = XP and X^H = sX constraints is considered, where P is a given Hermitian involutory matrix and s = ±1. By an eigenvalue decomposition of P, we equivalently transform the constrained problem to two well-known constrained problems and represent the solutions in terms of the eigenvectors of P. Using Moore-Penrose generalized inverses of the products generated by matrices A, B and P, the involved eigenvectors can be released and eigenvector-free formulas of the general solutions are presented. Similar strategy is applied to the equations AX = B, XC = D with the same constraints.     

Approximate methods for convex minimization problems with series–parallel structure

Consider a problem of minimizing a separable, strictly convex, monotone and differentiable function on a convex polyhedron generated by a system of m linear inequalities. The problem has a series–parallel structure, with the variables divided serially into n disjoint subsets, whose elements are considered in parallel. This special structure is exploited in two algorithms proposed here for the approximate solution of the problem. The first algorithm solves at most min{m, ν − n + 1} subproblems; each subproblem has exactly one equality constraint and at most n variables. The second algorithm solves a dynamically generated sequence of subproblems; each subproblem has at most ν − n + 1 equality constraints, where ν is the total number of variables. To solve these subproblems both algorithms use the authors’ Projected Newton Bracketing method for linearly constrained convex minimization, in conjunction with the steepest descent method. We report the results of numerical experiments for both algorithms.     

Optimal vector quantization in terms of Wasserstein distance

The optimal quantizer in memory-size constrained vector quantization induces a quantization error which is equal to a Wasserstein distortion. However, for the optimal (Shannon-)entropy constrained quantization error a proof for a similar identity is still missing. Relying on principal results of the optimal mass transportation theory, we will prove that the optimal quantization error is equal to a Wasserstein distance. Since we will state the quantization problem in a very general setting, our approach includes the Rényi-α-entropy as a complexity constraint, which includes the special case of (Shannon-)entropy constrained (α=1) and memory-size constrained (α=0) quantization. Additionally, we will derive for certain distance functions codecell convexity for quantizers with a finite codebook. Using other methods, this regularity in codecell geometry has already been proved earlier by György and Linder (2002, 2003) [11] and [12].     

Three-term asymptotic expansions for the moments of the random walk with triangular distributed interference of chance

In this study, a semi-Markovian random walk with a discrete interference of chance (X(t)) is considered and under some weak assumptions the ergodicity of this process is discussed. The exact formulas for the first four moments of ergodic distribution of the process X(t) are obtained when the random variable ζ₁, which is describing a discrete interference of chance, has a triangular distribution in the interval [s, S] with center (S + s)/2. Based on these results, the asymptotic expansions with three-term are obtained for the first four moments of the ergodic distribution of X(t), as a ≡ (S − s)/2 → ∞. Furthermore, the asymptotic expansions for the variance, skewness and kurtosis of the ergodic distribution of the process X(t) are established. Finally, by using Monte Carlo experiments it is shown that the given approximating formulas provide high accuracy even for small values of parameter a.     

Multi-degree reduction of tensor product Bézier surfaces with general boundary constraints

We propose an efficient approach to the problem of multi-degree reduction of rectangular Bézier patches, with prescribed boundary control points. We observe that the solution can be given in terms of constrained bivariate dual Bernstein polynomials. The complexity of the method is O(mn₁n₂) with m ? min(m₁, m₂), where (n₁, n₂) and (m₁, m₂) is the degree of the input and output Bézier surface, respectively. If the approximation—with appropriate boundary constraints—is performed for each patch of several smoothly joined rectangular Bézier surfaces, the result is a composite surface of global C^r continuity with a prescribed r ? 0. In the detailed discussion, we restrict ourselves to r ∈ {0, 1}, which is the most important case in practical application. Some illustrative examples are given.     

Nordsieck methods with computationally verified algebraic stability

We describe the search for algebraically stable Nordsieck methods of order p = s and stage order q = p, where s is the number of stages. This search is based on the theoretical criteria for algebraic stability proposed recently by Hill, and Hewitt and Hill, for general linear methods for ordinary differential equations. These criteria, which are expressed in terms of the non-negativity of the eigenvalues of a Hermitian matrix on the unit circle, are then verified computationally for the derived Nordsieck methods of order p ? 2.     

A branch-and-bound algorithm for the singly constrained assignment problem

The singly constrained assignment problem (SCAP) is a linear assignment problem (LAP) with one extra side constraint, e.g., due to a time restriction. The SCAP is, in contrast to the LAP, difficult to solve. A branch-and-bound algorithm is presented to solve the SCAP to optimality. Lower bounds are obtained by Lagrangean relaxation. Computational results show that the algorithm is able to solve different types of SCAP instances up to size n = 1000 within short running times on a standard personal computer.     

Eigenvalues and the One-Dimensional p-Laplacian

We consider the boundary value problem (?_p(u′))′ + λF(t, u) = 0, with p > 1, t ∈ (0, 1), u(0) = u(1) = 0, and with λ > 0. The value of λ is chosen so that the boundary value problem has a positive solution. In addition, we derive an explicit interval for λ such that, for any λ in this interval, the existence of a positive solution to the boundary value problem is guaranteed. In addition, the existence of two positive solutions for λ in an appropriate interval is also discussed.     

Maximizing throughput in queueing networks with limited flexibility

We study a queueing network where customers go through several stages of processing, with the class of a customer used to indicate the stage of processing. The customers are serviced by a set of flexible servers, i.e., a server is capable of serving more than one class of customers and the sets of classes that the servers are capable of serving may overlap. We would like to choose an assignment of servers that achieves the maximal capacity of the given queueing network, where the maximal capacity is λ^∗ if the network can be stabilized for all arrival rates λ < λ^∗ and cannot possibly be stabilized for all λ > λ^∗. We examine the situation where there is a restriction on the number of servers that are able to serve a class, and reduce the maximal capacity objective to a maximum throughput allocation problem of independent interest: the total discrete capacity constrained problem (TDCCP). We prove that solving TDCCP is in general NP-complete, but we also give exact or approximation algorithms for several important special cases and discuss the implications for building limited flexibility into a system.     

Exact and approximation algorithms for the min–max k-traveling salesmen problem on a tree

Given k identical salesmen, where k ? 2 is a constant independent of the input size, the min–max k-traveling salesmen problem on a tree is to determine a set of k tours for the salesmen to serve all customers that are located on a tree-shaped network, so that each tour starts from and returns to the root of the tree with the maximum total edge weight of the tours minimized. The problem is known to be NP-hard even when k = 2. In this paper, we have developed a pseudo-polynomial time exact algorithm for this problem with any constant k ? 2, closing a question that has remained open for a decade. Along with this, we have further developed a (1 + ?)-approximation algorithm for any ? > 0.     

Matrix inverse problem and its optimal approximation problem for R-skew symmetric matrices

Let R ∈ C^n×n be a nontrivial involution, i.e., R² = I and R ≠ ±I. A matrix A ∈ C^n×n is called R-skew symmetric if RAR = −A. The least-squares solutions of the matrix inverse problem for R-skew symmetric matrices with R∗ = R are firstly derived, then the solvability conditions and the solutions of the matrix inverse problem for R-skew symmetric matrices with R∗ = R are given. The solutions of the corresponding optimal approximation problem with R∗ = R for R-skew symmetric matrices are also derived. At last an algorithm for the optimal approximation problem is given. It can be seen that we extend our previous results [G.X. Huang, F. Yin, Matrix inverse problem and its optimal approximation problem for R-symmetric matrices, Appl. Math. Comput. 189 (2007) 482-489] and the results proposed by Zhou et al. [F.Z. Zhou, L. Zhang, X.Y. Hu, Least-square solutions for inverse problem of centrosymmetric matrices, Comput. Math. Appl. 45 (2003) 1581-1589].     

Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

A new exact discrete linear reformulation of the quadratic assignment problem

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.     

An iteration regularization for a time-fractional inverse diffusion problem

In the present paper we consider a time-fractional inverse diffusion problem, where data is given at x = 1 and the solution is required in the interval 0 < x < 1. This problem is typically ill-posed: the solution (if it exists) does not depend continuously on the data. We give a new iteration regularization method to deal with this problem, and error estimates are obtained for a priori and a posteriori parameter choice rules, respectively. Furthermore, numerical implement shows the proposed method works effectively.     

On the bin packing problem with a fixed number of object weights

We consider a bin packing problem where the number of different object weights is fixed to C. We analyze a simple approximate approach and show that it leads to an asymptotically exact polynomial algorithm with absolute error 0 if C = 2, at most 1 if 1 < C ? 6, and at most 1 + ⌊(C − 1)/3⌋ if C > 6. A consequence of our analysis is a new upper bound on the gap between the optimal value of the problem at hand and the round-up of the optimal value of the linear relaxation of its Gilmore–Gomory formulation.     

Robust optimization approximation for joint chance constrained optimization problem

Chance constraint is widely used for modeling solution reliability in optimization problems with uncertainty. Due to the difficulties in checking the feasibility of the probabilistic constraint and the non-convexity of the feasible region, chance constrained problems are generally solved through approximations. Joint chance constrained problem enforces that several constraints are satisfied simultaneously and it is more complicated than individual chance constrained problem. This work investigates the tractable robust optimization approximation framework for solving the joint chance constrained problem. Various robust counterpart optimization formulations are derived based on different types of uncertainty set. To improve the quality of robust optimization approximation, a two-layer algorithm is proposed. The inner layer optimizes over the size of the uncertainty set, and the outer layer optimizes over the parameter t which is used for the indicator function upper bounding. Numerical studies demonstrate that the proposed method can lead to solutions close to the true solution of a joint chance constrained problem.     

A bifurcation theorem for the p-logistic equation

We consider a p-logistic equation with an equidiffusive reaction. Using variational methods and truncation techniques, we show that there is a critical parameter value λ^∗ > 0 such that for λ > λ^∗ the problem has a unique positive smooth solution, and for λ ∈ (0, λ^∗] the problem has no positive solution.     

A model for heuristic coordination of real life distribution inventory systems with lumpy demand

This paper presents an approximation model for optimizing reorder points in one-warehouse N-retailer inventory systems subject to highly variable lumpy demand. The motivation for this work stems from close cooperation with a supply chain management software company, Syncron International, and one of their customers, a global spare parts provider. The model heuristically coordinates the inventory system using a near optimal induced backorder cost at the central warehouse. This induced backorder cost captures the impact that a reorder point decision at the warehouse has on the retailers’ costs, and decomposes the multi-echelon problem into solving N + 1 single-echelon problems. The decomposition framework renders a flexible model that is computationally and conceptually simple enough to be implemented in practice.     

A polynomial algorithm for some preemptive multiprocessor task scheduling problems

In this paper we consider a problem of preemptive scheduling of multiprocessor tasks on dedicated processors in order to minimize the sum of completion times. Using a standard notation, our problem can be denoted as P ∣ fix_j, pmtn ∣ ∑C_j. We give a polynomial-time algorithm to solve P ∣ fix_j, G = {P₄, dart}-free, pmtn ∣ ∑C_j problem. This result generalizes the following problems: P2 ∣ fix_j, pmtn ∣ ∑C_j, P ∣ ∣fix_j∣ ∈ {1, m}, pmtn ∣ ∑C_j and P4 ∣ fix_j = 2, pmtn ∣ ∑C_j.     

An analytical comparison of the LP relaxations of integer models for the k-club problem

Given an undirected graph G = (V, E), a k-club is a subset of nodes that induces a subgraph with diameter at most k. The k-club problem is to find a maximum cardinality k-club. In this study, we use a linear programming relaxation standpoint to compare integer formulations for the k-club problem. The comparisons involve formulations known from the literature and new formulations, built in different variable spaces. For the case k = 3, we propose two enhanced compact formulations. From the LP relaxation standpoint these formulations dominate all other compact formulations in the literature and are equivalent to a formulation with a non-polynomial number of constraints. Also for k = 3, we compare the relative strength of LP relaxations for all formulations examined in the study (new and known from the literature). Based on insights obtained from the comparative study, we devise a strengthened version of a recursive compact formulation in the literature for the k-club problem (k > 1) and show how to modify one of the new formulations for the case k = 3 in order to accommodate additional constraints recently proposed in the literature.