Efficient Approximation of the Capacitated Vehicle Routing Problem in a Metric Space of an Arbitrary Fixed Doubling Dimension

Doklady Mathematics - In this paper, for the first time, we provide a quasi-polynomial time approximation scheme for the well-known capacitated vehicle routing problem formulated in metric spaces...     

Special Issue: 18th International conference on mathematical optimization theory and operations research (MOTOR 2019)

Journal of Global Optimization -     

Efficient approximation of the metric CVRP in spaces of fixed doubling dimension

Journal of Global Optimization - The capacitated vehicle routing problem (CVRP) is the well-known combinatorial optimization problem having numerous practically important applications. CVRP is...     

Asymptotics of the solution of a system of nonlinear differential equations with a small parameter and with a higher-order extinction effect

We consider the Cauchy problem for two nonlinear differential equations with a small parameter multiplying the derivative in one of the equations. The right-hand side of this equation has a zero of high order at the origin with respect to one of the unknown functions. We construct and justify a uniform asymptotic approximation to the solution with accuracy of any power of the small parameter. We reveal two boundary layers in a neighborhood of the initial point.     

Combinatorial optimization problems related to the committee polyhedral separability of finite sets

In the paper, the computational and approximational complexity of the minimal affine separating committee problem, as well as of some important special cases of this problem, is investigated.     

Asymptotic expansion of the solution of the initial value problem for a singularly perturbed ordinary differential equation

We consider the Cauchy problem for the nonlinear differential equation

$$\varepsilon \frac{{du}}{{dx}} = f(x,u),u(0,\varepsilon ) = R_0 ,$$

where ? > 0 is a small parameter, f(x, u) ∈ C ^∞ ([0, d] × ?), R ₀ > 0, and the following conditions are satisfied: f(x, u) = x ? u ^p + O(x ² + |xu| + |u|^p+1) as x, u → 0, where p ∈ ? \ {1} f(x, 0) > 0 for x > 0; f _u ²(x, u) < 0 for (x, u) ∈ [0, d] × (0, + ∞); Σ ₀ ^+∞ f _u ²(x, u) du = ?∞. We construct three asymptotic expansions (external, internal, and intermediate) and prove that the matched asymptotic expansion approximates the solution uniformly on the entire interval [0, d].

     

On the Computational Complexity of the Minimum Committee Problem

Two special cases of the Minimum Committee Problem are studied, the Minimum Committee Problem of Finite Sets (MCFS) and the Minimum Committee Problem of a System of Linear Inequalities(MCLE). It is known that the first of these problems is NP-hard (see (Mazurov et al., Proc. Steklov Inst. Math., 1:67–101, 2002)). In this paper we show the NP-hardness of two integer optimization problems connected with it. In addition, we analyze the hardness of approximation to the MCFS problem. In particular, we show that, unless NP⊂TIME(n ^O(loglogn )), for every ε>0 there are no approximation algorithms for this problem with approximation ratio (1–ε)ln (m–1), where m is the number of inclusions in the MCFS problem. To prove this bound we use the SET COVER problem, for which a similar result is known (Feige, J. ACM, 45:634–652, 1998). We also show that the Minimum Committee of Linear Inequalities System (MCLE) problem is NP-hard as well and consider an approximation algorithm for this problem.