Some minimax problems in lexicographic order

In this paper, minimax theorems and saddle points for a class of vector-valued mappings f(x, y) = u(x)+β(x)v(y) are first investigated in the sense of lexicographic order, where u, v are two general vector-valued mappings and β is a non-negative real-valued function. Then, by applying the existence theorem of lexicographic saddle point, we investigate a lexicographic equilibrium problem and establish an equivalent relationship between the lexicographic saddle point theorem and existence theorem of a lexicographic equilibrium problem for vector-valued mappings.     

Lexicographic effect algebras

We investigate a class of effect algebras that can be represented in the form \({\Gamma (H \overrightarrow{\times} G}\), (u, 0)), where \({H \overrightarrow{\times} G}\) means the lexicographic product of an Abelian unital po-group (H, u) and an Abelian directed po-group G. We study conditions when an effect algebra is of this form. Fixing a unital po-group (H, u), the category of strongly (H, u)-perfect effect algebras is introduced and it is shown that it is categorically equivalent to the category of directed po-groups with interpolation. We prove some representation theorems of lexicographic effect algebras, including a subdirect product representation by antilattice lexicographic effect algebras.     

A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem

We present a 0.5-approximation algorithm for the Multiple Knapsack Problem (MKP). The algorithm uses the ordering of knapsacks according to the nondecreasing of size and the two orderings of items: in nonincreasing utility order and in nonincreasing order of the utility/size ratio. These orderings create two lexicographic orderings on A × B (here A is the set of knapsacks and B is the set of indivisible items). Based on each of these lexicographic orderings, the algorithm creates a feasible solution to the MKP by looking through the pairs (a, b) ∈ A × B in the corresponding order and placing item b into knapsack a if this item is not placed yet and there is enough free space in the knapsack. The algorithm chooses the best of the two obtained solutions. This algorithm is 0.5-approximate and has runtime O(mn) (without sorting), where mand n are the sizes of A and B correspondingly.     

On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets

Given n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d.We show that the extremal tree is unique for all even n but uniqueness may fail for odd n; moreover, for d = 3 and every odd n ≥ 7, there are exactly ?(n ? 3)/4? + 1 extremal trees. In the paper, the problem of searching for extremal (n, d)-trees is also considered for the 2-caterpillars; i.e., the trees in which every vertex lies at distance at most 2 from some simple path. Given n and d ∈ {3, 4}, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.     

Solving Equations of Free Vibration for a Cylindrical Shell Rotating on Rollers by the Fourier Method

The small free vibrations of an infinite circular cylindrical shell rotating about its axis at a constant angular velocity are considered. The shell is supported on n absolutely rigid cylindrical rollers equispaced on its circle. The roller-supported shell is a model of an ore benefication centrifugal concentrator with a floating bed. The set of linear differential equations of vibrations is sought in the form of a truncated Fourier series containing N terms along the circumferential coordinate. A system of 2N–n linear homogeneous algebraic equations with 2N–n unknowns is derived for the approximate estimation of vibration frequencies and mode shapes. The frequencies ω _k , k = 1, 2, …, 2N–n, are positive roots of the (2N–n)th-order algebraic equation D(ω²) = 0, where D is the determinant of this set. It is shown that the system of 2N–n equations is equivalent to several independent systems with a smaller number of unknowns. As a consequence, the (2N–n)th-order determinant D can be written as a product of lower-order determinants. In particular, the frequencies at N = n are the roots of algebraic equations of an order is lower than 2 and can be found in an explicit form. Some frequency estimation algorithms have been developed for the case of N > n. When N increases, the number of found frequencies also grows, and the frequencies determined at N = n are refined. However, in most cases, the vibration frequencies can not be found for N > n in an explicit form.     

A Note on Average-Case Sorting

This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize the expected number of comparisons. We generalize Fredman’s algorithm which is a variant of insertion sort and provide a basically tight upper bound: If μ is a distribution on permutations on n elements, then one may sort inputs from μ with expected number of comparisons that is at most H(μ) + 2n, where H is the entropy function. The algorithm uses less comparisons for more probable inputs: For every permutation π, the algorithm sorts π by using at most \(\log _{2}(\frac {1}{\Pr _{\mu }(\pi )})+2n\) comparisons. A lower bound on the expected number of comparisons of H(μ) always holds, and a linear dependence on n is also required.     

Radar placement along banks of river

In this paper, we consider the Radar Placement and Power Assignment problem (RPPA) along a river. In this problem, a set of crucial points in the river are required to be monitored by a set of radars which are placed along the two banks. The goal is to choose the locations for the radars and assign powers to them such that all the crucial points are monitored and the total power is minimized. If each crucial point is required to be monitored by at least k radars, the problem is a k-Coverage RPPA problem (k-CRPPA). Under the assumption that the river is sufficiently smooth, one may focus on the RPPA problem along a strip (RPPAS). In this paper, we present an O(n ⁹) dynamic programming algorithm for the RPPAS, where n is the number of crucial points to be monitored. In the special case where radars are placed only along the upper bank, we present an O(kn ⁵) dynamic programming algorithm for the k-CRPPAS. For the special case that the power is linearly dependent on the radius, we present an O(n log n)-time \({2\sqrt 2}\)-approximation algorithm for the RPPAS.     

Variational Analysis on Local Sharp Minima via Exact Penalization

In this paper we study local sharp minima of the nonlinear programming problem via exact penalization. Utilizing generalized differentiation tools in variational analysis such as subderivatives and regular subdifferentials, we obtain some primal and dual characterizations for a penalty function associated with the nonlinear programming problem to have a local sharp minimum. These general results are then applied to the ? _p penalty function with 0 ≤ p ≤ 1. In particular, we present primal and dual equivalent conditions in terms of the original data of the nonlinear programming problem, which guarantee that the ? _p penalty function has a local sharp minimum with a finite penalty parameter in the case of \(p\in (\frac {1}{2}, 1]\) and \(p=\frac {1}{2}\) respectively. By assuming the Guignard constraint qualification (resp. the generalized Guignard constraint qualification), we also show that a local sharp minimum of the nonlinear programming problem can be an exact local sharp minimum of the ? _p penalty function with p ∈ [0, 1] (resp. \(p\in [0, \frac {1}{2}]\)). Finally, we give some formulas for calculating the smallest penalty parameter for a penalty function to have a local sharp minimum.     

Parametric Integer Programming Analysis: A Contraction Approach

An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.The approach consists primarily of solving the most relaxed problem (θ = 1) using cutting planes and then contracting the region of feasible integer solutions in such a manner that the current optimal integer solution is eliminated.The algorithm was applied to 1800 integer linear programming problems with reasonable success. Integer programming problems which have proved to be unsolvable using cutting planes have been solved by expanding the region of feasible integer solutions (θ = 1) and then contracting to the original region.     

Sustainable workforce scheduling in construction program management

The multimode resource-constrained project scheduling problem (MRCPSP) deals with the scheduling of a set of projects with alternative requirements of renewable and non-renewable resources. Solutions to the MRCPSP usually consider objectives in terms of cost and time. However, social objectives related with the workforce may impact the performance of projects and affect program sustainability goals. To account for this new social input, this paper extends the MRCPSP and proposes a new multiobjective mixed-integer programming model. The proposed solution method uses an a priori lexicographic ordering of the objectives, followed by an ?-constraints approach. The model is illustrated with a case study of a construction program.     

Elementary Graphs with Respect to <Emphasis Type="Italic">f</Emphasis>-Parity Factors

This note concerns the f-parity subgraph problem, i.e., we are given an undirected graph G and a positive integer value function \({f : V(G) \rightarrow \mathbb{N}}\), and our goal is to find a spanning subgraph F of G with deg _F ≤ f and minimizing the number of vertices x with \({\deg_F(x) \not\equiv f(x) \, {\rm mod} \, {2}}\) . First we prove a Gallai–Edmonds type structure theorem and some other known results on the f-parity subgraph problem, using an easy reduction to the matching problem. Then we use this reduction to investigate barriers and elementary graphs with respect to f-parity factors, where an elementary graph is a graph such that the union of f-parity factors form a connected spanning subgraph.     

Fixed Points of Set Functors: How Many Iterations are Needed?

The initial algebra for a set functor can be constructed iteratively via a well-known transfinite chain, which converges after a regular infinite cardinal number of steps or at most three steps. We extend this result to the analogous construction of relatively initial algebras. For the dual construction of the terminal coalgebra Worrell proved that if a set functor is α-accessible, then convergence takes at most α + α steps. But until now an example demonstrating that fewer steps may be insufficient was missing. We prove that the functor of all α-small filters is such an example. We further prove that for β ≤ α the functor of all α-small β-generated filters requires precisely α + β steps and that a certain modified power-set functor requires precisely α steps. We also present an example showing that whether a terminal coalgebra exists at all does not depend solely on the object mapping of the given set functor. (This contrasts with the fact that existence of an initial algebra is equivalent to existence of a mere fixed point.)     

On the hyperbolicity of flows

Let X be a C~1 vector field on a compact boundaryless Riemannian manifold M(dim M≥2),and A a compact invariant set of X.Suppose that A has a hyperbolic splitting,i.e.,T∧M = E~sX E~u with E~s uniformly contracting and E~u uniformly expanding.We prove that if,in addition,A is chain transitive,then the hyperbolic splitting is continuous,i.e.,A is a hyperbolic set.In general,when A is not necessarily chain transitive,the chain recurrent part is a hyperbolic set.Furthermore,we show that if the whole manifold M admits a hyperbolic splitting,then X has no singularity,and the flow is Anosov.     

All Colors Shortest Path problem on trees

Given an edge weighted tree T(V, E), rooted at a designated base vertex \(r \in V\), and a color from a set of colors \(C=\{1,\ldots ,k\}\) assigned to every vertex \(v \in V\), All Colors Shortest Path problem on trees (ACSP-t) seeks the shortest, possibly non-simple, path starting from r in T such that at least one node from every distinct color in C is visited. We show that ACSP-t is NP-hard, and also prove that it does not have a constant factor approximation. We give an integer linear programming formulation of ACSP-t. Based on a linear programming relaxation of this formulation, an iterative rounding heuristic is proposed. The paper also explores genetic algorithm and tabu search to develop alternative heuristic solutions for ACSP-t. The performance of all the proposed heuristics are evaluated experimentally for a wide range of trees that are generated parametrically.     

Discrete Universality in the Selberg Class

The Selberg class S consists of functions L(s) that are defined by Dirichlet series and satisfy four axioms (Ramanujan conjecture, analytic continuation, functional equation, and Euler product). It has been known that functions in S that satisfy the mean value condition on primes are universal in the sense of Voronin, i.e., every function in a sufficiently wide class of analytic functions can be approximated by the shifts L(s + iτ ), τ ∈ R. In this paper we show that every function in the same class of analytic functions can be approximated by the discrete shifts L(s + ikh), k = 0, 1,..., where h > 0 is an arbitrary fixed number.     

An integro-local theorem applicable on the whole half-axis to the sums of random variables with regularly varying distributions

We obtain an integro-local limit theorem for the sum S(n) = ξ(1)+?+ξ(n) of independent identically distributed random variables with distribution whose right tail varies regularly; i.e., it has the form P(ξ≥t) = t ^?β L(t) with β > 2 and some slowly varying function L(t). The theorem describes the asymptotic behavior on the whole positive half-axis of the probabilities P(S(n) ∈ [x, x + Δ)) as x → ∞ for a fixed Δ > 0; i.e., in the domain where the normal approximation applies, in the domain where S(n) is approximated by the distribution of its maximum term, as well as at the “junction” of these two domains.     

A comparison of several enumerative algorithms for Sudoku

Sudoku is a puzzle played of an n × n grid Open image in new window where n is the square of a positive integer m. The most common size is n=9. The grid is partitioned into n subgrids of size m × m. The player must place exactly one number from the set N={1, …, n} in each row and each column of Open image in new window as well as in each subgrid. A grid is provided with some numbers already in place, called givens. In this paper, some relationships between Sudoku and several operations research problems are presented. We model the problem by means of two mathematical programming formulations. The first one consists of an integer linear programming model, while the second one is a tighter non-linear integer programming formulation. We then describe several enumerative algorithms to solve the puzzle and compare their relative efficiencies. Two basic backtracking algorithms are first described for the general Sudoku. We then solve both formulations by means of constraint programming. Computational experiments are performed to compare the efficiency and effectiveness of the proposed algorithms. Our implementation of a backtracking algorithm can solve most benchmark instances of size 9 within 0.02?s, while no such instance was solved within that time by any other method. Our implementation is also much faster than an existing alternative algorithm.     

Boundedness,univalence and quasiconformal extension of Robertson functions

This article contains several results for λ-Robertson functions, i.e., analytic functions f defined on the unit disk ? satisfying f(0) = f′(0) ? 1 = 0 and Re e ^?iλ {1 + zf″(z)/f′(z)} > 0 in ? where λ ∈ (?π/2, π/2). We will discuss about conditions for boundedness and quasiconformal extension of Robertson functions. In the last section we provide another proof of univalence for Robertson functions by using the theory of Löwner chains.     

A characterization of the normal distribution using stationary max-stable processes

Consider a max-stable process of the form \(\eta (t) = \max _{i\in \mathbb {N}} U_{i} \mathrm {e}^{\langle X_{i}, t\rangle - \kappa (t)}\), \(t\in \mathbb {R}^{d}\), where \(\{U_{i}, i\in \mathbb {N}\}\) are points of the Poisson process with intensity u ^?2du on (0,∞), X _i , \(i\in \mathbb {N}\), are independent copies of a random d-variate vector X (that are independent of the Poisson process), and \(\kappa :\mathbb {R}^{d} \to \mathbb {R}\) is a function. We show that the process η is stationary if and only if X has multivariate normal distribution and κ(t)?κ(0) is the cumulant generating function of X. In this case, η is a max-stable process introduced by R. L. Smith.     

Superization of homogeneous spin manifolds and geometry of homogeneous supermanifolds

Let M ₀=G ₀/H be a (pseudo)-Riemannian homogeneous spin manifold, with reductive decomposition \(\mathfrak {g}_{0}=\mathfrak {h}+\mathfrak {m}\) and let S(M ₀) be the spin bundle defined by the spin representation \(\tilde{ \operatorname {Ad}}:H\rightarrow \mathrm {GL}_{\mathbb {R}}(S)\) of the stabilizer H. This article studies the superizations of M ₀, i.e. its extensions to a homogeneous supermanifold M=G/H whose sheaf of superfunctions is isomorphic to the sheaf of sections of Λ(S ^*(M ₀)). Here G is the Lie supergroup associated with a certain extension of the Lie algebra of symmetry \(\mathfrak {g}_{0}\) to an algebra of supersymmetry \(\mathfrak {g}=\mathfrak {g}_{\overline {0}}+\mathfrak {g}_{\overline {1}}=\mathfrak {g}_{0}+S\) via the Kostant-Koszul construction. Each algebra of supersymmetry naturally determines a flat connection \(\nabla^{\mathcal {S}}\) in the spin bundle S(M ₀). Killing vectors together with generalized Killing spinors (i.e. \(\nabla^{\mathcal {S}}\)-parallel spinors) are interpreted as the values of appropriate geometric symmetries of M, namely even and odd Killing fields. An explicit formula for the Killing representation of the algebra of supersymmetry is obtained, generalizing some results of Koszul. The generalized spin connection \(\nabla^{\mathcal {S}}\) defines a superconnection on M, via the super-version of a theorem of Wang.