Toward a deterministic polynomial time algorithm with optimal additive query complexity

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 nn identical looking coins. Suppose that mm out of the nn 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 weighings for identifying the counterfeit coins and their weights is at least Ω(mlognlogm). We give a deterministic polynomial time adaptive algorithm for identifying the counterfeit coins and their weights using O(mlognlogm+mloglogm) weighings, assuming that the weight of the counterfeit coins are greater than the weight of the authentic coins. This algorithm is optimal when m≤nc/loglognm≤nc/loglogn, where cc is any constant. Also our weighing complexity is within loglogmloglogm times the optimal complexity for all mm.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 H. Mazzawi (2008) [20], we get a similar positive result for the problem of reconstructing a hidden weighted graph using additive queries.