Výsledky vyhledávání - "Lukasiewicz, Aleksander"

Report

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Autor: Lassota, Alexandra, Łukasiewicz, Aleksander, Polak, Adam

We solve the Bin Packing problem in $O^*(2^k)$ time, where $k$ is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third

Externí odkaz: http://arxiv.org/abs/2203.10077

Zobrazit plný text záznamu

Report

Noisy searching: simple, fast and correct

Autor: Dereniowski, Dariusz, Łukasiewicz, Aleksander, Uznański, Przemysław

This work considers the problem of the noisy binary search in a sorted array. The noise is modeled by a parameter $p$ that dictates that a comparison can be incorrect with probability $p$, independently of other queries. We state two types of upper b

Externí odkaz: http://arxiv.org/abs/2107.05753

Zobrazit plný text záznamu

Report

Cardinality estimation using Gumbel distribution

Autor: Łukasiewicz, Aleksander, Uznański, Przemysław

Cardinality estimation is the task of approximating the number of distinct elements in a large dataset with possibly repeating elements. LogLog and HyperLogLog (c.f. Durand and Flajolet [ESA 2003], Flajolet et al. [Discrete Math Theor. 2007]) are sma

Externí odkaz: http://arxiv.org/abs/2008.07590

Zobrazit plný text záznamu

Report

All-Pairs LCA in DAGs: Breaking through the $O(n^{2.5})$ barrier

Autor: Grandoni, Fabrizio, Italiano, Giuseppe F., Łukasiewicz, Aleksander, Parotsidis, Nikos, Uznański, Przemysław

Let $G=(V,E)$ be an $n$-vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices $u$ and $v$ is a common ancestor $w$ of $u$ and $v$ such that no descendant of $w$ has the same property. In this paper, we consider the probl

Externí odkaz: http://arxiv.org/abs/2007.08914

Zobrazit plný text záznamu

Report

An Efficient Noisy Binary Search in Graphs via Median Approximation

Autor: Dereniowski, Dariusz, Łukasiewicz, Aleksander, Uznański, Przemysław

Consider a generalization of the classical binary search problem in linearly sorted data to the graph-theoretic setting. The goal is to design an adaptive query algorithm, called a strategy, that identifies an initially unknown target vertex in a gra

Externí odkaz: http://arxiv.org/abs/2005.00144

Zobrazit plný text záznamu