An FPTAS for minimizing the product of two non-negative linear cost functions

We consider a quadratic programming (QP) problem (Π) of the form min x ^T C x subject to Ax ≥ b, x ≥ 0 where \({C\in {\mathbb R}^{n \times n}_+, {\rm rank}(C)=1}\) and \({A\in {\mathbb R}^{m \times n}, b\in {\mathbb R}^m}\) . We present an fully polynomial time approximation scheme (FPTAS) for this problem by reformulating the QP (Π) as a parameterized LP and “rounding” the optimal solution. Furthermore, our algorithm returns an extreme point solution of the polytope. Therefore, our results apply directly to 0–1 problems for which the convex hull of feasible integer solutions is known such as spanning tree, matchings and sub-modular flows. They also apply to problems for which the convex hull of the dominant of the feasible integer solutions is known such as s, t-shortest paths and s, t-min-cuts. For the above discrete problems, the quadratic program Π models the problem of obtaining an integer solution that minimizes the product of two linear non-negative cost functions.     

A remark on the ring of algebraic integers in $$\mathbb{Q}(\sqrt { - d} )$$

It is well-known that the rings O_d of algebraic integers in \(\mathbb{Q}(\sqrt { - d} )\) for d = 19, 43, 67, and 163 are principal ideal domains but not Euclidean. In this article we shall provide a method, based on a result of P. M. Cohn, to construct explicitly pairs (b, a) of integers in O_d for d = 19, 43, 67, and 163 such that, in O_d, there exists no terminating division chain of finite length starting from the pairs (b, a). That is, a greatest common divisor of the pairs (b, a) exists in O_d but it can not be obtained by applying a terminating division chain of finite length starting from (b, a). Furthermore, for squarefree positive integer d ? {1, 2, 3, 7, 11, 19, 43, 67, 163}, we shall also construct pairs (b, a) of integers in O_d which generate O_d but have no terminating division chain of finite length. It is of interest to note that our construction provides a short alternative proof of a theorem of Cohn which is related to the concept of GE₂-rings.     

Integer Programming with Bounded Variables via Canonical Separation

This paper presents a new algorithm for integer programming with bounded variables which is efficient when m < n and when the upper bounds on the variables are small. The main idea is the application of the Balas and Jeroslow canonical hyperplanes and the systematic search of integer points over certain faces of the feasible region. During each iteration the integer points on a certain face are examined, and then this whole face is discarded from the feasible region of a linear programming problem. After a bounded number of iterations, the optimal integer solution is found, if one exists.     

Koszul property of a class of graded algebras with nonpure resolutions

Given any integers a, b, c, and d with a > 1, c ≥ 0, b ≥ a + c, and d ≥ b + c, the notion of (a, b, c, d)-Koszul algebra is introduced, which is another class of standard graded algebras with “nonpure” resolutions, and includes many Artin-Schelter regular algebras of low global dimension as specific examples. Some basic properties of (a, b, c, d)-Koszul algebras/modules are given, and several criteria for a standard graded algebra to be (a, b, c, d)-Koszul are provided.     

Basics of the Quasiconformal Analysis of a Two-Index Scale of Spatial Mappings

We define a scale of mappings that depends on two real parameters p and q, n?1 ≤ q ≤ p < ∞ and a weight function θ. In the case of q = p = n, θ ≡ 1, we obtain the well-known mappings with bounded distortion. Mappings of a two-index scale inherit many properties of mappings with bounded distortion. They are used for solving a few problems of global analysis and applied problems.     

Cauchy problem for the Korteweg-de Vries equation in the case of a nonsmooth unbounded initial function

In the strip П = (?1, 0) × ?, we establish the existence of solutions of the Cauchy problem for the Korteweg-de Vries equation u _t + u _xxx + uu _x = 0 with initial condition either 1) u(?1, x) = ?xθ(x), or 2) u(?1, x) = ?xθ(?x), where θ is the Heaviside function. The solutions constructed in this paper are infinitely smooth for t ∈ (?1, 0) and rapidly decreasing as x → +∞. For the case of the first initial condition, we also establish uniqueness in a certain class. Similar special solutions of the KdV equation arise in the study of the asymptotic behavior with respect to small dispersion of the solutions of certain model problems in a neighborhood of lines of weak discontinuity.     

Generating subtour elimination constraints for the TSP from pure integer solutions

The traveling salesman problem (TSP) is one of the most prominent combinatorial optimization problems. Given a complete graph \(G = (V, E)\) and non-negative distances d for every edge, the TSP asks for a shortest tour through all vertices with respect to the distances d. The method of choice for solving the TSP to optimality is a branch and cut approach. Usually the integrality constraints are relaxed first and all separation processes to identify violated inequalities are done on fractional solutions. In our approach we try to exploit the impressive performance of current ILP-solvers and work only with integer solutions without ever interfering with fractional solutions. We stick to a very simple ILP-model and relax the subtour elimination constraints only. The resulting problem is solved to integer optimality, violated constraints (which are trivial to find) are added and the process is repeated until a feasible solution is found. In order to speed up the algorithm we pursue several attempts to find as many relevant subtours as possible. These attempts are based on the clustering of vertices with additional insights gained from empirical observations and random graph theory. Computational results are performed on test instances taken from the TSPLIB95 and on random Euclidean graphs.     

Filter factors of truncated tls regularization with multiple observations

The total least squares (TLS) and truncated TLS (T-TLS) methods are widely known linear data fitting approaches, often used also in the context of very ill-conditioned, rank-deficient, or ill-posed problems. Regularization properties of T-TLS applied to linear approximation problems Ax ≈ b were analyzed by Fierro, Golub, Hansen, and O’Leary (1997) through the so-called filter factors allowing to represent the solution in terms of a filtered pseudoinverse of A applied to b. This paper focuses on the situation when multiple observations b ₁,..., b _d are available, i.e., the T-TLS method is applied to the problem AX ≈ B, where B = [b ₁,..., b _d ] is a matrix. It is proved that the filtering representation of the T-TLS solution can be generalized to this case. The corresponding filter factors are explicitly derived.     

On Lehmer’s problem and Dedekind sums

Let p be an odd prime and c a fixed integer with (c, p) = 1. For each integer a with 1 ≤ a ≤ p ? 1, it is clear that there exists one and only one b with 0 ? b ? p ? 1 such that ab ≡ c (mod p). Let N(c, p) denote the number of all solutions of the congruence equation ab ≡ c (mod p) for 1 ? a, b ? p?1 in which a and \(\overline b \) are of opposite parity, where \(\overline b \) is defined by the congruence equation b\(\overline b \) ≡ 1 (mod p). The main purpose of this paper is to use the properties of Dedekind sums and the mean value theorem for Dirichlet L-functions to study the hybrid mean value problem involving N(c, p)?½φ(p) and the Dedekind sums S(c, p), and to establish a sharp asymptotic formula for it.     

On the global attractivity of two nonlinear difference equations

The main objective of this paper is to study some qualitative behavior of the solutions of the two difference equations

$ {x_{n + 1}} = {{{a{x_n} - b{x_{n - k}}}} \left/ {{\left( {c{x_n} - d{x_{n - k}}} \right)}} \right.}\quad n = 0,\,1,\,2, \ldots, $

and

$ {x_{n + 1}} = {{{a{x_{n - k}} + b{x_n}}} \left/ {{\left( {c{x_n} - d{x_{n - k}}} \right)}} \right.}\quad n = 0,\,1,\,2, \ldots, $

where the initial conditions x???k, ?, x???1, x0 are arbitrary positive real numbers and the coefficients a, b, c, and d are positive constants, while k is a positive integer number.

     

On the total-variation convergence of regularizing algorithms for ill-posed problems

It is well known that ill-posed problems in the space V[a, b] of functions of bounded variation cannot generally be regularized and the approximate solutions do not converge to the exact one with respect to the variation. However, this convergence can be achieved on separable subspaces of V[a, b]. It is shown that the Sobolev spaces W ₁ ^m [a, b], m ∈ ? can be used as such subspaces. The classes of regularizing functionals are indicated that guarantee that the approximate solutions produced by the Tikhonov variational scheme for ill-posed problems converge with respect to the norm of W ₁ ^m [a, b]. In turn, this ensures the convergence of the approximate solutions with respect to the variation and the higher order total variations.     

Drift perturbation of subordinate Brownian motions with Gaussian component

Let d ≥ 1 and Z be a subordinate Brownian motion on R~d with infinitesimal generator ? + ψ(?),where ψ is the Laplace exponent of a one-dimensional non-decreasing L′evy process(called subordinator). We establish the existence and uniqueness of fundamental solution(also called heat kernel) pb(t, x, y) for non-local operator L~b= ? + ψ(?) + b ?, where Rb is an Rd-valued function in Kato class K_(d,1). We show that p~b(t, x, y)is jointly continuous and derive its sharp two-sided estimates. The kernel pb(t, x, y) determines a conservative Feller process X. We further show that the law of X is the unique solution of the martingale problem for(L~b, C_c~∞(R~d)) and X is a weak solution of Xt = X0+ Zt + integral from n=0 to t(b(Xs)ds, t ≥ 0).Moreover, we prove that the above stochastic differential equation has a unique weak solution.     

Nonsingularity,positive definiteness,and positive invertibility under fixed-point data rounding

For a real square matrix A and an integer d ? 0, let A _(d) denote the matrix formed from A by rounding off all its coefficients to d decimal places. The main problem handled in this paper is the following: assuming that A _(d) has some property, under what additional condition(s) can we be sure that the original matrix A possesses the same property? Three properties are investigated: nonsingularity, positive definiteness, and positive invertibility. In all three cases it is shown that there exists a real number α(d), computed solely from A _(d) (not from A), such that the following alternative holdsif d > α(d), then nonsingularity (positive definiteness, positive invertibility) of A _(d) implies the same property for A if d < α(d) and A _(d) is nonsingular (positive definite, positive invertible), then there exists a matrix A′ with A′_(d) = A _(d) which does not have the respective property.For nonsingularity and positive definiteness the formula for α(d) is the same and involves computation of the NP-hard norm ‖ · ‖_∞,1; for positive invertibility α(d) is given by an easily computable formula.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

Higher Auslander Correspondence for Dualizing <Emphasis Type="Italic">R</Emphasis>-Varieties

Let R be a commutative artinian ring. We extend higher Auslander correspondence from Artin R-algebras of finite representation type to dualizing R-varieties. More precisely, for a positive integer d, we show that a dualizing R-variety is d-abelian if and only if it is a d-Auslander dualizing R-variety if and only if it is equivalent to a d-cluster-tilting subcategory of the category of finitely presented modules over a dualizing R-variety.     

A branch-and-cut algorithm for the capacitated open vehicle routing problem

In open vehicle routing problems, the vehicles are not required to return to the depot after completing service. In this paper, we present the first exact optimization algorithm for the open version of the well-known capacitated vehicle routing problem (CVRP). The algorithm is based on branch-and-cut. We show that, even though the open CVRP initially looks like a minor variation of the standard CVRP, the integer programming formulation and cutting planes need to be modified in subtle ways. Computational results are given for several standard test instances, which enables us for the first time to assess the quality of existing heuristic methods, and to compare the relative difficulty of open and closed versions of the same problem.     

Ergodic theorems with arithmetical weights

We prove that the divisor function d(n) counting the number of divisors of the integer n is a good weighting function for the pointwise ergodic theorem. For any measurable dynamical system (X, A, ν, τ) and any f ∈ L ^p (ν), p > 1, the limit

$$\mathop {\lim }\limits_{n \to \infty } \frac{1}{{\Sigma _{k = 1}^nd\left( k \right)}}\sum\limits_{k = 1}^n {d\left( k \right)f\left( {{\tau ^k}x} \right)} $$

exists ν-almost everywhere. The proof is based on Bourgain’s method, namely the circle method based on the shift model. Using more elementary ideas we also obtain similar results for other arithmetical functions, like the θ(n) function counting the number of squarefree divisors of n and the generalized Euler totient function J _s (n) = Σ _d|n d ^s μ(n/d), s > 0.

     

On an Extremal Problem for Poset Dimension

Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n ^1/2. We improve the best known upper bound and show f(n) = O (n ^2/3). For higher dimensions, we show \(f_{d}(n)=\O \left (n^{\frac {d}{d + 1}}\right )\), where f _d (n) is the largest integer such that every poset on n elements has a d-dimensional subposet on f _d (n) elements.     

On the gonality sequence of smooth curves

Let C be a smooth curve of genus g. For each positive integer r the r-gonality d _r (C) of C is the minimal integer t such that there is \({L\in {\rm Pic}^t(C)}\) with h ⁰(C, L) = r + 1. Here we use nodal plane curves to construct several smooth curves C with d ₂(C)/2 < d ₃(C)/3, i.e., for which a slope inequality fails.