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\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Online Piercing Set Problem with Recourse

  • Riju Bindua,
  • Minati De,
  • Naveen Garg,
  • Kanav Singla

摘要

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\) .