BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:0023c27d-e276-4b81-a3c2-3f97cd9af6b4
X-WR-CALNAME:[gt.go] - 'Discriminating Codes in Geometric Setups' by Sanjan
 a Dey
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20231029T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20211031T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20221030T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20210328T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20220327T020000
RDATE:20230326T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:0023c27d-e276-4b81-a3c2-3f97cd9af6b4
DTSTAMP:20260409T172941Z
CLASS:PUBLIC
DESCRIPTION:/Exposé en anglais/Talk in english/ \n\nWe study geometric vari
 ations 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 ca
 rdinality such that for each point p_i in P the subset S_i^* \subseteq S^*
  covering p_i\, satisfy S_i^*\neq \emptyset\, and each pair p_i\,p_j in P\
 , i \neq j\, satisfies S_i^* \neq S_j^*. In the continuous version of the 
 problem\, the solution set S^* can be chosen freely among a (potentially i
 nfinite) \nclass of allowed geometric objects. \n\nIn the 1-dimensional ca
 se\, 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 th
 at the discrete version of this problem is NP-complete. This is somewhat s
 urprising as the continuous version is known to be polynomial-time solvabl
 e. This is also in contrast with most geometric covering problems\, which 
 are usually polynomial-time solvable in one dimension. Still\, for the 1-d
 imensional 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 requir
 ed to have the same length. \n\nWe then study the 2-dimensional case\, d=2
 \, for axis-parallel unit square objects. We show that the continuous vers
 ion is NP-complete\, and design a polynomial-time approximation algorithm 
 that produces (8+\epsilon)-approximate solutions\, using rounding of suita
 bly defined integer linear programming problems. \n\n[Sanjana Dey] (indian
  Statistical Institute) \n\n\n\nRemarques / Remarks \n\nFind all the infor
 mation 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 ] \n\nRetrouvez toutes les infor
 mations du GT sur https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe
 /GT [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT ]
DTSTART;TZID=Europe/Paris:20211126T140000
DTEND;TZID=Europe/Paris:20211126T145500
LOCATION:A30/178 et sur https://u-bordeaux-fr.zoom.us/j/4939941120
SEQUENCE:0
SUMMARY:[gt.go] - 'Discriminating Codes in Geometric Setups' by Sanjana Dey
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
