  Two related online problems: knapsack and truthful bipartite matching are
considered. For these two problems, the common theme is how to `match' an
arriving left vertex in an online fashion with any of the available right
vertices, if at all, so as to maximize the sum of the value of the matched
edges, subject to satisfying a sum-weight constraint on the matched left
vertices. Assuming that the left vertices arrive in an uniformly random order
(secretary model), two almost similar algorithms are proposed for the two
problems, that are $2e$ competitive and $24$ competitive, respectively. The
proposed online bipartite matching algorithm is also shown to be truthful:
there is no incentive for any left vertex to misreport its bid/weight. Direct
applications of these problems include job allocation with load balancing,
generalized adwords, crowdsourcing auctions, and matching wireless users to
cooperative relays in device-to-device communication enabled cellular network.
