The connected <Emphasis Type="Italic">p</Emphasis>-median problem on block graphs

In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G.     

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.     

Counting rises and levels in <Emphasis Type="Italic">r</Emphasis>-color compositions

An r-color composition of a positive integer n is a sequence of positive integers, called parts, summing to n in which each part of size r is assigned one of r possible colors. In this paper, we address the problem of counting the r-color compositions having a prescribed number of rises. Formulas for the relevant generating functions are computed which count the compositions in question according to a certain statistic. Furthermore, we find explicit formulas for the total number of rises within all of the r-color compositions of n having a fixed number of parts. A similar treatment is given for the problem of counting the number of levels and a further generalization in terms of rises of a particular type is discussed.     

Lower bounds on the signed total k-domination number of graphs

Let G be a graph with vertex set V(G). For any integer k ≥ 1, a signed total k-dominating function is a function f: V(G) → {?1, 1} satisfying ∑_x∈N(v)f(x) ≥ k for every v ∈ V(G), where N(v) is the neighborhood of v. The minimum of the values ∑_v∈V(G)f(v), taken over all signed total k-dominating functions f, is called the signed total k-domination number. In this note we present some new sharp lower bounds on the signed total k-domination number of a graph. Some of our results improve known bounds.     

On vector variational-like inequalities and vector optimization problems with (<Emphasis Type="Italic">G</Emphasis>, <Emphasis Type="Italic">α</Emphasis>)-invexity

The aim of this paper is to study the relationship among Minty vector variational-like inequality problem, Stampacchia vector variational-like inequality problem and vector optimization problem involving (G, α)-invex functions. Furthermore, we establish equivalence among the solutions of weak formulations of Minty vector variational-like inequality problem, Stampacchia vector variational-like inequality problem and weak efficient solution of vector optimization problem under the assumption of (G, α)-invex functions. Examples are provided to elucidate our results.     

On approximation of dominating tree in wireless sensor networks

We study the following problem: Given a weighted graph G = (V, E, w) with \({w: E \rightarrow \mathbb{Z}^+}\) , the dominating tree (DT) problem asks us to find a minimum total edge weight tree T such that for every \({v \in V}\) , v is either in T or adjacent to a vertex in T. To the best of our knowledge, this problem has not been addressed in the literature. Solving the DT problem can yield a routing backbone for broadcast protocols since (1) each node does not have to construct their own broadcast tree, (2) utilize the virtual backbone to reduce the message overhead, and (3) the weight of backbone representing the energy consumption is minimized. We prove the hardness of this problem, including the inapproximability result and present an approximation algorithm together with an efficient heuristic. Finally, we verify the effectiveness of our proposal through simulation.     

Classification of 2-step nilpotent Lie algebras of dimension 9 with 2-dimensional center

A Lie algebra L is called 2-step nilpotent if L is not abelian and [L,L] lies in the center of L. 2-step nilpotent Lie algebras are useful in the study of some geometric problems, and their classification has been an important problem in Lie theory. In this paper, we give a classification of 2-step nilpotent Lie algebras of dimension 9 with 2-dimensional center.     

Scheduling an unbounded batching machine with family jobs and setup times

We consider the problem of scheduling n jobs on an unbounded batching machine that can process any number of jobs belonging to the same family simultaneously in the same batch. All jobs in the same batch complete at the same time. Jobs belonging to different families cannot be processed in the same batch, and setup times are required to switch between batches that process jobs from different families. For a fixed number of families m, we present a generic forward dynamic programming algorithm that solves the problem of minimizing an arbitrary regular cost function in pseudopolynomial time. We also present a polynomial-time backward dynamic programming algorithm with time complexity O (mn(n/m+1) ^m ) for minimizing any additive regular minsum objective function and any incremental regular minmax objective function. The effectiveness of our dynamic programming algorithm is shown by computational experiments based on the scheduling of the heat-treating process in a steel manufacturing plant.     

A partition-based relaxation for Steiner trees

The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G = (V, E), a set of terminals \({R\subseteq V}\) , and non-negative costs c _e for all edges \({e \in E}\) . Any tree that contains all terminals is called a Steiner tree; the goal is to find a minimum-cost Steiner tree. The vertices \({V \backslash R}\) are called Steiner vertices. The best approximation algorithm known for the Steiner tree problem is a greedy algorithm due to Robins and Zelikovsky (SIAM J Discrete Math 19(1):122–134, 2005); it achieves a performance guarantee of \({1+\frac{\ln 3}{2}\approx 1.55}\) . The best known linear programming (LP)-based algorithm, on the other hand, is due to Goemans and Bertsimas (Math Program 60:145–166, 1993) and achieves an approximation ratio of 2?2/|R|. In this paper we establish a link between greedy and LP-based approaches by showing that Robins and Zelikovsky’s algorithm can be viewed as an iterated primal-dual algorithm with respect to a novel LP relaxation. The LP used in the first iteration is stronger than the well-known bidirected cut relaxation. An instance is b-quasi-bipartite if each connected component of \({G \backslash R}\) has at most b vertices. We show that Robins’ and Zelikovsky’s algorithm has an approximation ratio better than \({1+\frac{\ln 3}{2}}\) for such instances, and we prove that the integrality gap of our LP is between \({\frac{8}{7}}\) and \({\frac{2b+1}{b+1}}\) .     

A note on the minimum total coloring of planar graphs

Graph coloring is an important tool in the study of optimization,computer science,network design,e.g.,file transferring in a computer network,pattern matching,computation of Hessians matrix and so on.In this paper,we consider one important coloring,vertex coloring of a total graph,which is also called total coloring.We consider a planar graph G with maximum degree Δ(G)≥8,and proved that if G contains no adjacent i,j-cycles with two chords for some i,j∈{5,6,7},then G is total-(Δ+1)-colorable.     

Two-stage flexible flow shop scheduling subject to fixed job sequences

This paper investigates the scheduling problem in a two-stage flexible flow shop, which consists of m stage-1 parallel dedicated machines and a stage-2 bottleneck machine, subject to the condition that n _l jobs per type l∈{1, …, m} are processed in a fixed sequence. Four regular performance metrics, including the total completion time, the maximum lateness, the total tardiness, and the number of tardy jobs, are considered. For each considered objective function, we aim to determine an optimal interleaving processing sequence of all jobs coupled with their starting times on the stage-2 bottleneck machine. The problem under study is proved to be strongly NP-hard. An O(m²Π_l=1 ^m n _l ²) dynamic programming algorithm coupled with numerical experiments is presented.     

Scalarization of stationary semiclassical problems for systems of equations and its application in plasma physics

We propose a method for determining asymptotic solutions of stationary problems for pencils of differential (and pseudodifferential) operators whose symbol is a self-adjoint matrix. We show that in the case of constant multiplicity, the problem of constructing asymptotic solutions corresponding to a distinguished eigenvalue (called an effective Hamiltonian, term, or mode) reduces to studying objects related only to the determinant of the principal matrix symbol and the eigenvector corresponding to a given (numerical) value of this effective Hamiltonian. As an example, we show that stationary solutions can be effectively calculated in the problem of plasma motion in a tokamak.     

A nested family of $$\varvec{}$$-total effective rewards for positional games

We consider Gillette’s two-person zero-sum stochastic games with perfect information. For each \(k \in \mathbb {N}=\{0,1,\ldots \}\) we introduce an effective reward function, called k-total. For \(k = 0\) and 1 this function is known as mean payoff and total reward, respectively. We restrict our attention to the deterministic case. For all k, we prove the existence of a saddle point which can be realized by uniformly optimal pure stationary strategies. We also demonstrate that k-total reward games can be embedded into \((k+1)\)-total reward games.     

On critical exponents of Dowling matroids

The critical problem in matroid theory is the problem to determine the critical exponent of a given representable matroid over a finite field. In this paper, we study the critical exponents of a class of representable matroids over finite fields, called Dowling matroids. Then the critical problem for a Dowling matroid is corresponding to the classical problem in coding theory to determine the maximum dimension k such that there exists an \([n,k,d]_q\) code for given n, d and q. We give a necessary and sufficient condition on the critical exponents of Dowling matroids by using a coding theoretical approach.     

Equivalence of two definitions of a generalized <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> solution to the initial-boundary value problem for the wave equation

In our previous papers, we introduced the notion of a generalized solution to the initial-boundary value problem for the wave equation with a boundary function µ(t) such that the integral ∫ ₀ ^T (T ? t)|µ(t)| ^p dt exists. Here we prove that this solution is a unique solution to the problem in L _p that satisfies the corresponding integral identity.     

On the Number of Ordinary Circles Determined by <Emphasis Type="Italic">n</Emphasis> Points

In this paper we deal with the following problem: Given a set B consisting of n points, not all on a line or a circle. A circle passes through exactly three points of B is called an ordinary circle. What is the minimal possible number of ordinary circles determined by B? In this paper we improve the best-known lower bound \(\frac{22}{247}{n\choose2}\) to \(\frac{1}{9}{n\choose2}\).     

The conjugacy problem in extensions of Thompson’s group F

We solve the twisted conjugacy problem on Thompson’s group F. We also exhibit orbit undecidable subgroups of Aut(F), and give a proof that Aut(F) and Aut₊(F) are orbit decidable provided a certain conjecture on Thompson’s group T is true. By using general criteria introduced by Bogopolski, Martino and Ventura in [5], we construct a family of free extensions of F where the conjugacy problem is unsolvable. As a byproduct of our techniques, we give a new proof of a result of Bleak–Fel’shtyn–Gonçalves in [4] showing that F has property R_∞, and which can be extended to show that Thompson’s group T also has property R_∞.     

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.     

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.     

Linear homotopy method for computing generalized tensor eigenpairs

Let m,m′, n be positive integers such that m ≠ m′. Let A be an mth order n-dimensional tensor, and let ? be an m′th order n-dimensional tensor. λ ∈ ? is called a ?-eigenvalue of A if A x^m?1 = λ?x^m′?1 and ?xm′= 1 for some x ∈ ?ⁿ\{0}. In this paper, we propose a linear homotopy method for solving this eigenproblem. We prove that the method finds all isolated ?-eigenpairs. Moreover, it is easy to implement. Numerical results are provided to show the efficiency of the proposed method.