1 citations · 2 across the 6 of their papers we have counts for
12 papers
Worst-Case Efficient Dynamic Geometric Independent Set
Jean Cardinal, John Iacono, Grigorios Koumoutsos
We consider the problem of maintaining an approximate maximum independent set of geometric objects under insertions and deletions. We present data structures that maintain a consta…
Memoryless Algorithms for the Generalized -server Problem on Uniform Metrics
Dimitris Christou, Dimitris Fotakis, Grigorios Koumoutsos
We consider the generalized -server problem on uniform metrics. We study the power of memoryless algorithms and show tight bounds of on their competitive ratio. In parti…
Dynamic Geometric Independent Set
Sujoy Bhore, Jean Cardinal, John Iacono +1
We present fully dynamic approximation algorithms for the Maximum Independent Set problem on several types of geometric objects: intervals on the real line, arbitrary axis-aligned…
Sublinear Explicit Incremental Planar Voronoi Diagrams
Elena Arseneva, John Iacono, Grigorios Koumoutsos +2
A data structure is presented that explicitly maintains the graph of a Voronoi diagram of point sites in the plane or the dual graph of a convex hull of points in three dimensi…
The Online Min-Sum Set Cover Problem
Dimitris Fotakis, Loukas Kavouras, Grigorios Koumoutsos +2
We consider the online Min-Sum Set Cover (MSSC), a natural and intriguing generalization of the classical list update problem. In Online MSSC, the algorithm maintains a permutation…
Competitive Online Search Trees on Trees
Prosenjit Bose, Jean Cardinal, John Iacono +2
We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tre…
External Memory Planar Point Location with Fast Updates
John Iacono, Ben Karsin, Grigorios Koumoutsos
We study dynamic planar point location in the External Memory Model or Disk Access Model (DAM). Previous work in this model achieves polylog query and polylog amortized update time…
Belga B-trees
Erik D. Demaine, John Iacono, Grigorios Koumoutsos +1
We revisit self-adjusting external memory tree data structures, which combine the optimal (and practical) worst-case I/O performances of B-trees, while adapting to the online distr…
Nested Convex Bodies are Chaseable
Nikhil Bansal, Martin Böhm, Marek Eliáš +2
In the Convex Body Chasing problem, we are given an initial point in and an online sequence of convex bodies . When we receive , we are required…
Competitive Algorithms for Generalized k-Server in Uniform Metrics
Nikhil Bansal, Marek Elias, Grigorios Koumoutsos +1
The generalized k-server problem is a far-reaching extension of the k-server problem with several applications. Here, each server lies in its own metric space . A reques…
Weighted k-Server Bounds via Combinatorial Dichotomies
Nikhil Bansal, Marek Elias, Grigorios Koumoutsos
The weighted -server problem is a natural generalization of the -server problem where each server has a different weight. We consider the problem on uniform metrics, which co…
The -Server Problem on Bounded Depth Trees
Nikhil Bansal, Marek Eliáš, Łukasz Jeż +1
We study the -server problem in the resource augmentation setting i.e., when the performance of the online algorithm with servers is compared to the offline optimal solution…