Search

Traditionally, inapproximability results for $\mathsf{Max\,k\,CSP\!-\!q}$ have been established using balanced $t$-wise independent distributions, which are related to orthogonal arrays of strength $t$. We contribute to the field by exploring such combinatorial designs in the context of the differential approximation measure. First, we establish a connection between the average differential ratio and orthogonal arrays. We deduce a differential approximation ratio of $1/q^k$ on $(k +1)$-partite instances of $\mathsf{k\,CSP\!-\!q}$, $\Omega(1/n^{k/2})$ on Boolean instances, $\Omega(1/n)$ when $k =2$, and $\Omega(1/\nu^{k -\lceil\log_{p^\kappa} k\rceil})$ when $k\geq 3$ and $q\geq 3$, where $p^\kappa$ is the smallest prime power greater than $q$. Secondly, by considering pairs of arrays related to balanced $k$-wise independence, we establish a reduction from $\mathsf{k\,CSP\!-\!q}$ to $\mathsf{k\,CSP\!-\!k}$ (with $q>k$), with an expansion factor of $1/(q -k/2)^k$ on the differential approximation guarantee. This, combined with the result of Yuri Nesterov, implies a lower differential approximability bound of $0.429/(q -1)^2$ for $\mathsf{2\,CSP\!-\!q}$. Finally, we prove that every Hamming ball with radius $k$ provides a $\Omega(1/n^k)$-approximation of the instance diameter. Our work highlights the utility of combinatorial designs in establishing approximation results., Comment: Preliminary versions of this work have been presented or published at the ISCO 2012, ISCO 2018 and IWOCA 2018 conferences

In [1], we introduced a family of combinatorial designs, which we call "alphabet reduction pairs of arrays", ARPAs for short. These designs depend on three integer parameters $q, p \leq q, k\leq p$: $q$ is the size of the symbol set $\{0, 1 ,\ldots, q -1\}$ in which the coefficients of the arrays take their values; $p$ is the maximum number of distinct symbols allowed in a row of the second array of the pair; $k$ is the larger integer for which the two arrays of the pair coincide -- up to the order of their rows -- on any $k$-ary subset of their columns. The first array must contain at least one occurrence of the word $0\ 1\ \ldots\ q -1$. Intuitively, the idea is to cover "as many as possible" occurrences of this word of $q$ symbols with "as few as possible" words of at most $p$ different symbols. These designs are related to the approximability of "Constraint Satisfaction Problems with bounded constraint arity", known as $k\,$CSPs. In this context, we are particularly interested in ARPAs in which the frequency of the word $0\ 1\ \ldots\ q -1$ is maximal. We introduce a seemingly simpler family of combinatorial designs as "Cover pairs of arrays" (CPAs). The arrays of a CPA take Boolean coefficients, and must still coincide on any $k$-ary subset of their columns. The purpose is, as it were, to cover "as many as possible" occurrences of the word of $q$ ones using "as few as possible" $q$-length Boolean words of weight at most $p$. We show that, when it comes to maximizing the frequency of the words $0\ 1\ \ldots\ q -1$ in ARPAs and $1\ 1\ \ldots\ 1$ in CPAs, ARPAs and CPAs are equivalent. We prove the optimality of the ARPAs given in [1] for the case $p =k$. In addition, we provide optimal ARPAs for the cases $k =1$ and $k =2$. We emphasize the fact that both families of combinatorial designs are related to the approximability of $k\,$CSPs.

The Double Travelling Salesman Problem with Multiple Stacks, DTSPMS, deals with the collect and delivery of n commodities in two distinct cities, where the pickup and the delivery tours are related by LIFO constraints. During the pickup tour, commodities are loaded into a container of k rows, or stacks, with capacity c. This paper focuses on computational aspects of the DTSPMS, which is NP-hard. We first review the complexity of two critical subproblems: deciding whether a given pair of pickup and delivery tours is feasible and, given a loading plan, finding an optimal pair of pickup and delivery tours, are both polynomial under some conditions on k and c. We then prove a (3k)/2 standard approximation for the MinMetrickDTSPMS, where k is a universal constant, and other approximation results for various versions of the problem. We finally present a matching-based heuristic for the 2DTSPMS, which is a special case with k=2 rows, when the distances are symmetric. This yields a 1/2-o(1), 3/4-o(1) and 3/2+o(1) standard approximation for respectively Max2DTSPMS, its restriction Max2DTSPMS-(1,2) with distances 1 and 2, and Min2DTSPMS-(1,2), and a 1/2-o(1) differential approximation for Min2DTSPMS and Max2DTSPMS.

STSP seeks a pair of pickup and delivery tours in two distinct networks, where the two tours are related by LIFO contraints. We address here the problem approximability. We notably establish that asymmetric MaxSTSP and MinSTSP12 are APX, and propose a heuristic that yields to a 1/2, 3/4 and 3/2 standard approximation for respectively Max2STSP, Max2STSP12 and Min2STSP12.

The multiple Stack Travelling Salesman Problem, STSP, deals with the collect and the deliverance of n commodities in two distinct cities. The two cities are represented by means of two edge-valued graphs (G1,d2) and (G2,d2). During the pick-up tour, the commodities are stored into a container whose rows are subject to LIFO constraints. As a generalisation of standard TSP, the problem obviously is NP-hard; nevertheless, one could wonder about what combinatorial structure of STSP does the most impact its complexity: the arrangement of the commodities into the container, or the tours themselves? The answer is not clear. First, given a pair (T1,T2) of pick-up and delivery tours, it is polynomial to decide whether these tours are or not compatible. Second, for a given arrangement of the commodities into the k rows of the container, the optimum pick-up and delivery tours w.r.t. this arrangement can be computed within a time that is polynomial in n, but exponential in k. Finally, we provide instances on which a tour that is optimum for one of three distances d1, d2 or d1+d2 lead to solutions of STSP that are arbitrarily far to the optimum STSP.

This article provides an overview of the performance and the theoretical complexity of approximate and exact methods for various versions of the shortest path problem. The proposed study aims to improve the resolution of a more general covering problem within a column generation scheme in which the shortest path problem is the sub-problem.