On body shapes providing maximum depth of penetration

The problem of maximization of the depth of penetration of rigid impactor into semi-infinite solid media (concrete shield) is investigated analytically and numerically using two-stage model and experimental data of Forrestal and Tzou (Int J Solids Struct 34(31–32):4127–4146, 1997). The shape of the axisymmetric rigid impactor has been taken as an unknown design variable. To solve the formulated optimization problem for nonadditive functional, we expressed the depth of penetration (DOP) under some isoperimetric constraints. We apply approaches based on analytical and qualitative variational methods and numerical optimization algorithm of global search. Basic attention for considered optimization problem was given to constraints on the mass of penetrated bodies, expressed by the volume in the case of penetrated solid body and by the surface area in the case of penetrated thin-walled rigid shell. As a result of performed investigation, based on two-term and three-term two stage models proposed by Forrestal et al. (Int J Impact Eng 15(4):396–405, 1994), Forrestal and Tzou (Int J Solids Struct 34(31–32):4127–4146, 1997) and effectively developed by Ben-Dor et al. (Comp Struct 56:243–248, 2002, Comput Struct 81(1):9–14, 2003a, Int J Solids Struct 40(17):4487–4500, 2003b, Mech Des Struct Mach 34(2): 139–156, 2006), we found analytical and numerical solutions and analyzed singularities of optimal forms.     

On Total Variation Minimization and Surface Evolution Using Parametric Maximum Flows

In a recent paper Boykov et al. (LNCS, Vol. 3953, pp. 409–422, 2006) propose an approach for computing curve and surface evolution using a variational approach and the geo-cuts method of Boykov and Kolmogorov (International conference on computer vision, pp. 26–33, 2003). We recall in this paper how this is related to well-known approaches for mean curvature motion, introduced by Almgren et al. (SIAM Journal on Control and Optimization 31(2):387–438, 1993) and Luckhaus and Sturzenhecker (Calculus of Variations and Partial Differential Equations 3(2):253–271, 1995), and show how the corresponding problems can be solved with sub-pixel accuracy using Parametric Maximum Flow techniques. This provides interesting algorithms for computing crystalline curvature motion, possibly with a forcing term. A. Chambolle’s research supported by ANR project “MICA”, grant ANR-08-BLAN-0082. J. Darbon’s research supported by ONR grant N000140710810.     

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n ⁵) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n ¹¹) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong.     

On the air damping of flexible microbeam in free space at the free-molecule regime

Predicting air damping is crucial in the design of high Q microelectromechanical systems. In the past, air damping of rigid microbeam in free space at molecular regime is usually estimated using the free molecular model proposed by Christian (Vacuum 16:175–178, 1966), air damping of flexible microbeam is estimated using the model proposed by Blom (J Vac Sci Technol B 10:19–26, 1992). The relation between the two models is Q _Blom = 3Q _Christian. In this paper, a general proof is presented that shows the Christian’s model is valid for the air damping of flexible microbeam in free space at molecular regime. By comparing with the experimental results available in the literatures (Blom et al. in J Vac Sci Technol B 10:19–26, 1992; Yasumura et al. in J Micromech Syst 9:117–125, 2000), we conclude that the Christian’s model is the best choice in predicting the air damping of flexible microbeam in free space at the molecular regime.     

High Order Extensions of Roe Schemes for Two-Dimensional Nonconservative Hyperbolic Systems

This paper is concerned with the development of well-balanced high order Roe methods for two-dimensional nonconservative hyperbolic systems. In particular, we are interested in extending the methods introduced in (Castro et al., Math. Comput. 75:1103–1134, 2006) to the two-dimensional case. We also investigate the well-balance properties and the consistency of the resulting schemes. We focus in applications to one and two layer shallow water systems.     

Linear Time Algorithms for Exact Distance Transform

In 2003, Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) published a paper describing an algorithm that computes the exact distance transform in linear time (with respect to image size) for the rectangular binary images in the k-dimensional space ℝ ^k and distance measured with respect to L _p -metric for 1≤p≤∞, which includes Euclidean distance L ₂. In this paper we discuss this algorithm from theoretical and practical points of view. On the practical side, we concentrate on its Euclidean distance version, discuss the possible ways of implementing it as signed distance transform, and experimentally compare implemented algorithms. We also describe the parallelization of these algorithms and discuss the computational time savings associated with them. All these implementations will be made available as a part of the CAVASS software system developed and maintained in our group (Grevera et al. in J. Digit. Imaging 20:101–118, 2007). On the theoretical side, we prove that our version of the signed distance transform algorithm, GBDT, returns the exact value of the distance from the geometrically defined object boundary. We provide a complete proof (which was not given of Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) that all these algorithms work correctly for L _p -metric with 1<p<∞. We also point out that the precise form of the algorithm from Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) is not well defined for L ₁ and L _∞ metrics. In addition, we show that the algorithm can be used to find, in linear time, the exact value of the diameter of an object, that is, the largest possible distance between any two of its elements.     

Ontology-driven coordination model for multiagent-based mobile workforce brokering systems

Coordination has been recognized by many researchers as the most important feature of multi-agent systems. Coordination is defined as managing interdependencies amongst activities (Malone and Crowston in ACM Comput. Surv. 26(1):87–119, 1994). The traditional approach of implementing a coordination mechanism is to hard-wire it into a coordination system at design time. However, in dynamic and open environments, many attributes of the system cannot be accurately identified at the design time. Therefore, dynamic coordination, capable of coordinating activities at run-time, has emerged. On the other hand, a successful dynamic coordination model for multi-agent systems requires knowledge sharing as well as common vocabulary. Therefore, an ontological approach is an appropriate way in proposing dynamic coordination models for multi-agent systems. In this paper, an Ontology-Driven Dynamic Coordination Model (O-DC) for Multiagent-Based Mobile Workforce Brokering Systems (MWBS) (Mousavi et al. in Int. J. Comput. Sci. 6:(5):557–565, 2010; Mousavi et al. in Proceedings of 4th IEEE international symposium on information technology, ITSim’10, Kuala Lumpur, Malaysia, 15–17 June 2010, vol. 3, pp. 1416–1421, 2010; Mousavi and Nordin in Proceedings of the IEEE international conference on electrical engineering and informatics, Bandung, Indonesia, 17–19 June 2007, pp. 294–297, 2007) is proposed and formulated. Subsequently, the applicability of O-DC is examined via simulation based on a real-world scenario.     

On the Planar Piecewise Quadratic 1-Center Problem

In this paper we introduce a minimax model unifying several classes of single facility planar center location problems. We assume that the transportation costs of the demand points to the serving facility are convex functions {Q _i }, i=1,…,n, of the planar distance used. Moreover, these functions, when properly transformed, give rise to piecewise quadratic functions of the coordinates of the facility location. In the continuous case, using results on LP-type models by Clarkson (J. ACM 42:488–499, 1995), Matoušek et al. (Algorithmica 16:498–516, 1996), and the derandomization technique in Chazelle and Matoušek (J. Algorithms 21:579–597, 1996), we claim that the model is solvable deterministically in linear time. We also show that in the separable case, one can get a direct O(nlog n) deterministic algorithm, based on Dyer (Proceedings of the 8th ACM Symposium on Computational Geometry, 1992), to find an optimal solution. In the discrete case, where the location of the center (server) is restricted to some prespecified finite set, we introduce deterministic subquadratic algorithms based on the general parametric approach of Megiddo (J. ACM 30:852–865, 1983), and on properties of upper envelopes of collections of quadratic arcs. We apply our methods to solve and improve the complexity of a number of other location problems in the literature, and solve some new models in linear or subquadratic time complexity.     

A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration

In this paper, we propose a unified primal-dual algorithm framework for two classes of problems that arise from various signal and image processing applications. We also show the connections to existing methods, in particular Bregman iteration (Osher et al., Multiscale Model. Simul. 4(2):460–489, 2005) based methods, such as linearized Bregman (Osher et al., Commun. Math. Sci. 8(1):93–111, 2010; Cai et al., SIAM J. Imag. Sci. 2(1):226–252, 2009, CAM Report 09-28, UCLA, March 2009; Yin, CAAM Report, Rice University, 2009) and split Bregman (Goldstein and Osher, SIAM J. Imag. Sci., 2, 2009). The convergence of the general algorithm framework is proved under mild assumptions. The applications to ℓ ¹ basis pursuit, TV−L ² minimization and matrix completion are demonstrated. Finally, the numerical examples show the algorithms proposed are easy to implement, efficient, stable and flexible enough to cover a wide variety of applications.     

The effects of scent and game play experience on memory of a virtual environment

Scent has been well documented as having significant effects on emotion (Alaoui-Ismaili in Physiol Behav 62(4):713–720, 1997; Herz et al. in Motiv Emot 28(4):363–383, 2004), learning (Smith et al. in Percept Mot Skills 74(2):339–343, 1992; Morgan in Percept Mot Skills 83(3)(2):1227–1234, 1996), memory (Herz in Am J Psychol 110(4):489–505, 1997) and task performance (Barker et al. in Percept Mot Skills 97(3)(1):1007–1010, 2003). This paper describes an experiment in which environmentally appropriate scent was presented as an additional sensory modality consistent with other aspects of a virtual environment called DarkCon. Subjects’ game play habits were recorded as an additional factor for analysis. Subjects were randomly assigned to receive scent during the VE, and/or afterward during a task of recall of the environment. It was hypothesized that scent presentation during the VE would significantly improve recall, and that subjects who were presented with scent during the recall task, in addition to experiencing the scented VE, would perform the best on the recall task. Skin-conductance was a significant predictor of recall, over and above experimental groups. Finally, it was hypothesized that subjects’ game play habits would affect both their behavior in and recall of the environment. Results are encouraging to the use of scent in virtual environments, and directions for future research are discussed. The project described herein has been sponsored by the US Army Research, Development, and Engineering Command (RDECOM). Statements and opinions expressed do not necessarily reflect the position or the policy of the US Government; no official endorsement should be inferred.     

A New Mapped Weighted Essentially Non-oscillatory Scheme

The weighted essentially non-oscillatory (WENO) methods are a popular high-order spatial discretization for hyperbolic partial differential equations. Recently Henrick et al. (J. Comput. Phys. 207:542–567, 2005) noted that the fifth-order WENO method by Jiang and Shu (J. Comput. Phys. 126:202–228, 1996) is only third-order accurate near critical points of the smooth regions in general. Using a simple mapping function to the original weights in Jiang and Shu (J. Comput. Phys. 126:202–228, 1996), Henrick et al. developed a mapped WENO method to achieve the optimal order of accuracy near critical points. In this paper we study the mapped WENO scheme and find that, when it is used for solving the problems with discontinuities, the mapping function in Henrick et al. (J. Comput. Phys. 207:542–567, 2005) may amplify the effect from the non-smooth stencils and thus cause a potential loss of accuracy near discontinuities. This effect may be difficult to be observed for the fifth-order WENO method unless a long time simulation is desired. However, if the mapping function is applied to seventh-order WENO methods (Balsara and Shu in J. Comput. Phys. 160:405–452, 2000), the error can increase much faster so that it can be observed with a moderate output time. In this paper a new mapping function is proposed to overcome this potential loss of accuracy.     

A note on double splittings of different monotone matrices

Comparison theorems between the spectral radii of different matrices are a useful tool for judging the efficiency of preconditioners. For single splittings of different monotone matrices, Elsner et al. (Linear Algebra Appl. 363:65–80, 2003) gave out comparison theorems for spectral radii. For double splittings, some convergence and comparison theorems of a monotone matrix are presented by Shen et al. (Comput. Math. Appl. 51:1751–1760, 2006). In this note we give the comparison theorem for the spectral radii of matrices arising from double splittings of different monotone matrices.     

Efficient RNTS system for privacy of banking off-line customer

With the development in IT technology and with growing demands of users, a ubiquitous environment is being made. Because individual identification is important in ubiquitous environment, RFID technology would be used frequently. RFID is a radio frequency identification technology to replace bar code. The reader transmits query (request of user information) and tag-provides user information. RFID has various advantages, such as high speed identification rates, mass memory storages. However, eavesdropping is possible as well as a problem that user information is exposed (Juels et al. in Conference on Computer and Communications Security—ACM CCS, pp. 103–111, 2003; Ohkubo et al. in RFID Privacy Workshop 2003; Weis et al. in International Conference on Security in Pervasive Computing, pp. 201–212, 2003; Weis et al. in Cryptographic Hardware and Embedded Systems—CHES, pp. 454–469, 2002). Therefore, when off-line customer had visited bank for banking service, RNTS (RFID number ticket service) system provides both anonymity in customer identification and efficiency of banking service. In addition, RNTS system protects privacy of an off-line user visiting the bank and it is an efficient method offering service in order of arriving in the bank.     

Finding Total Unimodularity in Optimization Problems Solved by Linear Programs

A popular approach in combinatorial optimization is to model problems as integer linear programs. Ideally, the relaxed linear program would have only integer solutions, which happens for instance when the constraint matrix is totally unimodular. Still, sometimes it is possible to build an integer solution with the same cost from the fractional solution. Examples are two scheduling problems (Baptiste and Schieber, J. Sched. 6(4):395–404, 2003; Brucker and Kravchenko, J. Sched. 11(4):229–237, 2008) and the single disk prefetching/caching problem (Albers et al., J. ACM 47:969–986, 2000). We show that problems such as the three previously mentioned can be separated into two subproblems: (1) finding an optimal feasible set of slots, and (2) assigning the jobs or pages to the slots. It is straigthforward to show that the latter can be solved greedily. We are able to solve the former with a totally unimodular linear program, from which we obtain simple combinatorial algorithms with improved worst case running time.     

Feature subset selection based on fuzzy entropy measures for handling classification problems

In this paper, we present a new method for dealing with feature subset selection based on fuzzy entropy measures for handling classification problems. First, we discretize numeric features to construct the membership function of each fuzzy set of a feature. Then, we select the feature subset based on the proposed fuzzy entropy measure focusing on boundary samples. The proposed method can select relevant features to get higher average classification accuracy rates than the ones selected by the MIFS method (Battiti, R. in IEEE Trans. Neural Netw. 5(4):537–550, 1994), the FQI method (De, R.K., et al. in Neural Netw. 12(10):1429–1455, 1999), the OFEI method, Dong-and-Kothari’s method (Dong, M., Kothari, R. in Pattern Recognit. Lett. 24(9):1215–1225, 2003) and the OFFSS method (Tsang, E.C.C., et al. in IEEE Trans. Fuzzy Syst. 11(2):202–213, 2003).

Hybrid WENO schemes for polydisperse sedimentation models

Polydisperse sedimentation models can be described by a strongly coupled system of conservation laws for the concentration of each species of solids. Typical solutions for the sedimentation model considered for batch settling in a column include stationary kinematic shocks separating layers of sediment of different composition. This phenomenon, known as segregation of species, is a specially demanding task for numerical simulation due to the need of accurate numerical simulations. Very high-order accurate solutions can be constructed by incorporating characteristic information, available due to the hyperbolicity analysis made in Donat and Mulet [A secular equation for the Jacobian matrix of certain multispecies kinematic flow models, Numer. Methods Partial Differential Equations 26 (2010), pp. 159–175.] But characteristic-based schemes, see Bürger et al. [On the implementation of WENO schemes for a class of polydisperse sedimentation models, J. Comput. Phys. 230 (2011), pp. 2322–2344], are very expensive in terms of computational time, since characteristic information is not readily available, and they are not really necessary in constant areas, where a less complex method can obtain similar results. With this idea in mind, in this paper we develop a hybrid finite difference WENO scheme that only uses the characteristic information of the Jacobian matrix of the system in those regions where singularities exist or are starting to develop, while it uses a component-wise approximation of the scheme in smooth regions. We perform some experiments showing the computational gains that can be achieved by this strategy.     

Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.     

Linearly implicit schemes for a class of dispersive–dissipative systems

We consider initial value problems for semilinear parabolic equations, which possess a dispersive term, nonlocal in general. This dispersive term is not necessarily dominated by the dissipative term. In our numerical schemes, the time discretization is done by linearly implicit schemes. More specifically, we discretize the initial value problem by the implicit–explicit Euler scheme and by the two-step implicit–explicit BDF scheme. In this work, we extend the results in Akrivis et al. (Math. Comput. 67:457–477, 1998; Numer. Math. 82:521–541, 1999), where the dispersive term (if present) was dominated by the dissipative one and was integrated explicitly. We also derive optimal order error estimates. We provide various physically relevant applications of dispersive–dissipative equations and systems fitting in our abstract framework.     

A face emotion tree structure representation with probabilistic recursive neural network modeling

This paper describes a novel structural approach to recognize the human facial features for emotion recognition. Conventionally, features extracted from facial images are represented by relatively poor representations, such as arrays or sequences, with a static data structure. In this study, we propose to extract facial expression features vectors as Localized Gabor Features (LGF) and then transform these feature vectors into FacE Emotion Tree Structures (FEETS) representation. It is an extension of the Human Face Tree Structures (HFTS) representation presented in (Cho and Wong in Lecture notes in computer science, pp 1245–1254, 2005). This facial representation is able to simulate as human perceiving the real human face and both the entities and relationship could contribute to the facial expression features. Moreover, a new structural connectionist architecture based on a probabilistic approach to adaptive processing of data structures is presented. The so-called probabilistic based recursive neural network (PRNN) model extended from Frasconi et al. (IEEE Trans Neural Netw 9:768–785, 1998) is developed to train and recognize human emotions by generalizing the FEETS representation. For empirical studies, we benchmarked our emotion recognition approach against other well known classifiers. Using the public domain databases, such as Japanese Female Facial Expression (JAFFE) (Lyons et al. in IEEE Trans Pattern Anal Mach Intell 21(12):1357–1362, 1999; Lyons et al. in third IEEE international conference on automatic face and gesture recognition, 1998) database and Cohn–Kanade AU-Coded Facial Expression (CMU) Database (Cohn et al. in 7th European conference on facial expression measurement and meaning, 1997), our proposed system might obtain an accuracy of about 85–95% for subject-dependent and subject-independent conditions. Moreover, by testing images having artifacts, the proposed model significantly supports the robust capability to perform facial emotion recognition.     

Model Checking Weighted Integer Reset Timed Automata

Weighted timed automata (WTA), introduced in Alur et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 49–62, Springer, Berlin, 2001), Behrmann et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 147–161, Springer, Berlin, 2001) are an extension of Alur and Dill (Theor. Comput. Sci. 126(2):183–235, 1994) timed automata, a widely accepted formalism for the modelling and verification of real time systems. Weighted timed automata extend timed automata by allowing costs on the locations and edges. There has been a lot of interest Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006), Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008), Brihaye et al. (Proceedings of FORMATS/FTRTFT’04, LNCS, vol. 3253, pp. 277–292, Springer, Berlin, 2004), Brihaye et al. (Inf. Comput. 204(3):408–433, 2006) in studying the model checking problem of weighted timed automata. The properties of interest are written using logic weighted CTL (WCTL), an extension of CTL with costs. It has been shown Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008) that the problem of model checking WTAs with a single clock using WCTL with no external cost variables is decidable, while 3 clocks render the problem undecidable Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006). The question of 2 clocks is open. In this paper, we introduce a subclass of weighted timed automata called weighted integer reset timed automata (WIRTA) and study the model checking problem. We give a clock reduction technique for WIRTA. Given a WIRTA A\mathcal{A} with n≥1 clocks, we show that a single clock WIRTA A￠\mathcal{A}' preserving the paths and costs of A\mathcal{A} can be obtained. This gives us the decidability of model checking WIRTA with n≥1 clocks and m≥1 costs using WCTL with no external cost variables. We then show that for a restricted version of WCTL with external cost variables, the model checking problem is undecidable for WIRTA with 3 stopwatch costs and 1 clock. Finally, we show that model checking WTA with 2 clocks and 1 stopwatch cost against WCTL with no external cost variables is undecidable, thereby answering a question that has remained long open.