An exact method for minimizing the total treatment time in intensity-modulated radiotherapy

In this paper, we solve a combinatorial optimization problem that arises from the treatment planning of a type of radiotherapy where intensity is modulated by multileaf collimators (MLC) in a step-and-shoot manner. In Ernst et al [INFORMS Journal on Computing 21 (4) (2009): 562–574], we proposed an exact method for minimizing the number of MLC apertures needed for a treatment. Our method outperformed the fastest algorithms available at the time. We refer to our method as the CPI method. We now attempt to minimize the total treatment time by modifying our CPI method. This modification involves non-trivial work, as some of the search space elimination schemes used in the CPI method cannot be applied in here. In our numerical experiments, we again compare our new method with the fastest algorithms currently available. There has been significant recent research in this area; hence we compare our method with those published in Wake et al [Computers and Operations Research 36 (2009): 795–810], Ta?kin et al [Operations Research 58 (3) (2010): 674–690] and Cambazard et al [CPAIRO (2010): 1–16]. The numerical comparisons indicate that our method generally outperformed the first two, while being competitive with the third.     

Extremely primitive groups and linear spaces

A non-regular primitive permutation group is called extremely primitive if a point stabilizer acts primitively on each of its nontrivial orbits. Let S be a nontrivial finite regular linear space and G ≤ Aut(S). Suppose that G is extremely primitive on points and let rank(G) be the rank of G on points. We prove that rank(G) ≥ 4 with few exceptions. Moreover, we show that Soc(G) is neither a sporadic group nor an alternating group, and G = PSL(2, q) with q + 1 a Fermat prime if Soc(G) is a finite classical simple group.     

An efficient numerical method for a mathematical model of a transport of coagulating particles

A new computational algorithm based on a fast way of computing integral operators describing the coagulation process is proposed for a mathematical model of coagulating particles. Using this algorithm, the computational complexity of each timestep of an explicit difference scheme can be substantially reduced. For each step, the complexity of execution is reduced from O(NM²) arithmetic operations to O(NMRlnM), where N is the number of mesh points along the physical coordinates of particles, M is the number of mesh points in a grid corresponding to sizes of coagulating particles, and R is the rank of a matrix corresponding to the values of the function of a coagulation kernel at mesh points. Using this approach, computations can be greatly accelerated, provided that kernel rank R is small.     

Building Graphs Whose Independence Polynomials Have Only Real Roots

A stable set in a graph G is a set of pairwise non-adjacent vertices, and the stability number α(G) is the maximum size of a stable set in G. The independence polynomial of G is

$I(G; x) = s_{0}+s_{1}x+s_{2}x^{2}+\cdots+s_{\alpha}x^{\alpha},\alpha=\alpha(G),$

where s _k equals the number of stable sets of cardinality k in G (Gutman and Harary [11]).

Unlike the matching polynomial, the independence polynomial of a graph can have non-real roots. It is known that the polynomial I(G; x) has only real roots whenever (a) α(G) = 2 (Brown et al. [4]), (b) G is claw-free (Chudnowsky and Symour [6]). Brown et al. [3] proved that given a well-covered graph G, one can define a well-covered graph H such that G is a subgraph of H, α(G) = α(H), and I(H; x) has all its roots simple and real.In this paper, we show that starting from a graph G whose I(G; x) has only real roots, one can build an infinite family of graphs, some being well-covered, whose independence polynomials have only real roots (and, sometimes, are also palindromic).     

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.     

Tabu search embedded simulated annealing for the shortest route cut and fill problem

The shortest route cut and fill problem proposed by Henderson et al ¹ is studied in this paper where we extend the model to include multiple vehicles and a makespan objective. A new tabu search embedded simulated annealing algorithm for both models is developed. Computational experiments show that the new approach is robust and achieves better solutions when compared with those found using Henderson et al's algorithm for larger test cases within significantly shorter times.     

On soluble groups of module automorphisms of finite rank

Let R be a commutative ring, M an R-module and G a group of R-automorphisms of M, usually with some sort of rank restriction on G. We study the transfer of hypotheses between M/C _M (G) and [M,G] such as Noetherian or having finite composition length. In this we extend recent work of Dixon, Kurdachenko and Otal and of Kurdachenko, Subbotin and Chupordia. For example, suppose [M,G] is R-Noetherian. If G has finite rank, then M/C _M (G) also is R-Noetherian. Further, if [M,G] is R-Noetherian and if only certain abelian sections of G have finite rank, then G has finite rank and is soluble-by-finite. If M/C _M (G) is R-Noetherian and G has finite rank, then [M,G] need not be R-Noetherian.     

The General Problem of <Emphasis Type="Italic">m</Emphasis> Persons and <Emphasis Type="Italic">n</Emphasis> Positions for Short- and Long-Term Decision-Making

This paper discusses the well-known problems of m candidates and n positions usually called term assignment problems. The paper considers these problems when decisions for short and long term policies must be taken and also in extreme situations, such as emergency cases. Assignment and Knapsack problems, Heirarchy Analysis, Graphs Theory and Metric Spaces using Dynamic Programming are used on a computer.     

Possible isolation number of a matrix over nonnegative integers

Let ?₊ be the semiring of all nonnegative integers and A an m × n matrix over ?₊. The rank of A is the smallest k such that A can be factored as an m × k matrix times a k×n matrix. The isolation number of A is the maximum number of nonzero entries in A such that no two are in any row or any column, and no two are in a 2 × 2 submatrix of all nonzero entries. We have that the isolation number of A is a lower bound of the rank of A. For A with isolation number k, we investigate the possible values of the rank of A and the Boolean rank of the support of A. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is 1 or 2 only. We also determine a special type of m×n matrices whose isolation number is m. That is, those matrices are permutationally equivalent to a matrix A whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.     

Few distinct distances implies no heavy lines or circles

We study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set \(\mathcal{P}\) of n points determines o(n) distinct distances, then no line contains Ω(n ^7/8) points of \(\mathcal{P}\) and no circle contains Ω(n ^5/6) points of \(\mathcal{P}\).We rely on the partial variant of the Elekes-Sharir framework that was introduced by Sharir, Sheffer, and Solymosi in [19] for bipartite distinct distance problems. To prove our bound for the case of lines we combine this framework with a theorem from additive combinatorics, and for our bound for the case of circles we combine it with some basic algebraic geometry and a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang [20].A significant difference between our approach and that of [19] (and of other related results) is that instead of dealing with distances between two point sets that are restricted to one-dimensional curves, we consider distances between one set that is restricted to a curve and one set with no restrictions on it.     

Uniform extensions of partial geometries

A geometry of rank 2 is an incidence system (P, \(\mathcal{B}\)), where P is a set of points and \(\mathcal{B}\) is a set of subsets from P, called blocks. Two points are called collinear if they lie in a common block. A pair (a, B) from (P, \(\mathcal{B}\)) is called a flag if its point belongs to the block, and an antiflag otherwise. A geometry is called φ-uniform (φ is a natural number) if for any antiflag (a, B) the number of points in the block B collinear to the point a equals 0 or φ, and strongly φ-uniform if this number equals φ. In this paper, we study φ-uniform extensions of partial geometries pG _α (s, t) with φ = s and strongly φ-uniform geometries with φ = s ? 1. In particular, the results on extensions of generalized quadrangles, obtained earlier by Cameron and Fisher, are extended to the case of partial geometries.     

On a matrix trace inequality due to Ando,Hiai and Okubo

Ando et al. have proved that inequality \(\Re \mathfrak{e}trA^{p_1 } B^{q_1 \ldots } A^{p_k } B^{q_k } \leqslant trA^{p_1 + \ldots + p_k } B^{q_1 + \ldots + q_k }p\) is valid for all positive semidefinite matrices A,B and those nonnegative real numbers p₁, q₁,..., p_k, q_k which satisfy certain additional conditions. We give an example to show that this inequality is not valid for all collections of p₁, q₁,..., p_k, q_k ≥ 0. We also study related trace inequalities.     

Remarks on Ramanujam-Kawamata-Viehweg Vanishing Theorem

In this article we prove a general result on a nef vector bundle E on a projective manifold X of dimension n depending on the vector space H^n,n(X,E): It is also shown that H^n,n(X,E) = 0 for an indecomposable nef rank 2 vector bundles E on some specific type of n dimensional projective manifold X. The same vanishing shown to hold for indecomposable nef and big rank 2 vector bundles on any variety with trivial canonical bundle.     

The convolution method for fourier expansions. The case of generalized transmission conditions of crack (screen) type in piecewise inhomogeneous media

We consider boundary value problems for the equation ? _x (K ? _x ?) + KL[?] = 0 in the space R ⁿ with generalized transmission conditions of the type of a strongly permeable crack or a weakly permeable screen on the surface x = 0. (Here L is an arbitrary linear differential operator with respect to the variables y ₁, …, y _n?1.) The coefficients K(x) > 0 are monotone functions of certain classes in the regions separated by the screen x = 0. The desired solution has arbitrary given singular points and satisfies a sufficiently weak condition at infinity.We derive formulas expressing the solutions of the above-mentioned problems in the form of simple quadratures via the solutions of the considered equation with a constant coefficient K for given singular points in the absence of a crack or a screen. In particular, the obtained formulas permit one to solve boundary value problems with generalized transmission conditions for equations with functional piecewise continuous coefficients in the framework of the theory of harmonic functions.     

Rational realization of the minimum ranks of nonnegative sign pattern matrices

A sign pattern matrix (or nonnegative sign pattern matrix) is a matrix whose entries are from the set {+,?, 0} ({+, 0}, respectively). The minimum rank (or rational minimum rank) of a sign pattern matrix A is the minimum of the ranks of the matrices (rational matrices, respectively) whose entries have signs equal to the corresponding entries of A. Using a correspondence between sign patterns with minimum rank r ≥ 2 and point-hyperplane configurations in R^r?1 and Steinitz’s theorem on the rational realizability of 3-polytopes, it is shown that for every nonnegative sign pattern of minimum rank at most 4, the minimum rank and the rational minimum rank are equal. But there are nonnegative sign patterns with minimum rank 5 whose rational minimum rank is greater than 5. It is established that every d-polytope determines a nonnegative sign pattern with minimum rank d + 1 that has a (d + 1) × (d + 1) triangular submatrix with all diagonal entries positive. It is also shown that there are at most min{3m, 3n} zero entries in any condensed nonnegative m × n sign pattern of minimum rank 3. Some bounds on the entries of some integer matrices achieving the minimum ranks of nonnegative sign patterns with minimum rank 3 or 4 are established.     

A note on Weyl groups and root lattices

We follow the dual approach to Coxeter systems and show for Weyl groups that a set of reflections generates the group if and only if the related sets of roots and coroots generate the root and the coroot lattices, respectively. Previously, we have proven if (W, S) is a Coxeter system of finite rank n with set of reflections T and if \(t_1, \ldots t_n \in T\) are reflections in W that generate W, then \(P:= \langle t_1, \ldots t_{n-1}\rangle \) is a parabolic subgroup of (W, S) of rank \(n-1\) (Baumeister et al. in J Group Theory 20:103–131, 2017, Theorem 1.5). Here we show if (W, S) is crystallographic as well, then all the reflections \(t \in T\) such that \(\langle P, t\rangle = W\) form a single orbit under conjugation by P.     

Rings of quasi-endomorphisms of some direct sums of torsion-free Abelian groups

We consider a representation of quasi-endomorphisms of Abelian torsion-free groups of rank 4 bymatrices of order 4 over the field of rational numbers Q. We obtain a classification for quasi-endomorphism rings of Abelian torsion-free groups of rank 4 quasi-decomposable into a direct sum of groups A ₁, A ₂ of rank 1 and strongly indecomposable group B of rank 2 such that quasi-homomorphism groups Q ? Hom(A _i , B) and Q ? Hom(B, A _i ) for any i = 1, 2 have rank 1 or are zero. Moreover, for algebras from the classification we present necessary and sufficient conditions for their realization as quasi-endomorphism rings of these groups.     

Multivariate extreme value copulas with factor and tree dependence structures

Parsimonious extreme value copula models with O(d) parameters for d observed variables of extrema are presented. These models utilize the dependence characteristics, including factor and tree structures, assumed on the underlying variables that give rise to the data of extremes. For factor structures, a class of parametric models is obtained by taking the extreme value limit of factor copulas with non-zero tail dependence. An alternative model suitable for both factor and tree structures imposes constraints on the parametric Hüsler-Reiss copula to get representations in terms of O(d) other parameters. Dependence properties are discussed. As the full density is often intractable, the method of composite (pairwise) likelihood is used for model inference. Procedures to improve the stability of bivariate density evaluation are also developed. The proposed models are applied to two data examples — one for annual extreme river flows and one for bimonthly extremes of daily stock returns.     

Serre dimension of monoid algebras

Let R be a commutative Noetherian ring of dimension d, M a commutative cancellative torsion-free monoid of rank r and P a finitely generated projective R[M]-module of rank t. Assume M is Φ-simplicial seminormal. If \(M\in \mathcal {C}({\Phi })\), then Serre dim R[M]≤d. If r≤3, then Serre dim R[int(M)]≤d. If \(M\subset \mathbb {Z}_{+}^{2}\) is a normal monoid of rank 2, then Serre dim R[M]≤d. Assume M is c-divisible, d=1 and t≥3. Then P?∧ ^t P⊕R[M] ^t?1. Assume R is a uni-branched affine algebra over an algebraically closed field and d=1. Then P?∧ ^t P⊕R[M] ^t?1.