|
|
 |
|
Jeudi 12 Décembre
| Heure: |
10:30 - 11:30 |
| Lieu: |
A303 |
| Résumé: |
Optimizing alphabet reduction pairs of arrays |
| Description: |
Sophie Toulouse In a previous work, we introduced alphabet reduction pairs of arrays (ARPAs), a family of combinatorial designs, to transport differential approximation results for k-CSPs over an alphabet of size p ? k to k-CSPs over an alphabet ?q of size q > p. ARPAs on ?q consist of two arrays of q columns satisfying the following conditions: the first array must contain a certain word composed of all symbols of ?q; no row of the second array can involve more than p different symbols of ?q; the two arrays must coincide on any subset of k columns. In the context of approximation, the target word in the first array represents an optimal solution that the second array allows us to associate with assignments involving at most p different values. Thus, we want to maximize the frequency of this particular word, and refer to ARPAs that achieve this as optimal.
To study optimal ARPAs, we consider a seemingly simpler family of combinatorial designs, called Cover Pairs of Arrays (CPAs), which can be viewed as a Boolean interpretation of ARPAs. The two arrays of a CPA still share the same number q of columns, and must match on any k of them; but they take Boolean entries, the second array is restricted to words with at most p ones, and we want to maximize the frequency of the word of q ones in the first array. Using combinatorics and linear programming, we establish the equivalence between ARPAs and CPAs in terms of maximizing the frequency of the target word. In addition, we provide optimal constructions for the case where k ? {1, 2, p}.
These results establish the optimality of ARPAs given in previous work for the case where p = k, and highlight the relevance of CPAs for the approximability of k CSPs. They also raise new questions about ARPAs, which we will discuss along with other questions about related combinatorial designs that allow refining our knowledge of how well k-CSP-q reduces to k-CSP-p.
Joint work with Jean-François Culus. |
|
|
