Suppose n people live in a house and wish to share their
expenses equally. Their respective expenses (before settling) are
x1, ..., xn. They agree to make payments to each other so as to
make all their net expenses equal. Naturally, they want to make a
few payments as possible
Suppose N People Live In A House And Wish To Share Their Expenses Equally Their Respective Expenses Before Settling A 1 (57.81 KiB) Viewed 35 times
2. Suppose n people live in a house and wish to share their expenses equally. Their respective expenses (before settling) are ₁,..., n. They agree to make payments to each other so as to make all their net expenses equal. Naturally, they want to make a few payments as possible. BALANCE denotes the decision version of this problem: Given nonnegative integers ₁,...,n (written in binary) and an integer k, can the net expenses be balanced using k or fewer payments? a) Show that BALANCE belongs to NP. b) Show that SUBSET SUM ≤, BALANCE, and thereby conclude that BALANCE is NP-complete.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!