An improved approximation algorithm for the <Emphasis Type="Italic">k</Emphasis>-level facility location problem with soft capacities

We consider the k-level facility location problem with soft capacities (k-LFLPSC). In the k-LFLPSC, each facility i has a soft capacity u _i along with an initial opening cost f _i ≥ 0, i.e., the capacity of facility i is an integer multiple of u _i incurring a cost equals to the corresponding multiple of f _i . We firstly propose a new bifactor (ln(1/β)/(1 ?β),1+2/(1 ?β))-approximation algorithm for the k-level facility location problem (k-LFLP), where β ∈ (0, 1) is a fixed constant. Then, we give a reduction from the k-LFLPSC to the k-LFLP. The reduction together with the above bifactor approximation algorithm for the k-LFLP imply a 5.5053-approximation algorithm for the k-LFLPSC which improves the previous 6-approximation.     

An exact and heuristic approach for the <Emphasis Type="Italic">d</Emphasis>-minimum branch vertices problem

Given a connected graph \(G=(V,E)\), the d-Minimum Branch Vertices (d-MBV) problem consists in finding a spanning tree of G with the minimum number of vertices with degree strictly greater than d. We developed a Miller–Tucker–Zemlin based formulation with valid inequalities for this problem. The results obtained for different values of d show the effectiveness of the proposed method, which has solved several instances faster than previous methods. Also, an heuristic is proposed for this problem, that was tested on several instances of the Minimum Branch Vertices problem, which is the d-MBV problem, when \(d = 2\).     

Inverse problem with nonlocal observation of finding the coefficient multiplying <Emphasis Type="Italic">u</Emphasis> <Subscript> <Emphasis Type="Italic">t</Emphasis> </Subscript> in the parabolic equation

We study the inverse problem of the reconstruction of the coefficient ?(x, t) = ?⁰(x, t) + r(x) multiplying u_t in a nonstationary parabolic equation. Here ?⁰(x, t) ≥ ?⁰ > 0 is a given function, and r(x) ≥ 0 is an unknown function of the class L_∞(Ω). In addition to the initial and boundary conditions (the data of the direct problem), we pose the problem of nonlocal observation in the form ∫₀^Tu(x, t) dμ(t) = χ(x) with a known measure dμ(t) and a function χ(x). We separately consider the case dμ(t) = ω(t)dt of integral observation with a smooth function ω(t). We obtain sufficient conditions for the existence and uniqueness of the solution of the inverse problem, which have the form of ready-to-verify inequalities. We suggest an iterative procedure for finding the solution and prove its convergence. Examples of particular inverse problems for which the assumptions of our theorems hold are presented.     

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.     

Finite <Emphasis Type="Italic">p</Emphasis>-groups all of whose maximal abelian subgroups are soft

A subgroup A of a p-group G is said to be soft in G if C _G (A) = A and |N _G (A/A| = p. In this paper we determined finite p-groups all of whose maximal abelian subgroups are soft; see Theorem A and Proposition 2.4.     

Automatic knowledge extraction from survey data: learning <Emphasis Type="Italic">M</Emphasis>-of-<Emphasis Type="Italic">N</Emphasis> constructs using a hybrid approach

Data collected from a survey typically consist of attributes that are mostly if not completely binary-valued or binary-encoded. We present a method for handling such data where the underlying data analysis can be cast as a classification problem. We propose a hybrid method that combines neural network and decision tree methods. The network is trained to remove irrelevant data attributes and the decision tree is applied to extract comprehensible classification rules from the trained network. The conditions of the rules are in the form of a conjunction of M-of-N constructs. An M-of-N construct is a rule condition that is satisfied if (at least, exactly, at most) M of the N binary attributes in the construct are present. The effectiveness of the method is illustrated on data collected for a study of global car market segmentation. The results show that besides achieving high predictive accuracy, the method also allows meaningful interpretation of the relationships among the data variables.     

On the phase transitions of (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)-SAT

Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let T _k (V) denote the set of all 2 ^k n ^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in T _k (V) independently with probability p, and let Q be a given set of q “bad” tuple assignments. An instance I = (C,Q) is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tuple assignment in Q. Suppose that θ, q > 0 are fixed and ε = ε(n) > 0 be such that εlnn/lnlnn→∞. Let k ≥ (1 + θ) log₂ n and let \({p_0} = \frac{{\ln 2}}{{q{n^{k - 1}}}}\). We prove that

$$\mathop {\lim }\limits_{n \to \infty } P\left[ {I is satisfiable} \right] = \left\{ {\begin{array}{*{20}c} {1,} & {p \leqslant (1 - \varepsilon )p_0 ,} \\ {0,} & {p \geqslant (1 + \varepsilon )p_0 .} \\ \end{array} } \right.$$

     

The development of management sciences/operational research discourses: surveying the trends in the US and the UK

This paper explores the trends in American and British management science/operational research (MS/OR) during the last 25 years. We argue that British MS/OR has developed a soft and systemic approach to MS/OR practice, which has resulted in the emergence of a number of interpretive and critical-oriented methodologies. American MS/OR practice has remained closed to the positivistic discourse. Using a set of keywords and authors’ names associated with the main features of the interpretive and critical MS discourses, we surveyed articles published in three major US MS/OR journals. We compare these results with trends in the UK MS/OR scene. Findings appear to confirm the different directions taken by the MS/OR practice across the Atlantic. The paper posits possible reasons underpinning these differences: firstly, the particular methodological path followed by the British MS/OR, from early ‘soft systems’ applications in the early 1970s to the now well-established ‘Problem Structuring Methods’; and secondly, continuous engagement between the systems and MS/OR British communities (a dialogue that seems not to have occurred in the US). The paper contributes to a reflection on the MS/OR historical developments and contrasts these developments in both countries, two areas of OR significantly under-researched.     

The Automorphism Group of a Class of Nilpotent Groups with Infinite Cyclic Derived Subgroups

The automorphism group of a class of nilpotent groups with infinite cyclic derived subgroups is determined. Let G be the direct product of a generalized extraspecial Z-group E and a free abelian group A with rank m, where E ={(1 kα_1 kα_2 ··· kα_nα_(n+1) 0 1 0 ··· 0 α_(n+2)...............000...1 α_(2n+1)000...01|αi∈ Z, i = 1, 2,..., 2 n + 1},where k is a positive integer. Let AutG G be the normal subgroup of Aut G consisting of all elements of Aut G which act trivially on the derived subgroup G of G, and AutG/ζ G,ζ GG be the normal subgroup of Aut G consisting of all central automorphisms of G which also act trivially on the center ζ G of G. Then(i) The extension 1→ Aut_(G') G→ AutG→ Aut(G')→ 1 is split.(ii) Aut_(G') G/Aut_(G/ζ G,ζ G)G≌Sp(2 n, Z) ×(GL(m, Z)■(Z~)m).(iii) Aut_(G/ζ G,ζ GG/Inn G)≌(Z_k)~(2n)⊕(Z)~(2nm).     

Multimethodology in series and parallel: strategic planning using hard and soft OR

This paper examines two distinct ways in which hard and soft operational research (OR) methodologies can be combined, in series and in parallel. Multimethodology in series is acknowledged as the simpler and more common approach. Multimethodology in parallel is identified as having the potential to provide significant benefits to projects in political, changing, or ‘wicked’ contexts that multimethodology in series cannot. Observations regarding these approaches to multimethodology are examined in light of an information systems strategic planning project in the Australian public sector. Two distinct methodologies were combined in the project: soft systems methodology and project management. These methodologies are based on the soft and hard paradigms, respectively. However, findings in this paper have the potential to be transferred to combinations of other hard and soft OR methodologies.     

On the Dunford Property (<Emphasis Type="Italic">C</Emphasis>) for Bounded Linear Operators <Emphasis Type="Italic">RS</Emphasis> and <Emphasis Type="Italic">SR</Emphasis>

In this paper we show that if \({S\in L(X,Y)}\) and \({R\in L(Y,X),}\) X and Y complex Banach spaces, then the products RS and SR share the Dunford property (C). We also study property (C) for R, S, RS and \({SR \in L(X)}\) in the case that R and S satisfies the operator equations RSR = R ² and SRS = S ².     

On <Emphasis Type="Italic">k</Emphasis>- critical 2<Emphasis Type="Italic">k</Emphasis>- connected graphs

A graph G is called an (n,k)-graph if κ(G-S)=n-|S| for any S ? V(G) with |S| ≤ k, where ?(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K_2k+2?(1-factor) is the unique (2k, k)-graph. Kriesell has settled two special cases for k = 3,4. We prove the conjecture for the general case k ≥ 5.     

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.     

An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

On Semi-Finite Hexagons of Order (2, <Emphasis Type="Italic">t</Emphasis>) Containing a Subhexagon

The research in this paper was motivated by one of the most important open problems in the theory of generalized polygons, namely the existence problem for semi–finite thick generalized polygons. We show here that no semi–finite generalized hexagon of order (2, t) can have a subhexagon H of order 2. Such a subhexagon is necessarily isomorphic to the split Cayley generalized hexagon H(2) or its point–line dual H ^D (2). In fact, the employed techniques allow us to prove a stronger result. We show that every near hexagon \({\mathcal{S}}\) of order (2, t) which contains a generalized hexagon H of order 2 as an isometrically embedded subgeometry must be finite. Moreover, if \({H \cong H^{D}}\)(2) then \({\mathcal{S}}\) must also be a generalized hexagon, and consequently isomorphic to either H ^D (2) or the dual twisted triality hexagon T(2, 8).     

<Emphasis Type="Italic">tt</Emphasis><Superscript>*</Superscript>-Geometry and Pluriharmonic Maps

In this paper we use the real differential geometric definition of a metric (a unimodular oriented metric) tt^*-bundle of Cortés and the author (Topological-anti-topological fusion equations, pluriharmonic maps and special Kähler manifolds) to define a map Φ from the space of metric (unimodular oriented metric) tt^*-bundles of rank r over a complex manifold M to the space of pluriharmonic maps from M to {GL}(r)/O(p,q) (respectively {SL}(r)/SO(p,q)), where (p,q) is the signature of the metric. In the sequel the image of the map Φ is characterized. It follows, that in signature (r,0) the image of Φ is the whole space of pluriharmonic maps. This generalizes a result of Dubrovin (Comm. Math. Phys. 152 (1992; S539–S564).     

Post-<Emphasis Type="Italic">J</Emphasis> test inference in non-nested linear regression models

This paper considers the post-J test inference in non-nested linear regression models. Post-J test inference means that the inference problem is considered by taking the first stage J test into account. We first propose a post-J test estimator and derive its asymptotic distribution. We then consider the test problem of the unknown parameters, and a Wald statistic based on the post-J test estimator is proposed. A simulation study shows that the proposed Wald statistic works perfectly as well as the two-stage test from the view of the empirical size and power in large-sample cases, and when the sample size is small, it is even better. As a result, the new Wald statistic can be used directly to test the hypotheses on the unknown parameters in non-nested linear regression models.     

Valuation ideals and primary <Emphasis Type="Italic">w</Emphasis>-ideals

Let D be an integral domain, V (D) (resp., t-V (D)) be the set of all valuation (resp., t-valuation) ideals of D, and w-P(D) be the set of primary w-ideals of D. Let D[X] be the polynomial ring over D, c(f) be the ideal of D generated by the coefficients of f ∈ D[X], and N _v = {f ∈ D[X] | c(f) _v = D}. In this paper, we study integral domains D in which w-P(D) ? t-V (D), t-V (D) ? w-P(D), or t-V (D) = w-P(D). We also study the relationship between t-V (D) and \(V\left( {D{{\left[ X \right]}_{{N_v}}}} \right)\), and characterize when t-V (A + XB[X]) ? w-P(A + XB[X]) holds for a proper extension A ? B of integral domains.     

Strong convergence theorem by a hybrid extragradient-like approximation method for variational inequalities and fixed point problems

The purpose of this paper is to investigate the problem of finding a common element of the set of fixed points F(S) of a nonexpansive mapping S and the set of solutions Ω _A of the variational inequality for a monotone, Lipschitz continuous mapping A. We introduce a hybrid extragradient-like approximation method which is based on the well-known extragradient method and a hybrid (or outer approximation) method. The method produces three sequences which are shown to converge strongly to the same common element of \({F(S)\cap\Omega_{A}}\). As applications, the method provides an algorithm for finding the common fixed point of a nonexpansive mapping and a pseudocontractive mapping, or a common zero of a monotone Lipschitz continuous mapping and a maximal monotone mapping.     

On the computation of <Emphasis Type="Italic">C</Emphasis>* certificates

The cone of completely positive matrices C* is the convex hull of all symmetric rank-1-matrices xx ^T with nonnegative entries. While there exist simple certificates proving that a given matrix \({B\in C^*}\) is completely positive it is a rather difficult problem to find such a certificate. We examine a simple algorithm which—for a given input B—either determines a certificate proving that \({B\in C^*}\) or converges to a matrix \({\bar S}\) in C* which in some sense is “close” to B. Numerical experiments on matrices B of dimension up to 200 conclude the presentation.