Approximation schemes for deal splitting and covering integer programs with multiplicity constraints

We consider the problem of splitting an order for R goods, R≥1, among a set of sellers, each having bounded amounts of the goods, so as to minimize the total cost of the deal. In deal splitting with packages (DSP), the sellers offer packages containing combinations of the goods; in deal splitting with price tables (DST), the buyer can generate such combinations using price tables. Our problems, which often occur in online reverse auctions, generalize covering integer programs with multiplicity constraints (CIP), where we must fill up an R-dimensional bin by selecting (with a bounded number of repetitions) from a set of R-dimensional items, such that the overall cost is minimized. Thus, both DSP and DST are NP-hard, already for a single good, and hard to approximate for arbitrary number of goods.In this paper we focus on finding efficient approximations for DSP and DST instances where the number of goods is some fixed constant. In particular, we develop polynomial time approximation schemes (PTAS) for several subclasses of instances of practical interest. Our results include a PTAS for CIP in fixed dimension, and a more efficient (combinatorial) scheme for CIP_∞, where the multiplicity constraints are omitted. Our approximation scheme for CIP_∞ is based on a non-trivial application of the fast scheme for the fractional covering problem, proposed by Fleischer [L. Fleischer, A fast approximation scheme for fractional covering problems with variable upper bounds, in: Proc. of the 15th ACM-SIAM Symposium on Discrete Algorithm, 2004, pp. 994-1003].     

Asymptotic equilibrium and stability of fuzzy differential equations

The local existence and uniqueness theorems and the global existence of solutions were investigated in [1–3], respectively, for the Cauchy problem of fuzzy-valued functions of a real variable whose values are in the fuzzy number space (Eⁿ, D). In this paper, we first study the asymptotic equilibrium for fuzzy evolution equations. Then, the stability properties of the trivial fuzzy solution of the perturbed semilinear fuzzy evolution equations are investigated by extending the Lyapunov's direct method.     

A numerical study of variable coefficient elliptic Cauchy problem via projection method

In this paper, we investigate a numerical method for the solution of an inverse problem of recovering lacking data on some part of the boundary of a domain from the Cauchy data on other part for a variable coefficient elliptic Cauchy problem. In the process, the Cauchy problem is transformed into the problem of solving a compact linear operator equation. As a remedy to the ill-posedness of the problem, we use a projection method which allows regularization solely by discretization. The discretization level plays the role of regularization parameter in the case of projection method. The balancing principle is used for the choice of an appropriate discretization level. Several numerical examples show that the method produces a stable good approximate solution.     

Characteristic stabilized finite element method for the transient Navier–Stokes equations

Based on the lowest equal-order conforming finite element subspace (X_h, M_h) (i.e. P₁–P₁ or Q₁–Q₁ elements), a characteristic stabilized finite element method for transient Navier–Stokes problem is proposed. The proposed method has a number of attractive computational properties: parameter-free, avoiding higher-order derivatives or edge-based data structures, and averting the difficulties caused by trilinear terms. Existence,uniqueness and error estimates of the approximate solution are proved by applying the technique of characteristic finite element method. Finally, a serious of numerical experiments are given to show that this method is highly efficient for transient Navier–Stokes problem.     

Stochastic complement analysis of multi-server threshold queues with hysteresis

We consider a K-server threshold-based queueing system with hysteresis, for which a set of forward thresholds (F₁,F₂,…,F_K−1) and a set of reverse thresholds (R₁,R₂,…,R_K−1) are defined. A simple version of this multi-server queueing system behaves as follows. When a customer arrives to an empty system, it is serviced by a single server. Whenever the number of customers exceeds a forward threshold F_i, a server is added to the system and server activation is instantaneous. Whenever the number of customer falls below a reverse threshold R_i, a server is removed from the system. We consider and solve several variations of this problem, namely: (1) homogeneous servers with Poisson arrivals, (2) homogeneous servers with bulk (Poisson) arrivals, and (3) heterogeneous servers with Poisson arrivals. We place no restrictions on the number of servers or the bulk sizes or the size of the waiting room. In [O.C. Ibe, J. Keilson, Multi-server threshold queues with hysteresis, Performance Evaluation 21 (1995) 185–212], the authors solve a limited form of this problem using Green’s function method. More specifically, they give a closed-form solution for a K-server system, when the servers are homogeneous, and for a two-server system, when the servers are heterogeneous; the authors experienced difficulties in extending Green’s function method beyond the case of two heterogeneous servers. Rather than using Green’s function, we solve this problem using the concept of stochastic complementation, which is a more intuitive and more easily extensible method. For the case of a homogeneous multi-server system we are able to derive a closed-form solution for the steady state probability vector; for the remaining cases we give an algorithmic solution. Note, however, that we can use stochastic complementation to derive closed-form solutions for some limited forms of cases (2) and (3), such as heterogeneous servers with K=2 and bulk arrivals with a limited bulk size. Finally, our technique works both for systems with finite and infinite waiting rooms.     

Multiprocessor systems with preemptive priorities

A system with N processors and R job classes subject to a preemptive priority scheduling discipline is considered. Exact analysis is presented for the case R = 2, under Markovian assumptions. That analysis suggests a method for obtaining approximate solutions for arbitrary R. The implementation of the methods is discussed and numerical results for some special cases are given.     

A Numerical Method to Solve Identification Problem for the Lower Coefficient and the Source in the Convection–Reaction Equation

We consider the problem of identifying simultaneously the kinetic reaction coefficient and source function depending only on a spatial variable in one-dimensional linear convection–reaction equation. As additional conditions, a non-local integral condition for the solution of the equation and condition of final overdetermination are given. This problem belongs to the class of combined inverse problems. By integrating the equation with the use of additional integral condition, the problem is transformed to a coefficient inverse problem with local conditions. The derivative with respect to the spatial variable is discretized and a special representation is proposed to solve the resultant semi-discrete problem. As a result, for each discrete value of the spatial variable, the semi-discrete problem splits into two parts: a Cauchy problem and a linear equation with respect to the approximate value of the unknown kinetic coefficient. To determine the source function, an explicit formula is also obtained. The numerical solution of the Cauchy problem uses the implicit Euler method. Numerical experiments are carried out on the basis of the proposed method.     

Penalty-finite-element analysis of 3-D Navier-Stokes equations

The steady-state Navier-Stokes equations in three dimensions are solved by a penalty-finite-element method for the problems of wall-driven cavity flow in a cubical box and natural convection in a cubical cavity subjected to differential side heating. The present solutions are compared with recent finite-difference solutions of the wall-driven cavity problem for Reynolds numbersR_E = 100 and 400. The agreement is found to be very good.     

An integrated framework for the diagnosis and correction of rule-based programs

We present a generic scheme for the declarative debugging of programs that are written in rewriting-based languages that are equipped with narrowing. Our aim is to provide an integrated development environment in which it is possible to debug a program and then correct it automatically. Our methodology is based on the combination (in a single framework) of a semantics-based diagnoser that identifies those parts of the code that contain errors and an inductive learner that tries to repair them, once the bugs have been located in the program. We develop our methodology in several steps. First, we associate with our programs a semantics that is based on a (continuous) immediate consequence operator, T_R, which models the answers computed by narrowing and is parametric w.r.t. the evaluation strategy, which can be eager or lazy. Then, we show that, given the intended specification of a program R, it is possible to check the correctness of R by a single step of T_R. In order to develop an effective debugging method, we approximate the computed answers semantics of R and derive a finitely terminating bottom-up abstract diagnosis method, which can be used statically. Finally, a bug-correction program synthesis methodology attempts to correct the erroneous components of the wrong code. We propose a hybrid, top-down (unfolding-based) as well as bottom-up (induction-based), correction approach that is driven by a set of evidence examples which are automatically produced as an outcome by the diagnoser. The resulting program is proven to be correct and complete w.r.t. the considered example sets. Our debugging framework does not require the user to provide error symptoms in advance or to answer difficult questions concerning program correctness. An implementation of our debugging system has been undertaken which demonstrates the workability of our approach.     

Membership problems for data dependencies in relational expressions

In relational databases, a query can be formulated in terms of a relational algebra expression using projection, selection, restriction, cross product and union. In this paper, we consider a problem, called the membership problem, of determining whether a given dependency d is valid in a given relational expression E over a given database scheme R that is, whether every instance of the view scheme defined by E satisfies d (assuming that the underlying constraints in R are always satisfied).Consider the case where each relation scheme in R is associated with functional dependencies (FDs) as constraints, and d is an FD. Then the complement of the membership problem is NP-complete. However, if E contains no union, then the membership problem can be solved in polynomial time. Furthermore, if E contains neither a union nor a projection, then we can construct in polynomial time a cover for valid FDs in E, that is, a set of FDs which implies every valid FD in E.Consider the case where each relation scheme in R is associated with multivalued dependencies (MVDs) as well as FDs, and d is an FD or an MVD. Even if E consists of selections and cross products only, the membership problem is NP-hard. However, if E contains no union, and each relation scheme name in R occurs in E at most once, then the membership problem can be solved in polynomial time. As a corollary of this result, it can be determined in polynomial time whether a given FD or MVD is valid in $\text{R}{}_1\text{???R}{}_{\mathrm{s}}$, where R₁,…,R_s are relation schemes with FDs and MVDs, and $\text{R}{}_{\mathrm{i}}\text{?R}{}_{\mathrm{j}}$ is the natural join of R_i and R_j.     

On the complexity of interval scheduling with a resource constraint

We consider a scheduling problem where jobs have to be carried out by parallel identical machines. The attributes of a job j are: a fixed start time s_j, a fixed finish time f_j, and a resource requirement r_j. Every machine owns R units of a renewable resource necessary to carry out jobs. A machine can process more than one job at a time, provided the resource consumption does not exceed R. The jobs must be processed in a non-preemptive way. Within this setting, the problem is to decide whether a feasible schedule for all jobs exists or not.We discuss such a decision problem and prove that it is strongly NP-complete even when the number of resources are fixed to any value R≥2. Moreover, we suggest an implicit enumeration algorithm which has O(nlogn) time complexity in the number n of jobs when the number m of machines and the number R of resources per machine are fixed.The role of storage layout and preemption are also discussed.     

Curved finite element methods for the solution of singular integral equations on surfaces in R3

We have shown in [1]that the singular integral equation (1.2) on a closed surface Γ of R³ admits a unique solution q and is variational and coercive in the Hilbert space $\text{H}{}^{\mathrm{<mtext>?</mtext><mtext>1</mtext><mtext>2</mtext>}}$(Γ). In this paper, with the help of curved finite elements, we introduce an approximate surface Γ_h, and an approximate problem on Γ_h, whose solution is q_h. Then we study the error of approximation |q ? q_h| in some Hubert spaces and also the associated error |u ? u_h| of the potential.     

Maximum principle and uniform convergence for the finite element method

The solution of the Dirichlet boundary value problem over a polyhedral domain Ω ? Rⁿ, n ≥ 2, associated with a second-order elliptic operator, is approximated by the simplest finite element method, where the trial functions are piecewise linear. When the discrete problem satisfies a maximum principle, it is shown that the approximate solution u_h converges uniformly to the exact solution u if u ? W_1,p (Ω), with p > n, and that $\text{∥u?u}{}_{\mathrm{h}}\text{∥}{}_{\mathrm{L}}\text{∞(Ω) = O(h)}$ if u ? W²,p(Ω), with 2p > n. In the case of the model problem ?Δu+au = f in Ω, u = u_o on δΩ, with a ? 0, a simple geometrical condition is given which insures the validity of the maximum principle for the discrete problem.     

An optimal triangulation for second-order elliptic problems

Let Ω be a polygonal domain in $\text{R}{}^{\mathrm{n}}$, τ_h an associated triangulation and u_h the finite element solution of a well-posed second-order elliptic problem on (Ω, τ_h). Let M = {M_i}^{p + q}_{i = 1} be the set of nodes which defines the vertices of the triangulation τ_h: for each i,$\text{M}{}_{\mathrm{i}}\text{= {x}{}_{\mathrm{i}}{}^{\mathrm{l}}\text{¦1 ? l ?n}}$ in Rⁿ. The object of this paper is to provide a computational tool to approximate the best set of positions M? of the nodes and hence the best triangulation $\text{}\text{?}\text{gt}{}_{\mathrm{h}}$ which minimizes the solution error in the natural norm associated with the problem.The main result of this paper are theorems which provide explicit expressions for the partial derivatives of the associated energy functional with respect to the coordinates x_i^l, 1 ? l ? n, of each of the variable nodes M_i, i = 1,…, p.     

The cable trench problem: combining the shortest path and minimum spanning tree problems

Let G=(V,E) be a connected graph with specified vertex v₀∈V, length l(e)⩾0 for each e∈E, and positive parameters τ and γ. The cable-trench problem (CTP) is to find a spanning tree T such that τl_τ(T)+γl_γ(T) is minimized where l_τ(T) is the total length of the spanning tree T and l_γ(T) is the total path length in T from v₀ to all other vertices of V. Since all vertices must be connected to v₀ and only edges from E are allowed, the solution will not be a Steiner tree. Consider the ratio R=τ/γ. For R large enough the solution will be a minimum spanning tree and for R small enough the solution will be a shortest path. In this paper, the CTP will be shown to be NP-complete. A mathematical formulation for the CTP will be provided for specific values of τ and γ. Also, a heuristic will be discussed that will solve the CTP for all values of R.Scope and purposeBoth the shortest path and the minimum spanning tree problems are universally discussed in operations research and management science textbooks. Since the late 1950s, efficient algorithms have been known for both of these problems. In this paper, the cable-trench problem is defined which combines the shortest path problem and the minimum spanning tree problem to create a problem that is shown to be NP-complete. In other words, two easy problems are combined to get a more realistic problem that is difficult to solve. Examples are used to illustrate an efficient and effective heuristic solution procedure for the cable-trench problem.     

A novel L1/2 regularization shooting method for Cox’s proportional hazards model

Nowadays, a series of methods are based on a L ₁ penalty to solve the variable selection problem for a Cox’s proportional hazards model. In 2010, Xu et al. have proposed a L _1/2 regularization and proved that the L _1/2 penalty is sparser than the L ₁ penalty in linear regression models. In this paper, we propose a novel shooting method for the L _1/2 regularization and apply it on the Cox model for variable selection. The experimental results based on comprehensive simulation studies, real Primary Biliary Cirrhosis and diffuse large B cell lymphoma datasets show that the L _1/2 regularization shooting method performs competitively.     

A theoretical limit for safety verification techniques with regular fix-point computations

In computer aided verification, the reachability problem is particularly relevant for safety analyses. Given a regular tree language L, a term t and a relation R, the reachability problem consists in deciding whether there exist a positive integer n and terms t₀,t₁,…,tn such that t₀∈L, tn=t and for every 0?i<n, (ti,ti+1)∈R. In this case, the term t is said to be reachable, otherwise it is said unreachable. This problem is decidable for particular kinds of relations, but it is known to be undecidable in general, even if L is finite. Several approaches to tackle the unreachability problem are based on the computation of an R-closed regular language containing L. In this paper we show a theoretical limit to this kind of approaches for this problem.     

Retrieval of total suspended matter concentration in the Yellow and East China Seas from MODIS imagery

A retrieval algorithm, of total suspended matter (TSM) concentration in the Yellow Sea (YS) and East China Sea (ECS) was developed using observations made in the 2003 Spring and Autumn cruises over the YS and the ECS. Analysis of the in-situ backscattering coefficients of the suspended particles (b_bp) indicates that the accuracy becomes worse when the concentration of TSM (C_TSM) is higher than 20 mg/l. The accuracy of the b_bp is improved by using a bio-optical model in which b_bp is optimized with a non-linear least-square Levenberg-Marquardt method. The remote sensing reflectance (R_rs) is obtained by means of the optimization. The optimized R_rs for waters with C_TSM higher than 20 mg/l, together with the measured R_rs for waters with C_TSM lower than 20 mg/l, are used to establish the relationships between R_rs(748), R_rs(869) and R_rs(645), which are used in the iterative method for atmospheric correction. Two atmospheric correction algorithms are switched according to the water turbidity. The shortwave infrared wavelengths (SWIR) method is used for waters with high-turbidity, and the iterative method is used otherwise. Results of the atmospheric correction were then applied to the Tassan model modified in this paper to compute the C_TSM. Comparison between the retrieval results from MODIS imagery and the in-situ measurements indicates that the algorithms described in this paper can provide a reliable estimation of the C_TSM distributions in the YS and ECS.     

Inapproximability results for equations over finite groups

An equation over a finite group G is an expression of form w₁w₂…w_k=1_G, where each w_i is a variable, an inverted variable, or a constant from G; such an equation is satisfiable if there is a setting of the variables to values in G so that the equality is realized. We study the problem of simultaneously satisfying a family of equations over a finite group G and show that it is NP-hard to approximate the number of simultaneously satisfiable equations to within |G|−ε for any ε>0. This generalizes results of Håstad (J. ACM 48 (4) (2001) 798), who established similar bounds under the added condition that the group G is Abelian.