Zobrazeno 1 - 10
of 100
pro vyhledávání: '"De, Minati"'
We present algorithms for the online minimum hitting set problem: Given a set $P$ of $n$ points in the plane and a sequence of geometric objects that arrive one-by-one, we need to maintain a hitting set at all times. For disks of radii in the interva
Externí odkaz:
http://arxiv.org/abs/2412.04646
The hitting set problem is one of the fundamental problems in combinatorial optimization and is well-studied in offline setup. We consider the online hitting set problem, where only the set of points is known in advance, and objects are introduced on
Externí odkaz:
http://arxiv.org/abs/2409.11166
We present online deterministic algorithms for minimum coloring and minimum dominating set problems in the context of geometric intersection graphs. We consider a graph parameter: the independent kissing number $\zeta$, which is a number equal to `th
Externí odkaz:
http://arxiv.org/abs/2312.01467
In this paper, we study the online class cover problem where a (finite or infinite) family $\cal F$ of geometric objects and a set ${\cal P}_r$ of red points in $\mathbb{R}^d$ are given a prior, and blue points from $\mathbb{R}^d$ arrives one after a
Externí odkaz:
http://arxiv.org/abs/2308.07020
We consider the online version of the piercing set problem, where geometric objects arrive one by one, and the online algorithm must maintain a valid piercing set for the already arrived objects by making irrevocable decisions. It is easy to observe
Externí odkaz:
http://arxiv.org/abs/2305.02445
We investigate the geometric hitting set problem in the online setup for the range space $\Sigma=({\cal P},{\cal S})$, where the set $\P\subset\mathbb{R}^2$ is a collection of $n$ points and the set $\cal S$ is a family of geometric objects in $\math
Externí odkaz:
http://arxiv.org/abs/2304.06780
Autor:
De, Minati, Singh, Satyam
Publikováno v:
Theoretical Computer Science 992C (2024) 114452
We consider the online hitting set problem for the range space $\Sigma=(\cal X,\cal R)$, where the point set $\cal X$ is known beforehand, but the set $\cal R$ of geometric objects is not known in advance. Here, objects from $\cal R$ arrive one by on
Externí odkaz:
http://arxiv.org/abs/2303.11779
Publikováno v:
In Computational Geometry: Theory and Applications December 2024 123
Finding minimum dominating set and maximum independent set for graphs in the classical online setup are notorious due to their disastrous $\Omega(n)$ lower bound of the competitive ratio that even holds for interval graphs, where $n$ is the number of
Externí odkaz:
http://arxiv.org/abs/2111.07812
Online hitting of unit balls and hypercubes in [formula omitted] using points from [formula omitted]
Autor:
De, Minati, Singh, Satyam
Publikováno v:
In Theoretical Computer Science 21 April 2024 992