id: 05779291
dt: a
an: 05779291
au: Bshouty, Nader H.; Mazzawi, Hanna
ti: Toward a deterministic polynomial time algorithm with optimal additive
    query complexity.
so: Hliněný, Petr (ed.) et al., Mathematical foundations of computer science
    2010. 35th international symposium, MFCS 2010, Brno, Czech Republic,
    August 23‒27, 2010. Proceedings. Berlin: Springer (ISBN
    978-3-642-15154-5/pbk). Lecture Notes in Computer Science 6281, 221-232
    (2010).
py: 2010
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-15155-2_21
ab: Summary: In this paper, we study two combinatorial search problems: The
    coin weighing problem with a spring scale (also known as the vector
    reconstructing problem using additive queries) and the problem of
    reconstructing weighted graphs using additive queries. Suppose we are
    given $n$ identical looking coins. Suppose that $m$ out of the $n$
    coins are counterfeit and the rest are authentic. Assume that we are
    allowed to weigh subsets of coins with a spring scale. It is known that
    the optimal number of weighing for identifying the counterfeit coins
    and their weights is at least $$Ω\left(\frac{m\log n}{\log
    m}\right).$$ We give a deterministic polynomial time adaptive algorithm
    for identifying the counterfeit coins and their weights using $$
    O\left(\frac{m\log n}{\log m}+ m\log \log m\right)$$ weighings,
    assuming that the weight of the counterfeit coins are greater than the
    weight of the authentic coin. This algorithm is optimal when $m \leq n
    ^{c/\log \log n }$, where $c$ is any constant. Also our weighing
    complexity is within $\log \log m$ times the optimal complexity for all
    $m$. To obtain this result, our algorithm makes use of search matrices,
    the divide and conquer approach and the guess and check approach. When
    combining these methods with the technique introduced in [Optimally
    Reconstructing Weighted Graphs Using Queries. SODA, 2010], we get a
    similar positive result for the problem of reconstructing a hidden
    weighted graph using additive queries.
rv: