A Tailored Finite Point Method for a Singular Perturbation Problem on an Unbounded Domain

In this paper, we propose a tailored-finite-point method for a kind of singular perturbation problems in unbounded domains. First, we use the artificial boundary method (Han in Frontiers and Prospects of Contemporary Applied Mathematics, [2005]) to reduce the original problem to a problem on bounded computational domain. Then we propose a new approach to construct a discrete scheme for the reduced problem, where our finite point method has been tailored to some particular properties or solutions of the problem. From the numerical results, we find that our new methods can achieve very high accuracy with very coarse mesh even for very small ε. In the contrast, the traditional finite element method does not get satisfactory numerical results with the same mesh. Han was supported by the NSFC Project No. 10471073. Z. Huang was supported by the NSFC Projects No. 10301017, and 10676017, the National Basic Research Program of China under the grant 2005CB321701. R.B. Kellogg was supported by the Boole Centre for Research in Informatics at National University of Ireland, Cork and by Science Foundation Ireland under the Basic Research Grant Programme 2004 (Grants 04/BR/M0055, 04/BR/M0055s1).     

Tractable cases of the extended global cardinality constraint

We study the consistency and domain consistency problem for extended global cardinality (EGC) constraints. An EGC constraint consists of a set X of variables, a set D of values, a domain D(x) í DD(x) \subseteq D for each variable x, and a “cardinality set” K(d) of non-negative integers for each value d. The problem is to instantiate each variable x with a value in D(x) such that for each value d, the number of variables instantiated with d belongs to the cardinality set K(d). It is known that this problem is NP-complete in general, but solvable in polynomial time if all cardinality sets are intervals. First we pinpoint connections between EGC constraints and general factors in graphs. This allows us to extend the known polynomial-time case to certain non-interval cardinality sets. Second we consider EGC constraints under restrictions in terms of the treewidth of the value graph (the bipartite graph representing variable-value pairs) and the cardinality-width (the largest integer occurring in the cardinality sets). We show that EGC constraints can be solved in polynomial time for instances of bounded treewidth, where the order of the polynomial depends on the treewidth. We show that (subject to the complexity theoretic assumption  FPT ≠ W[1]) this dependency cannot be avoided without imposing additional restrictions. If, however, also the cardinality-width is bounded, this dependency gets removed and EGC constraints can be solved in linear time.     

Some notes on maximal arc intersection of spherical polygons: its \mathcal{NP} -hardness and approximation algorithms

Finding a sequence of workpiece orientations such that the number of setups is minimized is an important optimization problem in manufacturing industry. In this paper we present some interesting notes on this optimal workpiece setup problem. These notes show that (1) The greedy algorithm proposed in Comput. Aided Des. 35 (2003), pp. 1269–1285 for the optimal workpiece setup problem has the performance ratio bounded by O(ln n−ln ln n+0.78), where n is the number of spherical polygons in the ground set; (2) In addition to greedy heuristic, linear programming can also be used as a near-optimal approximation solution; (3) The performance ratio by linear programming is shown to be tighter than that of greedy heuristic in some cases.     

Bounded Model Checking for Timed Automata

Given a timed automaton M, a linear temporal logic formula φ, and a bound k, bounded model checking for timed automata determines if there is a falsifying path of length k to the hypothesis that M satisfies the specification φ. This problem can be reduced to the satisfiability problem for Boolean constraint formulas over linear arithmetic constraints. We show that bounded model checking for timed automata is complete, and we give lower and upper bounds for the length k of counterexamples. Moreover, we define bounded model checking for networks of timed automata in a compositional way.     

A constructive approach to constrained hexahedral mesh generation

Mitchell proved that a necessary and sufficient condition for the existence of a topological hexahedral mesh constrained to a quadrilateral mesh on the sphere is that the constraining quadrilateral mesh contains an even number of elements. Mitchell’s proof depends on Smale’s theorem on the regularity of curves on compact manifolds. Although the question of the existence of constrained hexahedral meshes has been solved, the known solution is not easily programmable; indeed, there are cases, such as Schneider’s Pyramid, that are not easily solved. Eppstein later utilized portions of Mitchell’s existence proof to demonstrate that hexahedral mesh generation has linear complexity. In this paper, we demonstrate a constructive proof to the existence theorem for the sphere, as well as assign an upper-bound to the constant of the linear term in the asymptotic complexity measure provided by Eppstein. Our construction generates 76 × n hexahedra elements within the solid where n is the number of quadrilaterals on the boundary. The construction presented is used to solve some problems posed by Schneiders and Eppstein. We will also use the results provided in this paper, in conjunction with Mitchell’s Geode-Template, to create an alternative way of creating a constrained hexahedral mesh. The construction utilizing the Geode-Template requires 130 × n hexahedra, but will have fewer topological irregularities in the final mesh.     

Some topological and combinatorial properties of WK-recursive mesh and WK-pyramid interconnection networks

The WK-recursive mesh and WK-pyramid networks are recursively defined hierarchical interconnection networks with excellent properties which well idealize them as alternatives for mesh and traditional pyramid interconnection topologies. They have received much attention due to their favorable attributes such as small diameter, large connectivity, and high degree of scalability and expandability. In this paper, we deal with pancyclicity and surface area of these networks. These properties are of great importance in the implementation of a variety of parallel algorithms in multicomputers. We show that WK-recursive mesh network is 1-partially pancyclic, i.e. any cycle of length 3, 4, 6,…, and N can be constructed in the WK-recursive mesh. Also, we prove that the WK-pyramid is pancyclic, that is all cycles of length 3, 4, … , and N can be formed in a WK-pyramid. It is also proved that two link-disjoint Hamiltonian paths/cycles can be embedded in the WK-recursive mesh/WK-pyramid. We then study the surface area of WK-recursive mesh and WK-pyramid networks and put forth some equations for calculating the surface area in these networks.     

Routing on Meshes with Buses

We consider the problem of routing packets on an MIMD mesh-connected array of processors augmented with row and column buses. We give lower bounds and randomized algorithms for the problem of routing k-permutations (where each processor is the source and destination of exactly k packets) on a d-dimensional mesh with buses, which we call the (k,d)-routing problem. We give a general class of ``hard' permutations which we use to prove lower bounds for the (k,d)-routing problem, for all k,d≥ 1. For the (1,1)- and (1,2)-routing problems the worst-case permutations from this class are identical to ones published by other authors, as are the resulting lower bounds. However, we further show that the (1,d)-routing problem requires 0.72 ... n steps for d=3, 0.76 ... n steps for d=4, and slightly more than steps for all d≥ 5. We also obtain new lower bounds for the (k,d)-routing problem for k,d > 1, which improve on the bisection lower bound in some cases. These lower bounds hold for off-line routing as well. We develop efficient algorithms for the (k,1)-routing problem and for the problem of routing k-randomizations (where each processor has k packets initially and each packet is routed to a random destination) on the one-dimensional mesh and use them in a general (k,d)-routing algorithm which improves considerably on previous results. In particular, the routing time for the (1,d)-routing problem is bounded by steps with high probability (whp), whenever for some constant ε > 0, and the routing time for the (k,d)-routing problem is steps whp whenever for some constant ε > 0 and k≥ 3.6 ... d, matching the bisection lower bound. We then present a simple algorithm for the (2,2)-routing problem running in 1.39 ... n+o(n) steps whp. Finally, for the important special case of routing permutations on two-dimensional meshes with buses, the (1,2)-routing problem, we give a more sophisticated algorithm that runs in 0.78 ... n+o(n) steps whp. Received May 18, 1994; revised June 23, 1995.     

Additive Schwarz with aggregation-based coarsening for elliptic problems with highly variable coefficients

Summary We develop a new coefficient-explicit theory for two-level overlapping domain decomposition preconditioners with non-standard coarse spaces in iterative solvers for finite element discretisations of second-order elliptic problems. We apply the theory to the case of smoothed aggregation coarse spaces introduced by Vanek, Mandel and Brezina in the context of algebraic multigrid (AMG) and are particularly interested in the situation where the diffusion coefficient (or the permeability) α is highly variable throughout the domain. Our motivating example is Monte Carlo simulation for flow in rock with permeability modelled by log–normal random fields. By using the concept of strong connections (suitably adapted from the AMG context) we design a two-level additive Schwarz preconditioner that is robust to strong variations in α as well as to mesh refinement. We give upper bounds on the condition number of the preconditioned system which do not depend on the size of the subdomains and make explicit the interplay between the coefficient function and the coarse space basis functions. In particular, we are able to show that the condition number can be bounded independent of the ratio of the two values of α in a binary medium even when the discontinuities in the coefficient function are not resolved by the coarse mesh. Our numerical results show that the bounds with respect to the mesh parameters are sharp and that the method is indeed robust to strong variations in α. We compare the method to other preconditioners and to a sparse direct solver.      

On bounded lattices satisfying Elkan’s law

In this short paper we shall prove that every bounded lattice L with the conditions: (c1) 1′ =  0 and (EL): (a · b′)′ =  b +  a′ · b′ for all a, b ∈ L is a Boolean algebra. This is a more general result than that of Renedo et al. (Proceedings NAFIPS’04, 2004), in which it is proved that every orthocomplemented lattice with (EL) is a Boolean algebra.     

Improved Parameterized Set Splitting Algorithms: A Probabilistic Approach

In this paper, we study parameterized algorithms for the set splitting problem, for both weighted and unweighted versions. First, we develop a new and effective technique based on a probabilistic method that allows us to develop a simpler and more efficient deterministic kernelization algorithm for the unweighted set splitting problem. We then propose a randomized algorithm for the weighted set splitting problem that is based on a new subset partition technique and has its running time bounded by O ^*(2 ^k ), which is significantly better than that of the previous best deterministic algorithm (which only works for the simpler unweighted set splitting problem) of running time O ^*(2.65 ^k ). We also show that our algorithm can be de-randomized, which leads to a deterministic parameterized algorithm of running time O ^*(4 ^k ) for the weighted set splitting problem and gives the first proof that the problem is fixed-parameter tractable. A preliminary version of this paper was presented at The 13th Annual International Computing and Combinatorics Conference (COCOON 2007), Banff, Canada, July 2007, LNCS vol. 4598, pp. 537–547. This work was supported in part by the National Science Foundation under the Grant CCF-0430683.     

Fractional Path Coloring in Bounded Degree Trees with Applications

This paper studies the natural linear programming relaxation of the path coloring problem. We prove constructively that finding an optimal fractional path coloring is Fixed Parameter Tractable (FPT), with the degree of the tree as parameter: the fractional coloring of paths in a bounded degree trees can be done in a time which is linear in the size of the tree, quadratic in the load of the set of paths, while exponential in the degree of the tree. We give an algorithm based on the generation of an efficient polynomial size linear program. Our algorithm is able to explore in polynomial time the exponential number of different fractional colorings, thanks to the notion of trace of a coloring that we introduce. We further give an upper bound on the cost of such a coloring in binary trees and extend this algorithm to bounded degree graphs with bounded treewidth. Finally, we also show some relationships between the integral and fractional problems, and derive a 1+5/3e≈1.61—approximation algorithm for the path coloring problem in bounded degree trees, improving on existing results. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (wdm) optical networks.     

Generating well-shaped d-dimensional Delaunay Meshes

A d-dimensional simplicial mesh is a Delaunay triangulation if the circumsphere of each of its simplices does not contain any vertices inside. A mesh is well shaped if the maximum aspect ratio of all its simplices is bounded from above by a constant. It is a long-term open problem to generate well-shaped d-dimensional Delaunay meshes for a given polyhedral domain. In this paper, we present a refinement-based method that generates well-shaped d-dimensional Delaunay meshes for any PLC domain with no small input angles. Furthermore, we show that the generated well-shaped mesh has O(n) d-simplices, where n is the smallest number of d-simplices of any almost-good meshes for the same domain. Here a mesh is almost-good if each of its simplices has a bounded circumradius to the shortest edge length ratio.     

Analysis-suitable volume parameterization of multi-block computational domain in isogeometric applications

Parameterization of the computational domain is a key step in isogeometric analysis just as mesh generation is in finite element analysis. In this paper, we study the volume parameterization problem of the multi-block computational domain in an isogeometric version, i.e., how to generate analysis-suitable parameterization of the multi-block computational domain bounded by B-spline surfaces. Firstly, we show how to find good volume parameterization of the single-block computational domain by solving a constraint optimization problem, in which the constraint condition is the injectivity sufficient conditions of B-spline volume parameterization, and the optimization term is the minimization of quadratic energy functions related to the first and second derivatives of B-spline volume parameterization. By using this method, the resulting volume parameterization has no self-intersections, and the isoparametric structure has good uniformity and orthogonality. Then we extend this method to the multi-block case, in which the continuity condition between the neighbor B-spline volumes should be added to the constraint term. The effectiveness of the proposed method is illustrated by several examples based on the three-dimensional heat conduction problem.     

Resource Allocation in Bounded Degree Trees

We study the bandwidth allocation problem (bap) in bounded degree trees. In this problem we are given a tree and a set of connection requests. Each request consists of a path in the tree, a bandwidth requirement, and a weight. Our goal is to find a maximum weight subset S of requests such that, for every edge e, the total bandwidth of requests in S whose path contains e is at most 1. We also consider the storage allocation problem (sap), in which it is also required that every request in the solution is given the same contiguous portion of the resource in every edge in its path. We present a deterministic approximation algorithm for bap in bounded degree trees with ratio . Our algorithm is based on a novel application of the local ratio technique in which the available bandwidth is divided into narrow strips and requests with very small bandwidths are allocated in these strips. We also present a randomized (2+ε)-approximation algorithm for bap in bounded degree trees. The best previously known ratio for bap in general trees is 5. We present a reduction from sap to bap that works for instances where the tree is a line and the bandwidths are very small. It follows that there exists a deterministic 2.582-approximation algorithm and a randomized (2+ε)-approximation algorithm for sap in the line. The best previously known ratio for this problem is 7. A preliminary version of this paper was presented at the 14th Annual European Symposium on Algorithms (ESA), 2006.     

An Improved Approximation Algorithm for the Traveling Tournament Problem

This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose an approximation algorithm for the traveling tournament problem with the constraints such that both the number of consecutive away games and that of consecutive home games are at most k. When k≤5, the approximation ratio of the proposed algorithm is bounded by (2k−1)/k+O(k/n) where n denotes the number of teams; when k>5, the ratio is bounded by (5k−7)/(2k)+O(k/n). For k=3, the most investigated case of the traveling tournament problem to date, the approximation ratio of the proposed algorithm is 5/3+O(1/n); this is better than the previous approximation algorithm proposed for k=3, whose approximation ratio is 2+O(1/n).     

Constant-Time Tree Algorithms on Reconfigurable Meshes on Size n × n

Recently, an elegant and powerful architecture called the reconfigurable mesh has been proposed in the literature. In essence, a reconfigurable mesh consists of a mesh-connected architecture enhanced by the addition of a dynamic bus system whose configuration changes in response to computational and communication needs. In this paper we show that the reconfigurable mesh architecture can be exploited to yield very simple constant-time algorithms to solve a number of important computational problems involving trees. Specifically, we address the problem of generating the computation tree form of an arithmetic expression, the problem of reconstructing a binary tree from its preorder and inorder traversals, and the problem of reconstructing an ordered forest from its preorder and postorder traversals. We show that with an input of size n, all these problems find constant-time solutions on a reconfigurable mesh of size n × n.     

Robust RHC for wheeled vehicles with bounded disturbances

The robust receding horizon control (RHC) synthesis approach is developed in this paper, for the simultaneous tracking and regulation problem (STRP) of wheeled vehicles with bounded disturbances. Considering the bounded disturbances, we firstly provide a robust positively invariant (RPI) set and associated feedback controller for the perturbed vehicles, which contribute to the foundation of the robust RHC synthesis approach. Then, by extending the tube‐based approach introduced in the article of Mayne et al (robust model predictive control of constrained linear systems with bounded disturbances in Automatica, 2005, vol. 41) to the STRP of wheeled vehicles, we employ the designed RPI set to determine the robust tube and terminal state region, and further construct a nominal optimal control problem. The actual control input is implemented by correcting the solved nominal input with the designed feedback controller. Following the contributed properties of the developed RPI set and extended tube‐based approach, a robust RHC algorithm is finally proposed with the guarantees of recursive feasibility and robust convergence, which can also be adapted for real‐time implementation. Additionally, due to the elaborate control design, the effect of disturbances can be completely nullified to achieve better tracking performance. The effectiveness and advantage of the proposed approach are illustrated by two simulation examples.     

On the isomorphism problem of concept algebras

Weakly dicomplemented lattices are bounded lattices equipped with two unary operations to encode a negation on concepts. They have been introduced to capture the equational theory of concept algebras (Wille 2000; Kwuida 2004). They generalize Boolean algebras. Concept algebras are concept lattices, thus complete lattices, with a weak negation and a weak opposition. A special case of the representation problem for weakly dicomplemented lattices, posed in Kwuida (2004), is whether complete weakly dicomplemented lattices are isomorphic to concept algebras. In this contribution we give a negative answer to this question (Theorem 4). We also provide a new proof of a well known result due to M.H. Stone (Trans Am Math Soc 40:37–111, 1936), saying that each Boolean algebra is a field of sets (Corollary 4). Before these, we prove that the boundedness condition on the initial definition of weakly dicomplemented lattices (Definition 1) is superfluous (Theorem 1, see also Kwuida (2009)).     

On the design of efficient ATM routing schemes

In this paper we deal with the problem of designing virtual path layouts in ATM networks when the hop-count is given and the load has to be minimized. We first prove a lower bound for networks with arbitrary topology and arbitrary set of connection requests. This result is then applied to derive lower bounds for the following settings: (i) one-to-all (one node has to be connected to all other nodes of the network) in arbitrary networks; (ii) all-to-all (each node has to be connected to all other nodes in the network) in several classes of networks, including planar and k-separable networks and networks of bounded genus. We finally study the all-to-all setting on two-dimensional meshes and we design a virtual path layout for this problem. When the hop-count and the network degree are bounded by constants, our results show that the upper bounds proposed in this paper for the one-to-all problem in arbitrary networks and for the all-to-all problem in two-dimensional mesh networks are asymptotically optimal. Moreover, the general lower bound shows that the algorithm proposed in Gerstel (Ph.D. Thesis, Technion-Haifa, Israel, 1995) for the all-to-all problem in k-separable networks is also asymptotically optimal. The upper bound for mesh networks also shows that the lower bound presented in this paper for the all-to-all problem in planar networks is asymptotically tight.     

Trimming of Graphs, with Application to Point Labeling

For t>0 and g≥0, a vertex-weighted graph of total weight W is (t,g)-trimmable if it contains a vertex-induced subgraph of total weight at least (1−1/t)W and with no simple path of more than g edges. A family of graphs is trimmable if for every constant t>0, there is a constant g≥0 such that every vertex-weighted graph in the family is (t,g)-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. We also show that every family of directed graphs of bounded layer bandwidth (a less restrictive condition than bounded directed bandwidth) is trimmable. As an application of these results, we derive polynomial-time approximation schemes for various forms of the problem of labeling a subset of given weighted point features with nonoverlapping sliding axes-parallel rectangular labels so as to maximize the total weight of the labeled features, provided that the ratios of label heights or the ratios of label lengths are bounded by a constant. This settles one of the last major open questions in the theory of map labeling.