The Online Piercing Set Problem with Recourse
摘要
Given a set of geometric objects, A, in \(\mathbb {R}^d\) , a set of points P is a piercing set if every object in A includes a point in P. We consider the online version of the piercing set problem where recourse is allowed. In the traditional online setting, with irrevocable decisions, no algorithm can guarantee a competitive ratio better than \(\varOmega (n)\) for piercing intervals, where n is the length of the input sequence. In this paper, we show a 2-competitive algorithm for the problem by allowing at most one recourse per input. We prove that to maintain an optimum piercing set for intervals, any online algorithm needs \(\varOmega (n)\) amortised recourse. We also design an algorithm for piercing intervals which provides a trade-off between recourse and competitive ratio; the algorithm is \((1+\epsilon )\) -competitive when allowed \((1+2/\epsilon )\) recourse at each step. We extend our results to higher dimensions by obtaining a \(2^{d+1}\) -competitive algorithm with amortised two recourse for piercing axis-aligned hypercubes in \(\mathbb {R}^d\) .