Zobrazeno 1 - 10
of 22
pro vyhledávání: '"Bercea, Ioana O."'
Given a $k$-CNF formula and an integer $s$, we study algorithms that obtain $s$ solutions to the formula that are maximally dispersed. For $s=2$, the problem of computing the diameter of a $k$-CNF formula was initiated by Creszenzi and Rossi, who sho
Externí odkaz:
http://arxiv.org/abs/2408.03465
In the online sorting problem, $n$ items are revealed one by one and have to be placed (immediately and irrevocably) into empty cells of a size-$n$ array. The goal is to minimize the sum of absolute differences between items in consecutive cells. Thi
Externí odkaz:
http://arxiv.org/abs/2406.19257
Hashing is a common technique used in data processing, with a strong impact on the time and resources spent on computation. Hashing also affects the applicability of theoretical results that often assume access to (unrealistic) uniform/fully-random h
Externí odkaz:
http://arxiv.org/abs/2308.14134
A filter is a widely used data structure for storing an approximation of a given set $S$ of elements from some universe $U$ (a countable set).It represents a superset $S'\supseteq S$ that is ''close to $S$'' in the sense that for $x\not\in S$, the pr
Externí odkaz:
http://arxiv.org/abs/2205.14894
Autor:
Bercea, Ioana O., Even, Guy
Bucket Sort is known to run in expected linear time when the input keys are distributed independently and uniformly at random in the interval $[0,1)$. The analysis holds even when a quadratic time algorithm is used to sort the keys in each bucket. We
Externí odkaz:
http://arxiv.org/abs/2002.10499
Autor:
Bercea, Ioana O., Even, Guy
A fully-dynamic dictionary is a data structure for maintaining sets that supports insertions, deletions and membership queries. A filter approximates membership queries with a one-sided error. We present two designs: 1. The first space-efficient full
Externí odkaz:
http://arxiv.org/abs/1911.05060
Autor:
Bercea, Ioana O., Groß, Martin, Khuller, Samir, Kumar, Aounon, Rösner, Clemens, Schmidt, Daniel R., Schmidt, Melanie
Clustering is a fundamental tool in data mining. It partitions points into groups (clusters) and may be used to make decisions for each point based on its group. However, this process may harm protected (minority) classes if the clustering algorithm
Externí odkaz:
http://arxiv.org/abs/1811.10319
Autor:
Bercea, Ioana O.
Given a set of $n$ disks of radius $R$ in the Euclidean plane, the Traveling Salesman Problem With Neighborhoods (TSPN) on uniform disks asks for the shortest tour that visits all of the disks. The problem is a generalization of the classical Traveli
Externí odkaz:
http://arxiv.org/abs/1809.07159
We study the problem of sensor placement in environments in which localization is a necessity, such as ad-hoc wireless sensor networks that allow the placement of a few anchors that know their location or sensor arrays that are tracking a target. In
Externí odkaz:
http://arxiv.org/abs/1607.05791
Whether or not the problem of finding maximal independent sets (MIS) in hypergraphs is in (R)NC is one of the fundamental problems in the theory of parallel computing. Unlike the well-understood case of MIS in graphs, for the hypergraph problem, our
Externí odkaz:
http://arxiv.org/abs/1405.1133