Since Tassiulas and Ephremides developed the max-weight (MW) algorithm in 1992, the trade-off between complexity and throughput in scheduling algorithms has been much studied under various directions. In particular, for input-queue switches, the high-complexity MW algorithm achieves 100% throughput, while the low-complexity longest-queue-first (LQF) algorithm does only 50% throughput. In this work, we present a low-complexity scheduling algorithm which achieves 100% throughput for input-queue switches, i.e, it achieves the best possible guarantees for both throughput and complexity. Our algorithm is motivated by the popular "Belief Propagation (BP)" algorithm in artificial intelligence, where analyzing a time-varying BP is the main technical challenge.