Reducibility of bilevel programming problems to vector optimization problems

Reductions are studied of the bilevel programming problems to vector (multicriteria) optimization problems. A general framework is proposed for constructing these reductions. Some particular cases of bilevel problems are considered.     

Reducibility among single machine weighted completion time scheduling problems

Various sum of weighted completion time problems are compared. The constraints considered include release date, deadline, and continuous machine processing. Relations between the problems are developed by examining the computational complexity of transforming one problem class into another. These results give indications of the relative computational effort required to solve different problem classes.     

Reducibility of minimax to minisum 0–1 programming problems

We consider 0–1 programming problems with a minimax objective function and any set of constraints. Upon appropriate transformations of its cost coefficients, such a minimax problem can be reduced to a linear minisum problem with the same set of feasible solutions such that an optimal solution to the latter will also solve the original minimax problem.Although this reducibility applies for any 0–1 programming problem, it is of particular interest for certain locational decision models. Among the obvious implications are that an algorithm for solving a p-median (minisum) problem in a network will also solve a corresponding p-center (minimax) problem.It should be emphasized that the results presented will in general only hold for 0–1 problems due to intrinsic properties of the minimax criterion.     

Reducibility number

Let P be a poset in a class of posets P. A smallest positive integer r is called reducibility number of P with respect to P if there exists a non-empty subset S of P with |S|=r and P-S∈P. The reducibility numbers for the power set 2ⁿ of an n-set (n?2) with respect to the classes of distributive lattices, modular lattices and Boolean lattices are calculated. Also, it is shown that the reducibility number r of the lattice of all subgroups of a finite group G with respect to the class of all distributive lattices is 1 if and only if the order of G has at most two distinct prime divisors; further if r is a prime number then order of G is divisible by exactly three distinct primes. The class of pseudo-complemented u-posets is shown to be reducible. Deletable elements in semidistributive posets are characterized.     

Reducibility on families

A reducibility on families of subsets of natural numbers is introduced which allows the family per se to be treated without its representation by natural numbers being fixed. This reducibility is used to study a series of problems both in classical computability and on admissible sets: for example, describing index sets of families belonging to , generalizing Friedberg’s completeness theorem for a suitable reducibility on admissible sets, etc. *Supported by RFBR (project No. 05-01-00605) and by the Council for Grants (under RF President) and State Aid of Young Candidates of Science (grant MK-4314.2008.1). **Supported by RFBR (projects No. 08-01-00442 and 06-04002-DFGa), by the Council for Grants (under RF President) of Leading Scientific Schools (grant NSh-335.2008.1), and by the Russian Foundation for Support of Domestic Science. Translated from Algebra i Logika, Vol. 48, No. 1, pp. 31-53, January-February, 2009.     

Flow Hypergraph Reducibility

Reducible flow graphs were first defined by Hecht and Ullman in terms of intervals; another definition, based on two flow graph transformations, was also presented. In this paper, we extend the notion of reducibility to directed hypergraphs, proving that the interval and the transformation approaches are still equivalent when applied to this family.     

Reducibility of hyperplane arrangements

Certain problems on reducibility of central hyperplane arrangements are settled. Firstly, a necessary and sufficient condition on reducibility is obtained. More precisely, it is proved that the number of irreducible components of a central hyperplane arrangement equals the dimension of the space consisting of the logarithmic derivations of the arrangement with degree zero or one. Secondly, it is proved that the decomposition of an arrangement into a direct sum of its irreducible components is unique up to an isomorphism of the ambient space. Thirdly, an effective algorithm for determining the number of irreducible components and decomposing an arrangement into a direct sum of its irreducible components is offered. This algorithm can decide whether an arrangement is reducible, and if it is the case, what the defining equations of irreducible components are.     

Reducibility of matrix weights

In this paper, we discuss the notion of reducibility of matrix weights and introduce a real vector space \(\mathcal C_\mathbb R\) which encodes all information about the reducibility of W. In particular, a weight W reduces if and only if there is a nonscalar matrix T such that \(TW=WT^*\). Also, we prove that reducibility can be studied by looking at the commutant of the monic orthogonal polynomials or by looking at the coefficients of the corresponding three-term recursion relation. A matrix weight may not be expressible as direct sum of irreducible weights, but it is always equivalent to a direct sum of irreducible weights. We also establish that the decompositions of two equivalent weights as sums of irreducible weights have the same number of terms and that, up to a permutation, they are equivalent. We consider the algebra of right-hand-side matrix differential operators \(\mathcal D(W)\) of a reducible weight W, giving its general structure. Finally, we make a change of emphasis by considering the reducibility of polynomials, instead of reducibility of matrix weights.     

Reducibility of covers of AFT shifts

In this paper we show that the reducibility structure of several covers of sofic shifts is a flow invariant. In addition, we prove that for an irreducible subshift of almost finite type the left Krieger cover and the past set cover are reducible. We provide an example which shows that there are non almost finite type shifts which have reducible left Krieger covers. As an application we show that the Matsumoto algebra of an irreducible, strictly sofic shift of almost finite type is not simple.     

Reducibility of finite reflection groups

A finite (pseudo-)reflection group G naturally gives rise to a hyperplane arrangement,i.e.,its reflection arrangement.We show that G is reducible if and only if its reflection arrangement is reducible.     

交换矩阵半群的可约性

首先分别给出单生矩阵半群或者摹群不可约、不可分解以及完全可约的充分必要条件,其次讨论一般域上矩阵半群的可约性的一些条件,最后特别地讨论实数域上矩阵半群的可约性,完全确定了实数域上对称和反对称矩阵组成的不可约交换矩阵半群.     

Wadge Reducibility and Infinite Computations

This is a survey of results about Wadge reducibility in some spaces and its relation to the study of infinite (non-terminating) computations. We also discuss the related techniques and directions of future research. Supported by DFG-RFBR Grant 06-01-04002 and by RFBR grant 07-01-00543a.     

Reducibility of translates of Dickson polynomials

Let be a field and . The Dickson polynomial is characterized by the equation . We prove that is reducible if and only if there is a prime such that for some , or and for some . This result generalizes the well-known reducibility criterion for binomials; and it provides a reducibility criterion for where denotes the Chebyshev polynomial of degree .

     

Reducibility of lacunary polynomials,VII

Letk>1 and let be non-zero algebraic numbers contained in the field . It is shown that for almost all, in the sense of density integer vectorsn ₁,...,n _k the polynomial becomes irreducible over on dividing by the product of all factorsx–, where is a root of unity.Dedicated to Professor E. Hlawka on the occasion of his seventieth birthday