Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Sublinear time:
TR07-052 | 7th May 2007
Li Chen, Bin Fu

Linear and Sublinear Time Algorithms for the Basis of Abelian Groups

Revisions: 2

It is well known that every finite Abelian group $G$ can be
represented as a product of cyclic groups: $G=G_1\times
G_2\times\cdots G_t$, where each $G_i$ is a cyclic group of size
$p^j$ for some prime $p$ and integer $j\ge 1$. If $a_i$ is the
generator of the cyclic group of ... more >>>

TR11-028 | 24th February 2011
Richard Beigel, Bin Fu

A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing

The bin packing problem is to find the minimum
number of bins of size one to pack a list of items with sizes
$a_1,\ldots , a_n$ in $(0,1]$. Using uniform sampling, which selects
a random element from the input list each time, we develop a
randomized $O({n(\log n)(\log\log n)\over ... more >>>

ISSN 1433-8092 | Imprint