/Exposé en anglais/Talk in english/
We study geometric variations of the discriminating code problem. In the discrete version of the problem, a finite set of points P and a finite set of objects S are given in R^d. The objective is to choose a subset S^* \subseteq S of minimum cardinality such that for each point p_i in P the subset S_i^* \subseteq S^* covering p_i, satisfy S_i^*
eq \emptyset, and each pair p_i,p_j in P, i
eq j, satisfies S_i^*
eq S_j^*. In the continuous version of the problem, the solution set S^* can be chosen freely among a (potentially infinite)
class of allowed geometric objects.
In the 1-dimensional case, d=1, the points in P are placed on a line L and the objects in S are finite-length line segments aligned with L (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. This is also in contrast with most geometric covering problems, which are usually polynomial-time solvable in one dimension. Still, for the 1-dimensional discrete version, we design a polynomial-time 2-approximation algorithm. We also design a PTAS for both discrete and continuous versions in one dimension, for the restriction where the intervals are all required to have the same length.
We then study the 2-dimensional case, d=2, for axis-parallel unit square objects. We show that the continuous version is NP-complete, and design a polynomial-time approximation algorithm that produces (8+\epsilon)-approximate solutions, using rounding of suitably defined integer linear programming problems.
[Sanjana Dey] (indian Statistical Institute)
Remarques / Remarks
Find all the information of the working group on the web page https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en ]
Retrouvez toutes les informations du GT sur https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT ]