Solving steel mill slab design problems

The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. (INFORMS J Comput 18:129–134, 2006). The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. (INFORMS J Comput 18:129–134, 2006) for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results (Schaus et al., Constraints 16:125–147, 2010). Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality.     

Effect of Stochastic Noise on Superior Julia Sets

Julia sets are considered one of the most attractive fractals and have wide range of applications in science and engineering. The strong physical meaning of Mandelbrot and Julia sets is broadly accepted and nicely connected by Christian Beck (Physica D 125(3–4):171–182, 1999) to the complex logistic maps, in the former case, and to the inverse complex logistic map, in the latter. Argyris et al. (Chaos Solitons Fractals 11(13):2067–2073, 2000) have studied the effect of noise on Julia sets and concluded that Julia sets are stable for noises of low strength, and a small increment in the strength of noise may cause considerable deterioration in the configuration of the Julia sets. It is well-known that the method of function iterates plays a crucial role in discrete dynamics utilizing the techniques of fractal theory. However, recently Rani and Kumar (J. Korea Soc. Math. Edu. Ser. D: Res. Math. Edu. 8(4):261–277, 2004) introduced superior iterations as a generalization of function iterations in the study of Julia sets and studied superior Julia sets. This technique is further utilized to study effectively new Mandelbrot sets and related properties (see, for instance, Negi and Rani, Chaos Solitons Fractals 36(2):237–245, 2008; 36(4):1089–1096, 2008, Rani and Kumar, J. Korea Soc. Math. Edu. Ser. D: Res. Math. Edu. 8(4):279–291, 2004). The intent of this paper is to study certain effects of noise on superior Julia sets. We find that the superior Julia sets are drastically more stable for higher strength of noises than the classical Julia sets. Finally, we make a humble attempt to discuss some applications of superior orbit in discrete dynamics and of superior Julia sets in particle dynamics.     

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.     

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.     

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.     

Using Biologically Inspired Features for Face Processing

In this paper, we show that a new set of visual features, derived from a feed-forward model of the primate visual object recognition pathway proposed by Riesenhuber and Poggio (R&P Model) (Nature Neurosci. 2(11):1019–1025, 1999) is capable of matching the performance of some of the best current representations for face identification and facial expression recognition. Previous work has shown that the Riesenhuber and Poggio Model features can achieve a high level of performance on object recognition tasks (Serre, T., et al. in IEEE Comput. Vis. Pattern Recognit. 2:994–1000, 2005). Here we modify the R&P model in order to create a new set of features useful for face identification and expression recognition. Results from tests on the FERET, ORL and AR datasets show that these features are capable of matching and sometimes outperforming other top visual features such as local binary patterns (Ahonen, T., et al. in 8th European Conference on Computer Vision, pp. 469–481, 2004) and histogram of gradient features (Dalal, N., Triggs, B. in International Conference on Computer Vision & Pattern Recognition, pp. 886–893, 2005). Having a model based on shared lower level features, and face and object recognition specific higher level features, is consistent with findings from electrophysiology and functional magnetic resonance imaging experiments. Thus, our model begins to address the complete recognition problem in a biologically plausible way.     

Orientation-Matching Minimization for Image Denoising and Inpainting

In this paper, we propose an orientation-matching functional minimization for image denoising and image inpainting. Following the two-step TV-Stokes algorithm (Rahman et al. in Scale space and variational methods in computer vision, pp. 473–482, Springer, Heidelberg, 2007; Tai et al. in Image processing based on partial differential equations, pp. 3–22, Springer, Heidelberg, 2006; Bertalmio et al. in Proc. conf. comp. vision pattern rec., pp. 355–362, 2001), a regularized tangential vector field with zero divergence condition is first obtained. Then a novel approach to reconstruct the image is proposed. Instead of finding an image that fits the regularized normal direction from the first step, we propose to minimize an orientation matching cost measuring the alignment between the image gradient and the regularized normal direction. This functional yields a new nonlinear partial differential equation (PDE) for reconstructing denoised and inpainted images. The equation has an adaptive diffusivity depending on the orientation of the regularized normal vector field, providing reconstructed images which have sharp edges and smooth regions. The additive operator splitting (AOS) scheme is used for discretizing Euler-Lagrange equations. We present the results of various numerical experiments that illustrate the improvements obtained with the new functional.     

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.     

Border Collision Bifurcations in a Footloose Capital Model with First Nature Firms

In this paper we extend the discrete time Footloose Capital model analyzed in Commendatore et al. (Nonlinear Dyn Psychol Life Sci 11(2):267–289, 2007) by introducing “first nature firms”, i.e., firms that use locally specific blueprints and, therefore, are immobile. Due to the presence of first nature firms (symmetrically distributed across the regions), the central dynamic map becomes a piecewise differentiable function: in addition to “standard” flip and pitchfork bifurcations also border collision bifurcations are possible and instances of multistability may emerge. Our analysis confirms and extends the results of Commendatore et al. (2007): (1) continuous time formulation hides complex dynamics patterns; (2) asymmetric distributions of industrial activity can be endogenously generated and are path dependent.     

A note on the alternating group network

The class of alternating group networks was introduced in the late 1990’s as an alternative to the alternating group graphs as interconnection networks. Recently, additional properties for the alternating group networks have been published. In particular, Zhou et al., J. Supercomput (2009), doi:, was published very recently in this journal. We show that this so-called new interconnection topology is in fact isomorphic to the (n,n−2)-star, a member of the well-known (n,k)-stars, 1≤k≤n−1, a class of popular networks proposed earlier for which a large amount of work have already been done. Specifically, the problem in Zhou et al., J. Supercomput (2009), doi:, was addressed in Lin and Duh, Inf. Sci. 178(3), 788–801, 2008, when k = n−2.     

Variational proof of optimality criteria for Michell structures with pre-existing members

This note puts forward a direct variational derivation of the optimality criteria of a class of Michell-like structures in which some members are a priori given; an alternative derivation was published in Rozvany et al. (Struct Multidisc Optim 31:373–377, 2006).     

Petri net-based context modeling for context-aware systems

The context-aware services require to efficiently perceive not only the user requirements but also the context of the environment to provide customized services to the user. To efficiently develop the context-aware applications a systematic methodology correctly specifying the relation among dynamically changing contexts is essential. Here the context model simplifying the manipulation of complex contexts is a key accessor for the specification and analysis of the service. Among various modeling approaches such as timed automata (Tang and You in Intell Automat Soft Comput 16(4):605–619, 2010), workflow (Rosemann et al. in Understanding context-awareness in business process design, 2010), Petri net (PN) (J?rgensen et al. in Innovat Syst Softw Eng 5(1):13–25, 2009), etc. developed for context-aware system, the PN-based approach has been recognized as one of the most effective one. In this paper we identify the issues of how the contexts are modeled and what kinds of the requirements needs to be considered in the context processing. We then discuss various Petri net (PN)-based modeling methodologies concerning the five important features for context processing: relationships and dependencies, time constraint, resource constraint, usability of modeling formalisms, and context identification. The study reveals that the approach effectively allowing both the time and resource constraints in the model while supporting other important properties needs to be developed further for accurately assess the context-aware systems. Also, the expandability and scalability issue need to be investigated.     

New Results on Web Caching with Request Reordering

We study web caching with request reordering. The goal is to maintain a cache of web documents so that a sequence of requests can be served at low cost. To improve cache hit rates, a limited reordering of requests is allowed. Feder et al. (Proceedings of the 13th ACM–SIAM Symposium on Discrete Algorithms, pp. 104–105, 2002), who recently introduced this problem, considered caches of size 1, i.e. a cache can store one document. They presented an offline algorithm based on dynamic programming as well as online algorithms that achieve constant factor competitive ratios. For arbitrary cache sizes, Feder et al. (Theor. Comput. Sci. 324:201–218, 2004) gave online strategies that have nearly optimal competitive ratios in several cost models.     

Algorithmic applications of XPCR

An emerging trend in DNA computing consists of the algorithmic analysis of new molecular biology technologies, and in general of more effective tools to tackle computational biology problems. An algorithmic understanding of the interaction between DNA molecules becomes the focus of some research which was initially addressed to solve mathematical problems by processing data within biomolecules. In this paper a novel mechanism of DNA recombination is discussed, that turned out to be a good implementation key to develop new procedures for DNA manipulation (Franco et al., DNA extraction by cross pairing PCR, 2005; Franco et al., DNA recombination by XPCR, 2006; Manca and Franco, Math Biosci 211:282–298, 2008). It is called XPCR as it is a variant of the polymerase chain reaction (PCR), which was a revolution in molecular biology as a technique for cyclic amplification of DNA segments. A few DNA algorithms are proposed, that were experimentally proven in different contexts, such as, mutagenesis (Franco, Biomolecular computing—combinatorial algorithms and laboratory experiments, 2006), multiple concatenation, gene driven DNA extraction (Franco et al., DNA extraction by cross pairing PCR, 2005), and generation of DNA libraries (Franco et al., DNA recombination by XPCR, 2006), and some related ongoing work is outlined.     

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 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.     

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).

Efficient scheme of verifying integrity of application binaries in embedded operating systems

Currently, embedded systems have been widely used for ubiquitous computing environments including digital setup boxes, mobile phones, and USN (Ubiquitous Sensor Networks). The significance of security has been growing as it must be necessarily embedded in all these systems. Up until now, many researchers have made efforts to verify the integrity of applied binaries downloaded in embedded systems. The research of problem solving is organized into hardware methods and software-like methods. In this research, the basic approach to solving problems from the software perspective was employed. From the software perspective, unlike in the existing papers (Seshadri et al., Proc. the IEEE symposium on security and privacy, 2004; Seshadri et al., Proc. the symposium on operating systems principals, 2005) based on the standardized model (TTAS.KO-11.0054. 2006) publicized in Korea, there is no extra verifier and conduct for the verification function in the target system. Contrary to the previous schemes (Jung et al. , 2008; Lee et al., LNCS, vol. 4808, pp. 346–355, 2007), verification results are stored in 1 validation check bit, instead of storing signature value for application binary files in the i-node structure for the purpose of reducing run-time execution overhead. Consequently, the proposed scheme is more efficient because it dramatically reduces overhead in storage space, and when it comes to computing, it performs one hash algorithm for initial execution and thereafter compares 1 validation check bit only, instead of signature and hash algorithms for every application binary. Furthermore, in cases where there are frequent changes in the i-node structure or file data depending on the scheme application, the scheme can provide far more effective verification performance compared to the previous schemes.     

An improved data hiding approach for polygon meshes

We present an improved technique for data hiding in polygonal meshes, which is based on the work of Bogomjakov et al. (Comput. Graph. Forum 27(2):637–642, 2008). Like their method, we use an arrangement on primitives relative to a reference ordering to embed a message. But instead of directly interpreting the index of a primitive in the reference ordering as the encoded/decoded bits, our method slightly modifies the mapping so that our modification doubles the chance of encoding an additional bit compared to Bogomjakov et al.’s (Comput. Graph. Forum 27(2):637–642, 2008). We illustrate the inefficiency in the original mapping of Bogomjakov et al. (Comput. Graph. Forum 27(2):637–642, 2008) with an intuitive representation using a binary tree.     

An Arbitrary High-Order Spline Finite Element Solver for the Time Domain Maxwell Equations

In this paper, we study high order methods for solving the time domain Maxwell equations using spline finite elements on domains defined by NURBS. Convenient basis functions for the discrete exact sequence of spaces introduced by Buffa et al. (Comput. Methods Appl. Mech. Eng. 199:1143–1152, 2009) are exhibited which provide the same discrete structure as for classical Whitney Finite Elements. An analysis of stability of the time scheme is also developed.