Covering a laminar family by leaf to leaf links

The Tree Augmentation Problem (TAP) is: given a tree T=(V,E) and a set E of edges (called links) on V disjoint to E, find a minimum-size edge-subset F⊆E such that T+F is 2-edge-connected. TAP is equivalent to the problem of finding a minimum-size edge-cover F⊆E of a laminar set-family. We consider the restriction, denoted LL-TAP, of TAP to instances when every link in E connects two leaves of T. The best approximation ratio for TAP is 3/2, obtained by Even et al. (2001, 2009, 2008) [3], [4] and [5], and no better ratio was known for LL-TAP. All the previous approximation algorithms that achieve a ratio better than 2 for TAP, or even for LL-TAP, have been quite involved.For LL-TAP we obtain the following approximation ratios: 17/12 for general trees, 11/8 for trees of height 3, and 4/3 for trees of height 2. We also give a very simple3/2-approximation algorithm (for general trees) and prove that it computes a solution of size at most , where t is the minimum size of an edge-cover of the leaves, and t^∗ is the optimal value of the natural LP-relaxation for the problem of covering the leaf edges only. This provides the first evidence that the integrality gap of a natural LP-relaxation for LL-TAP is less than 2.     

An algorithm for source location in directed graphs

A polynomial time solution algorithm is described to find a smallest subset R of nodes of a directed graph D=(V,A) such that, for every node v∈V-R, there are k edge-disjoint paths from R to v and there are l edge-disjoint paths from v to R.     

The chromatic covering number of a graph

Following [1], we investigate the problem of covering a graph G with induced subgraphs G₁,…, G_k of possibly smaller chromatic number, but such that for every vertex u of G, the sum of reciprocals of the chromatic numbers of the G_i's containing u is at least 1. The existence of such “chromatic coverings” provides some bounds on the chromatic number of G. © 2005 Wiley Periodicals, Inc.     

Solving a laminar boundary layer equation with the rational Gegenbauer functions

In this paper, a collocation method using a new weighted orthogonal system on the half-line, namely the rational Gegenbauer functions, is introduced to solve numerically the third-order nonlinear differential equation, af^?+ff^″=0${\mathit{af}}^{?}+{\mathit{ff}}^{″}=0$, where a   is a constant parameter. This method solves the problems on semi-infinite domain without truncating it to a finite domain and transforming the domain of the problems to a finite domain. For a=2$a=2$, the equation is the well-known Blasius equation, which is a laminar viscous flow over a semi-infinite flat plate. We solve this equation by considering 1?a?2$1?a?2$ and compare the new results with the established results to show the efficiency and accuracy of the new method.     

Fault-tolerant concave facility location problem with uniform requirements

In this paper, we consider the fault-tolerant concave facility location problem (FTCFL) with uni- form requirements. By investigating the structure of the FTCFL, we obtain a modified dual-fitting bifactor approximation algorithm. Combining the scaling and greedy argumentation technique, the approximation fac- tor is proved to be 1.52.     

A monotone approximation algorithm for scheduling with precedence constraints

We provide a monotone O(m^2/3)-approximation algorithm for scheduling related machines with precedence constraints.     

Continuous covering and cooperative covering problems with a general decay function on networks

A cooperative covering location problem anywhere on the networks is analysed. Each facility emits a signal that decays by the distance along the arcs of the network and each node observes the total signal emitted by all facilities. A node is covered if its cumulative signal exceeds a given threshold. The cooperative approach differs from traditional covering models where the signal from the closest facility determines whether or not a point is covered. The objective is to maximize coverage by the best location of facilities anywhere on the network. The problems are formulated and analysed. Optimal algorithms for one or two facilities are proposed. Heuristic algorithms are proposed for location of more than two facilities. Extensive computational experiments are reported.     

A projection method for a system of nonlinear monotone equations with convex constraints

In this paper, we propose a projection method for solving a system of nonlinear monotone equations with convex constraints. Under standard assumptions, we show the global convergence and the linear convergence rate of the proposed algorithm. Preliminary numerical experiments show that this method is efficient and promising. This work was supported by the Postdoctoral Fellowship of The Hong Kong Polytechnic University, the NSF of Shandong China (Y2003A02).     

Locating a semi-obnoxious covering facility with repelling polygonal regions

A facility is to be located in the Euclidean plane to serve certain sites by covering them closely. Simultaneously, a set of polygonal areas must be protected from the negative effects from that facility. The problem is formulated as a margin maximization model. Necessary optimality conditions are studied and a finite dominating set of solutions is obtained, leading to a polynomial algorithm. The method is illustrated on some examples.     

Analytical solutions of laminar swirl decay in a straight pipe

In this work, the laminar swirl flow in a straight pipe is revisited and solved analytically by using prescribed axial flow velocity profiles. Based on two axial velocity profiles, namely a slug flow and a developed parabolic velocity profiles, the swirl velocity equation is solved by the separation of variable technique for a rather general inlet swirl velocity distribution, which includes a forced vortex in the core and a free vortex near the wall. The solutions are expressed by the Bessel function for the slug flow and by the generalized Laguerre function for the developed parabolic velocity. Numerical examples are calculated and plotted for different combinations of influential parameters. The effects of the Reynolds number, the pipe axial distance, and the inlet swirl profiles on the swirl velocity distribution and the swirl decay are analyzed. The current results offer analytical equations to estimate the decay rate and the outlet swirl intensity and velocity distribution for the design of swirl flow devices.     

Wall effect on determination of laminar burning velocity in a constant volume bomb using a quasi-dimensional model

In experiment, two optical and pressure-based methods are frequently used to evaluate laminar burning velocity of a combustible mixture. In the currently reported work, the pressure-based method was utilized to find the laminar burning velocity using the measurement of pressure variations during the combustion process in a spherical bomb and analyzing them through a multi-zone quasi-dimensional model. To check the results of the method, isooctane–air mixtures were used at equivalence ratios of 0.85 and 1.0 and initial pressures of 95 and 150 kPa with 343 K initial temperature. The time history of the bomb pressure during the combustion event, initial pressure and temperature, fuel type, and equivalence ratio were applied as input to a Fortran program written by the author based on the multi-zone combustion model; and, flame radius-time, flame speed, and laminar burning velocity at different pressures and temperatures were evaluated assuming spherical flame growth. The obtained results were compared with those of some other researchers and a reasonable agreement was observed. The wall effect on the laminar burning velocity at the end of the combustion process was clearly highlighted and a reliable range of burning velocity was distinguished. The results showed that the evaluated laminar burning velocity was not reliable at the late part of the combustion process due to possible local contact of flame front and the bomb wall, the wall effect on the reacting species, flow to small crevices, and the boundary layer effect.     

Estimating the distance to a monotone function

In standard property testing, the task is to distinguish between objects that have a property 𝒫 and those that are ε‐far from 𝒫, for some ε > 0. In this setting, it is perfectly acceptable for the tester to provide a negative answer for every input object that does not satisfy 𝒫. This implies that property testing in and of itself cannot be expected to yield any information whatsoever about the distance from the object to the property. We address this problem in this paper, restricting our attention to monotonicity testing. A function f : {1,…,n} ↦ R is at distance ε_f from being monotone if it can (and must) be modified at ε_fn places to become monotone. For any fixed δ > 0, we compute, with probability at least 2/3, an interval [(1/2 − δ)ε,ε] that encloses ε_f. The running time of our algorithm is O(ε_f⁻¹ log log ε_f^{− 1} log n), which is optimal within a factor of loglog ε_f⁻¹ and represents a substantial improvement over previous work. We give a second algorithm with an expected running time of O(ε_f⁻¹ log nlog log log n). Finally, we extend our results to multivariate functions. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

A robust support vector regression with a linear-log concave loss function

Support vector regression (SVR) is one of the most popular nonlinear regression techniques with the aim to approximate a nonlinear system with a good generalization capability. However, SVR has a major drawback in that it is sensitive to the presence of outliers. The ramp loss function for robust SVR has been introduced to resolve this problem, but SVR with ramp loss function has a non-differentiable and non-convex formulation, which is not easy to solve. Consequently, SVR with the ramp loss function requires smoothing and Concave-Convex Procedure techniques, which transform the non-differentiable and non-convex optimization to a differentiable and convex one. We present a robust SVR with linear-log concave loss function (RSLL), which does not require the transformation technique, where the linear-log concave loss function has a similar effect as the ramp loss function. The zero norm approximation and the difference of convex functions problem are employed for solving the optimization problem. The proposed RSLL approach is used to develop a robust and stable virtual metrology (VM) prediction model, which utilizes the status variables of process equipment to predict the process quality of wafer level in semiconductor manufacturing. We also compare the proposed approach to existing SVR-based methods in terms of the root mean squared error of prediction using both synthetic and real data sets. Our experimental results show that the proposed approach performs better than existing SVR-based methods regardless of the data set and type of outliers (ie, X-space and Y-space outliers), implying that it can be used as a useful alternative when the regression data contain outliers.     

An improved monotone algorithm for scheduling related machines with precedence constraints

We answer an open question posed by Krumke et al. (2008) [6] by showing how to turn the algorithm of Chekuri and Bender for scheduling related machines with precedence constraints into an O(logm)-approximation algorithm that is monotone in expectation. This significantly improves on the previously best known monotone approximation algorithms for this problem, from Krumke et al. [6] and Thielen and Krumke (2008) [8], which have an approximation guarantee of O(m^2/3).     

Minimizing a differentiable function over a differential manifold

To generalize the descent methods of unconstrained optimization to the constrained case, we define intrinsically the gradient field of the objective function on the constraint manifold and analyze descent methods along geodesics, including the gradient projection and reduced gradient methods for special choices of coordinate systems. In particular, we generalize the quasi-Newton methods and establish their superlinear convergence; we show that they only require the updating of a reduced size matrix. In practice, the geodesic search is approximated by a tangent step followed by a constraints restoration or by a simple arc search again followed by a restoration step.A first draft of this paper was first presented at the 10th International Symposium on Mathematical Programming, Montreal, Canada, 1979. The present version has been prepared while the author was visiting the Department of Engineering-Economic Systems at Stanford University, partially supported by AFOSR Grant No. 77-3141.     

Numerical simulation of laminar flow past a circular cylinder

The present paper focuses on the analysis of two- and three-dimensional flow past a circular cylinder in different laminar flow regimes. In this simulation, an implicit pressure-based finite volume method is used for time-accurate computation of incompressible flow using second order accurate convective flux discretisation schemes. The computation results are validated against measurement data for mean surface pressure, skin friction coefficients, the size and strength of the recirculating wake for the steady flow regime and also for the Strouhal frequency of vortex shedding and the mean and RMS amplitude of the fluctuating aerodynamic coefficients for the unsteady periodic flow regime. The complex three dimensional flow structure of the cylinder wake is also reasonably captured by the present prediction procedure.     

Bin covering with a general profit function: approximability results

In the recent paper (Benk? et al. 2010) we introduced a new problem that we call Bin Packing/Covering with Delivery, or BP/CD for short. Mainly we mean under this expression that we look for not only a good, but a “good and fast” packing or covering. In the present paper we investigate the offline case. For the analysis, a novel view on “offline optimum” is introduced, which appears to be relevant concerning all problems where a final solution is ordering-dependent. We prove that if the item sizes are not allowed to be arbitrarily close to zero, then an optimal offline solution can be found in polynomial time. On the other hand, for unrestricted problem instances, no polynomial-time algorithm can achieve an asymptotic approximation ratio better than 6/7 if $P\ne NP$ .