![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
learn something new every day
Apr. 10th, 2010 01:26 amSo, among the other things I haven't been paying much attention to lately, I must include my independent study class. I'd been sitting in on Samir's Advanced Algorithms class before Spring Break (aeons ago!), but that's about it. So when I turned back up after being out of class for two weeks, he caught me after lecture and pretty much ordered me to schedule an appointment with him. Fair enough. And in spite of (or perhaps because of) dreading the meeting all week, I didn't look at algorithms or my project at all until a few hours before the meeting.
I should back up. Samir is quite interested in carpooling/ridesharing, and while a rideshare service launched on campus earlier this year, he was quite disappointed to learn that absolutely no matching was done at all besides generic euclidean distance.
In initially talking with him, however, he was very much going off on the tangent of Bipartite Graphs and Perfect Matching. In Samir's world, you'd sign up for the service, the service would say "here! this is your best match!" and the two carpoolers would go off into the sunset. We talked some about bids and offers and incentives, but all roads led back to Bipartite Matching. I didn't have the words to explain why I felt this to be completely inadequate to the problem. Just, "I dont think that will work well."
Well, after several weeks of the algorithms class and desultorily reading Kleinberg's algorithms text, I at least understand *why* all roads lead to Bipartite Matching-- as far as I can tell, all of algorithms and math is based on "here's a thing we know how to do. can we transform the problem in front of us into something we know how to do? because that'd be great. if not, can we at least approximate or put bounds on the problem doing something we know how to do? somehow? kthxbye."
That still didn't address my gut feeling as to why this wasn't the right tree to be barking up. So around 1pm today (meeting was at 3), I sat back down with the algorithms text, the rideshare site, and just started writing down things I saw to be problems. Finally, the answer showed up in front of me.
This isn't a pure ask-offer matching problem. One person may want to be a passenger. Another may want to be a driver. But most are in a nebulous third state: they are advertising that they could be a driver *or* a passenger. Suddenly I had something concrete to offer.
...
So, lessons today:
1) It's not sufficient to just dismiss something as "not going to work." It may not work. But development cannot be done on hunches.
2) It's actually far more satisfying to come up with valid technical concerns based on *understanding* the proposed methodology than just saying "I told you so."
3) Dreading the meeting was stupid. We had a good meeting, he hadn't considered that aspect of the matching problem, and we had other useful topics of conversation as well.
I should back up. Samir is quite interested in carpooling/ridesharing, and while a rideshare service launched on campus earlier this year, he was quite disappointed to learn that absolutely no matching was done at all besides generic euclidean distance.
In initially talking with him, however, he was very much going off on the tangent of Bipartite Graphs and Perfect Matching. In Samir's world, you'd sign up for the service, the service would say "here! this is your best match!" and the two carpoolers would go off into the sunset. We talked some about bids and offers and incentives, but all roads led back to Bipartite Matching. I didn't have the words to explain why I felt this to be completely inadequate to the problem. Just, "I dont think that will work well."
Well, after several weeks of the algorithms class and desultorily reading Kleinberg's algorithms text, I at least understand *why* all roads lead to Bipartite Matching-- as far as I can tell, all of algorithms and math is based on "here's a thing we know how to do. can we transform the problem in front of us into something we know how to do? because that'd be great. if not, can we at least approximate or put bounds on the problem doing something we know how to do? somehow? kthxbye."
That still didn't address my gut feeling as to why this wasn't the right tree to be barking up. So around 1pm today (meeting was at 3), I sat back down with the algorithms text, the rideshare site, and just started writing down things I saw to be problems. Finally, the answer showed up in front of me.
This isn't a pure ask-offer matching problem. One person may want to be a passenger. Another may want to be a driver. But most are in a nebulous third state: they are advertising that they could be a driver *or* a passenger. Suddenly I had something concrete to offer.
...
So, lessons today:
1) It's not sufficient to just dismiss something as "not going to work." It may not work. But development cannot be done on hunches.
2) It's actually far more satisfying to come up with valid technical concerns based on *understanding* the proposed methodology than just saying "I told you so."
3) Dreading the meeting was stupid. We had a good meeting, he hadn't considered that aspect of the matching problem, and we had other useful topics of conversation as well.
