Inverse <Emphasis Type="Italic">p</Emphasis>-median problems with variable edge lengths

The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly NP{\mathcal{NP}}-hard on general graphs and weakly NP{\mathcal{NP}}-hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest a linear time algorithm.     

Inverse median location problems with variable coordinates

Given n points in \mathbbR^d{\mathbb{R}^d} with nonnegative weights, the inverse 1-median problem with variable coordinates consists in changing the coordinates of the given points at minimum cost such that a prespecified point in \mathbbR^d{\mathbb{R}^d} becomes the 1-median. The cost is proportional to the increase or decrease of the corresponding point coordinate. If the distances between points are measured by the rectilinear norm, the inverse 1-median problem is NP{\mathcal{NP}}-hard, but it can be solved in pseudo-polynomial time. Moreover, a fully polynomial time approximation scheme exists in this case. If the point weights are assumed to be equal, the corresponding inverse problem can be reduced to d continuous knapsack problems and is therefore solvable in O(nd) time. In case that the squared Euclidean norm is used, we derive another efficient combinatorial algorithm which solves the problem in O(nd) time. It is also shown that the inverse 1-median problem endowed with the Chebyshev norm in the plane is NP{\mathcal{NP}}-hard. Another pseudo-polynomial algorithm is developed for this case, but it is shown that no fully polynomial time approximation scheme does exist.     

On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices

We examine the performance of different subtour-patching heuristics for solving the strongly NP\mathcal{NP}-hard traveling salesman problem (TSP) on permuted Monge matrices. We prove that a well-known heuristic is asymptotically optimal for the TSP on product matrices and k-root cost matrices. We also show that the heuristic is provably asymptotically optimal for general permuted Monge matrices under some mild conditions. Our theoretical results are strongly supported by the findings of a large-scale experimental study on randomly generated numerical examples, which show that the heuristic is not only asymptotically optimal, but also finds optimal TSP tours with high probability that increases with the problem size. Thus the heuristic represents a practical tool to solve large instances of the problem.     

A branch and bound algorithm for scheduling jobs with controllable processing times on a single machine to meet due dates

In most deterministic scheduling problems, job-processing times are regarded as constant and known in advance. However, in many realistic environments, job-processing times can be controlled by the allocation of a common resource to jobs. In this paper, we consider the problem of scheduling jobs with arbitrary release dates and due dates on a single machine, where job-processing times are controllable and are modeled by a non-linear convex resource consumption function. The objective is to determine simultaneously an optimal processing permutation as well as an optimal resource allocation, such that no job is completed later than its due date, and the total resource consumption is minimized. The problem is strongly NP\mathcal{NP}-hard. A branch and bound algorithm is presented to solve the problem. The computational experiments show that the algorithm can provide optimal solution for small-sized problems, and near-optimal solution for medium-sized problems in acceptable computing time.     

Routing problems with loading constraints

We consider difficult combinatorial optimization problems arising in transportation logistics when one is interested in optimizing both the routing of vehicles and the loading of goods into them. The separate problems (routing and loading) are already NP\mathcal{NP}-hard, and very difficult to solve in practice. A fortiori their combination is extremely challenging and stimulating. Although the specific literature is still quite limited, a first attempt to a systematic view of this field can be useful both to academic researchers and to practitioners. We review vehicle routing problems with two- and three-dimensional loading constraints. Other combinations of routing and special loading constraints arising from industrial applications are also considered.     

On a bipartition problem of Bollobás and Scott

The bipartite density of a graph G is max {|E(H)|/|E(G)|: H is a bipartite subgraph of G}. It is NP-hard to determine the bipartite density of any triangle-free cubic graph. A biased maximum bipartite subgraph of a graph G is a bipartite subgraph of G with the maximum number of edges such that one of its partite sets is independent in G. Let $ \mathcal{H} $ \mathcal{H} denote the collection of all connected cubic graphs which have bipartite density $ \tfrac{4} {5} $ \tfrac{4} {5} and contain biased maximum bipartite subgraphs. Bollobás and Scott asked which cubic graphs belong to $ \mathcal{H} $ \mathcal{H} . This same problem was also proposed by Malle in 1982. We show that any graph in $ \mathcal{H} $ \mathcal{H} can be reduced, through a sequence of three types of operations, to a member of a well characterized class. As a consequence, we give an algorithm that decides whether a given graph G belongs to $ \mathcal{H} $ \mathcal{H} . Our algorithm runs in polynomial time, provided that G has a constant number of triangles that are not blocks of G and do not share edges with any other triangles in G.     

Supply chain scheduling to minimize holding costs with outsourcing

This paper addresses a scheduling problem in a flexible supply chain, in which the jobs can be either processed in house, or outsourced to a third-party supplier. The goal is to minimize the sum of holding and delivery costs. This problem is proved to be strongly \(\mathcal{NP}\) -hard. Consider two special cases, in which the jobs have identical processing times. For the problem with limited outsourcing budgets, a \(\mathcal{NP}\) -hardness proof, a pseudo-polynomial algorithm and a fully polynomial time approximation scheme are presented. For the problem with unlimited outsourcing budgets, the problem is shown to be equivalent to the shortest path problem, and therefore it is in class  \(\mathcal{P}\) . This shortest-path-problem solution approach is further shown to be applicable to a similar but more applicable problem, in which the number of deliveries is upper bounded.     

Two-level evolutionary approach to the survivable mesh-based transport network topological design

The complete topology design problem of survivable mesh-based transport networks is to address simultaneously design of network topology, working path routing, and spare capacity allocation based on span-restoration. Each constituent problem in the complete design problem could be formulated as an Integer Programming (IP) and is proved to be NP\mathcal{NP} -hard. Due to a large amount of decision variables and constraints involved in the IP formulation, to solve the problem directly by exact algorithms (e.g. branch-and-bound) would be impractical if not impossible. In this paper, we present a two-level evolutionary approach to address the complete topology design problem. In the low-level, two parameterized greedy heuristics are developed to jointly construct feasible solutions (i.e., closed graph topologies satisfying all the mesh-based network survivable constraints) of the complete problem. Unlike existing “zoom-in”-based heuristics in which subsets of the constraints are considered, the proposed heuristics take all constraints into account. An estimation of distribution algorithm works on the top of the heuristics to tune the control parameters. As a result, optimal solution to the considered problem is more likely to be constructed from the heuristics with the optimal control parameters. The proposed algorithm is evaluated experimentally in comparison with the latest heuristics based on the IP software CPLEX, and the “zoom-in”-based approach on 28 test networks problems. The experimental results demonstrate that the proposed algorithm is more effective in finding high-quality topologies than the IP-based heuristic algorithm in 21 out of 28 test instances with much less computational costs, and performs significantly better than the “zoom-in”-based approach in 19 instances with the same computational costs.     

Modules with Cosupport and Injective Functors

Several authors have studied the filtered colimit closure \varinjlimB\varinjlim\mathcal{B} of a class B\mathcal{B} of finitely presented modules. Lenzing called \varinjlimB\varinjlim\mathcal{B} the category of modules with support in B\mathcal{B}, and proved that it is equivalent to the category of flat objects in the functor category (B^op,Ab)(\mathcal{B}^\mathrm{op},\mathsf{Ab}). In this paper, we study the category (Mod-R)^B({\mathsf{Mod}\textnormal{-}R})^{\mathcal{B}} of modules with cosupport in B\mathcal{B}. We show that (Mod-R)^B({\mathsf{Mod}\textnormal{-}R})^{\mathcal{B}} is equivalent to the category of injective objects in (B,Ab)(\mathcal{B},\mathsf{Ab}), and thus recover a classical result by Jensen-Lenzing on pure injective modules. Works of Angeleri-Hügel, Enochs, Krause, Rada, and Saorín make it easy to discuss covering and enveloping properties of (Mod-R)^B({\mathsf{Mod}\textnormal{-}R})^{\mathcal{B}}, and furthermore we compare the naturally associated notions of B\mathcal{B}-coherence and B\mathcal{B}-noetherianness. Finally, we prove a number of stability results for \varinjlimB\varinjlim\mathcal{B} and (Mod-R)^B({\mathsf{Mod}\textnormal{-}R})^{\mathcal{B}}. Our applications include a generalization of a result by Gruson-Jensen and Enochs on pure injective envelopes of flat modules.     

Latin trades in groups defined on planar triangulations

For a finite triangulation of the plane with faces properly coloured white and black, let A_W\mathcal{A}_{W} be the abelian group constructed by labelling the vertices with commuting indeterminates and adding relations which say that the labels around each white triangle add to the identity. We show that A_W\mathcal{A}_{W} has free rank exactly two. Let A_W^*\mathcal{A}_{W}^{*} be the torsion subgroup of  A_W\mathcal{A}_{W} , and A_B^*\mathcal{A}_{B}^{*} the corresponding group for the black triangles. We show that A_W^*\mathcal{A}_{W}^{*} and A_B^*\mathcal{A}_{B}^{*} have the same order, and conjecture that they are isomorphic. For each spherical latin trade W, we show there is a unique disjoint mate B such that (W,B) is a connected and separated bitrade. The bitrade (W,B) is associated with a two-colourable planar triangulation and we show that W can be embedded in  A_W^*\mathcal{A}_{W}^{*} , thereby proving a conjecture due to Cavenagh and Drápal. The proof involves constructing a (0,1) presentation matrix whose permanent and determinant agree up to sign. The Smith normal form of this matrix determines A_W^*\mathcal{A}_{W}^{*} , so there is an efficient algorithm to construct the embedding. Contrasting with the spherical case, for each genus g≥1 we construct a latin trade which is not embeddable in any group and another that is embeddable in a cyclic group.     

Piercing Numbers for Balanced and Unbalanced Families

Given a finite family F\mathcal{F} of convex sets in ℝ ^d , we say that F\mathcal{F} has the (p,q) _r property if for any p convex sets in F\mathcal{F} there are at least r q-tuples that have nonempty intersection. The piercing number of F\mathcal{F} is the minimum number of points we need to intersect all the sets in F\mathcal{F}. In this paper we will find some bounds for the piercing number of families of convex sets with (p,q) _r properties.     

A$\mathcal{T}$-algebras and extensions of A$\mathbb{T}$-algebras

Lin and Su classified A$ \mathcal{T} $ \mathcal{T} -algebras of real rank zero. This class includes all A$ \mathbb{T} $ \mathbb{T} -algebras of real rank zero as well as many C*-algebras which are not stably finite. An A$ \mathcal{T} $ \mathcal{T} -algebra often becomes an extension of an A$ \mathbb{T} $ \mathbb{T} -algebra by an AF-algebra. In this paper, we show that there is an essential extension of an A$ \mathbb{T} $ \mathbb{T} -algebra by an AF-algebra which is not an A$ \mathcal{T} $ \mathcal{T} -algebra. We describe a characterization of an extension E of an A$ \mathbb{T} $ \mathbb{T} -algebra by an AF-algebra if E is an A$ \mathcal{T} $ \mathcal{T} -algebra.     

A generalization of Mathieu subspaces to modules of associative algebras

We first propose a generalization of the notion of Mathieu subspaces of associative algebras $ \mathcal{A} $ \mathcal{A} , which was introduced recently in [Zhao W., Generalizations of the image conjecture and the Mathieu conjecture, J. Pure Appl. Algebra, 2010, 214(7), 1200–1216] and [Zhao W., Mathieu subspaces of associative algebras], to $ \mathcal{A} $ \mathcal{A} -modules $ \mathcal{M} $ \mathcal{M} . The newly introduced notion in a certain sense also generalizes the notion of submodules. Related with this new notion, we also introduce the sets σ(N) and τ(N) of stable elements and quasi-stable elements, respectively, for all R-subspaces N of $ \mathcal{A} $ \mathcal{A} -modules $ \mathcal{M} $ \mathcal{M} , where R is the base ring of $ \mathcal{A} $ \mathcal{A} . We then prove some general properties of the sets σ(N) and τ(N). Furthermore, examples from certain modules of the quasi-stable algebras [Zhao W., Mathieu subspaces of associative algebras], matrix algebras over fields and polynomial algebras are also studied.     

Platonic polyhedra,topological constraints and periodic solutions of the classical <Emphasis Type="Italic">N</Emphasis>-body problem

We prove the existence of a number of smooth periodic motions u _∗ of the classical Newtonian N-body problem which, up to a relabeling of the N particles, are invariant under the rotation group R\mathcal{R} of one of the five Platonic polyhedra. The number N coincides with the order |R||\mathcal{R}| of R\mathcal{R} and the particles have all the same mass. Our approach is variational and u _∗ is a minimizer of the Lagrangian action A\mathcal{A} on a suitable subset K\mathcal{K} of the H ¹ T-periodic maps u:ℝ→ℝ^3N . The set K{\mathcal {K}} is a cone and is determined by imposing on u both topological and symmetry constraints which are defined in terms of the rotation group R\mathcal{R}. There exist infinitely many such cones K{\mathcal {K}}, all with the property that A|_K{\mathcal {A}}|_{{\mathcal {K}}} is coercive. For a certain number of them, using level estimates and local deformations, we show that minimizers are free of collisions and therefore classical solutions of the N-body problem with a rich geometric–kinematic structure.     

Some properties for the largest component of random geometric graphs with applications in sensor networks

In this paper we consider the standard Poisson Boolean model of random geometric graphs G（Hλ,s; 1） in Rd and study the properties of the order of the largest component L1 （G（Hλ,s; 1）） . We prove that ElL1 （G（Hλ,s; 1））] is smooth with respect to A, and is derivable with respect to s. Also, we give the expression of these derivatives. These studies provide some new methods for the theory of the largest component of finite random geometric graphs （not asymptotic graphs as s - co） in the high dimensional space （d 〉 2）. Moreover, we investigate the convergence rate of E[L1（G（Hλ,s; 1））]. These results have significance for theory development of random geometric graphs and its practical application. Using our theories, we construct and solve a new optimal energy-efficient topology control model of wireless sensor networks, which has the significance of theoretical foundation and guidance for the design of network layout.     

Tensoring with Infinite-Dimensional Modules in $\mathcal {O}_0$

We show that the principal block O₀\mathcal {O}_0 of the BGG category O\mathcal {O} for a semisimple Lie algebra \frak g\frak g acts faithfully on itself via exact endofunctors which preserve tilting modules, via right exact endofunctors which preserve projective modules and via left exact endofunctors which preserve injective modules. The origin of all these functors is tensoring with arbitrary (not necessarily finite-dimensional) modules in the category O\mathcal {O}. We study such functors, describe their adjoints and show that they give rise to a natural (co)monad structure on O₀\mathcal {O}_0. Furthermore, all this generalises to parabolic subcategories of O₀\mathcal {O}_0. As an example, we present some explicit computations for the algebra \fraksl₃\frak{sl}_3.     

Computing compatible tours for the symmetric traveling salesman problem

We consider the following natural heuristic for the Symmetric Traveling Salesman Problem: solve the subtour relaxation, yielding a solution x*, and then find the best tour [`(x)]{\bar x} that is compatible with x*, where compatible means that every subtour elimination constraint that is satisfied at equality at x* is also satisfied at equality at [`(x)]{\bar x}. We prove that finding the best compatible tour is NP{\mathcal{NP}}-hard and show that the tour can have a cost approaching 5/3 that of the optimal tour. We then describe a branch-and-cut algorithm for computing the best compatible tour, and present extensive computational results for TSPLIB instances. It turns out that, in practice, the tour is usually of very good quality. Moreover, the computational effort for computing the compatible tour is considerably smaller than that of solving the full problem with the best available software, i.e., Concorde.     

Two complexity results on c-optimality in experimental design

Finding a c-optimal design of a regression model is a basic optimization problem in statistics. We study the computational complexity of the problem in the case of a finite experimental domain. We formulate a decision version of the problem and prove its NP\boldsymbol{\mathit{NP}}-completeness. We provide examples of computationally complex instances of the design problem, motivated by cryptography. The problem, being NP\boldsymbol{\mathit{NP}}-complete, is then relaxed; we prove that a decision version of the relaxation, called approximate c-optimality, is P-complete. We derive an equivalence theorem for linear programming: we show that the relaxed c-optimality is equivalent (in the sense of many-one LOGSPACE-reducibility) to general linear programming.