Linear assignment problems, part I

I’m going to devote a few posts to my thesis topic, the quadratic assignment problem.  Quadratic assignment problems are a type of matching problem that are NP hard and have some interesting applications.  I’ll start out by describing linear assignment problems, which are simpler but still fun.

As the name suggests, in a linear assignment problem objects in one set are to be assigned to an equal number of objects in a second set. The cost of assigning objects in the first set to objects in the second set are given, and the objective is to find the assignment that minimizes the total assignment cost.  For example, the problem may be to assign workers to jobs so as to minimize the total amount of working time.  A more formal description of the problem can be found on this page (and I recommend the book, BTW).

LAP can also be posed as the problem of finding the minimum cost matching on a bipartite graph.  For this reason, in algorithms texts this problem is also sometimes referred to as “minimum cost weighted bipartite matching”.  LAPs are linear programs and so they can be solved in polynomial time.  As the wikipedia article on the problem states, there are algorithms that take advantage of the special structure of LAP to solve them more efficiently than general purpose LP solvers.

Next time I’ll go through one possible solution approach for LAP.

Advertisements

Why writing software is like moving

Me and my brother helped my mom move over the weekend.  Advice for movers and software developers:

  • Don’t move anything you don’t actually want or need.  Throw out your SAT study guide, your old copies of Maxim, the Michigan starter jacket, the annotated James Joyce that you’ve never read but impresses people.
  • Invite the right number of people.  It’s a sinking feeling to show up and find out that you and your friend are going to move the whole house.  It’s fun, but not terribly productive to show up and find 7 other people there – you end up spending a lot of time paging through other people’s books, or drinking, or both.
  • Pack before people show up.  Nothing kills me more than showing up to help a friend move to find that they haven’t done the prep work.  I don’t want to show up at 9:00 to find that I’m supposed to help you pack your t-shirts.
  • Figure out how to load the truck before lifting anything.  If it turns out that you don’t have enough room then you will waste a lot of time moving stuff around, or worse yet, leaving stuff behind.  Taking more than one trip is disastrous.  That second trip is never very fun.
  • Wrap fragile items, or items with sharp edges.  It’s worth the extra time.  Once the truck starts moving objects will tend to bump into each other so it’s wise to protect the ones that might break.
  • Do the heavy stuff first.  That way you’ll know if you’ve got enough room in the truck, besides, it’s better for morale.
  • Don’t try to do it all by yourself.  Yes, you have superhuman strength, and that ottoman isn’t all that heavy.  But if you’ve got help then why not take advantage.
  • Spring for the extra five bucks and unhook the dolly.  Then you can stack up all those boxes of books and move them in one trip.
  • When you get to the new place, just worry about getting the boxes out of the truck and into the right rooms.  Worry about arranging the furniture and unpacking boxes later.

And – the appropriate payment is always a six pack.

Management advice from Satchel Paige

Actually it’s not management advice — somehow I doubt Satchel Paige would have much patience for that sort of thing.  I don’t really like baseball, but I do like the personalities (particularly from the past) and the stats.  When I was growing up we had an old baseball stats reference on the bookshelf and I used to pore over the numbers, why I don’t really know.

Anyway, Satchel Paige said: “Don’t look back. Something might be gaining on you.” I think that’s pretty good advice.

Here are a bunch of other Satchel Paige quotes.