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: