Zobrazeno 1 - 10
of 35
pro vyhledávání: '"Koumoutsos, Grigorios"'
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 constant-factor approximate maximum independent set for broad classes of fat
Externí odkaz:
http://arxiv.org/abs/2108.08050
We consider the generalized $k$-server problem on uniform metrics. We study the power of memoryless algorithms and show tight bounds of $\Theta(k!)$ on their competitive ratio. In particular we show that the \textit{Harmonic Algorithm} achieves this
Externí odkaz:
http://arxiv.org/abs/2007.08669
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 squares in the plane and axis-aligned $d$-dimensional hypercubes. It i
Externí odkaz:
http://arxiv.org/abs/2007.08643
A data structure is presented that explicitly maintains the graph of a Voronoi diagram of $N$ point sites in the plane or the dual graph of a convex hull of points in three dimensions while allowing insertions of new sites/points. Our structure suppo
Externí odkaz:
http://arxiv.org/abs/2007.01686
Autor:
Fotakis, Dimitris, Kavouras, Loukas, Koumoutsos, Grigorios, Skoulakis, Stratis, Vardas, Manolis
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 on $n$ elements based on subsets $S_1, S_2, \ldots$ arriving online.
Externí odkaz:
http://arxiv.org/abs/2003.02161
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 tree model in which the underlying search space is the set of vertices of
Externí odkaz:
http://arxiv.org/abs/1908.00848
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. We present a data structure with $O( \log_B^2 N)$ query time and $O(
Externí odkaz:
http://arxiv.org/abs/1905.02620
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 distribution of queries. Our approach is analogous to undergoing efforts in
Externí odkaz:
http://arxiv.org/abs/1903.03560
In the Convex Body Chasing problem, we are given an initial point $v_0$ in $R^d$ and an online sequence of $n$ convex bodies $F_1, ..., F_n$. When we receive $F_i$, we are required to move inside $F_i$. Our goal is to minimize the total distance trav
Externí odkaz:
http://arxiv.org/abs/1707.05527
The generalized k-server problem is a far-reaching extension of the k-server problem with several applications. Here, each server $s_i$ lies in its own metric space $M_i$. A request is a k-tuple $r = (r_1,r_2,\dotsc,r_k)$ and to serve it, we need to
Externí odkaz:
http://arxiv.org/abs/1707.04519