« October 2003 | Main | December 2003 »

November 2003 Archives

Minesweeper Fanfic

Paul said to me one day, "You know what exists on the Internet now? Minesweeper Fanfic!" And indeed, the man does not lie. Ladies and gentlemen, boys and girls of all ages, I present you with: Minesweeper Fanfic.

Photography Exhibit Day

Last Saturday was Kenneth's Day of High Culture... The Other Ken was always complaining that no one ever sees me out of the house and not in a movie theater, so I called him up when I read about Michael Light's 100 Suns in the Mercury News during lunch one day. Light compiled a hundred photographs of nuclear test detonations from the above-ground era (1945 through 1962), and they were being exhibited at the warehouse-like "Hosfelt Gallery" in Downtown.

It was pretty surreal, as you might imagine. You might imagine a standard mushroom cloud, but every explosion was different. Take a look at Fox, Hood, Huron, Truckee, and Mohawk. Even though these were test detonations, I still felt a little guilty about finding them beautiful, but of course that's the whole point of the thing. There's a coffee table book version of this, and I think I might get it. It's certainly not your everyday coffee table book, that's for sure.

He also had company passes to SFMOMA, and we saw the Diane Arbus photography exhibit. She was famous in the 60s and 70s for her photographs of eccentrics like circus freaks, nudists, and transvestites, but she also shot middle and lower class people on the street. I think I liked the latter stuff more because I could actually relate to it instead of just thinking, "Oh, that's weird." Here are some of the ones I liked:

My favorite one was of this really stuck-up-looking old lady on the street, but I didn't find it online. Old ladies look funny! :P

Actually a week before Kenneth's Day of High Culture, I was at Joanne's goodbye party when we saw in a bookstore window paintings from Babar's Museum of Art. Lots of classic paintings.. except with elephants! :) I think that will be coffee table book number two once I move in to my new place. :)

SMB3 in 11 minutes

On a lighter note, after that crazy airline flight complexity thing that got me all excited, jsmthng showed me Super Mario Brothers 3 in eleven minutes. (17.5MB WMV) That link is a mirror of this slower link. Stephen wasn't impressed, having played very far in Zelda 1 blindfolded back in the day, but I think it's pretty cool, :) especially the extra lives by bouncing off of Bob-ombs bit. Or maybe that's just because I love saying "Bob-omb". Bob-omb! Bob-omb! Bob-ob-ob-ob-omb!

Here, as a free bonus, I'll give you a link to a German page with something about Bob-ombs. Gotta love the Internet.

Airline Flight Search Complexity

Here's a fascinating paper on the complexity of airline flight searches. I'd suggest grabbing the more readable PDF version. (1.0 MB)

Airlines have a number of different fares for each leg of every flight. This example in the paper shows that for a single airline (AA) on a single day, on a single path (SFO to ORD to BOS, then BOS to DFW to SFO), there are over 25 million valid fares, from a search space of 10 billion! That number goes way up as you make more flexible queries. All this is because the airlilnes try their best to charge everyone as much as they're willing to pay. Here's some interesting information on why flight pricing is so complicated:

Why this mess? Why so many fares, such complicated rules, the logic of priceable units, and so on? The answer is often called variable pricing. Various airline economists make the following claim: there is no price such that the price times the demand at the price equals the cost of flying a large jet. There are a lot of technical issues that can be raised with their argument, but leaving those aside the argument is that if the airline charges $1 per ticket of course the plane will fill, but the total revenue of $150 barely pays for an hour of a pilot’s salary. If they charge $1000 a ticket then if they could fill the plane they’d make a fortune, but only a small number of people are willing to fly at that price, so again they can’t equal the fixed costs of flying a plane. But if the airline can make those who are willing to pay it pay $1000, and others pay $800, and others $500, maybe down to $100 or so, then the sum total over all passengers is sufficient to pay for the fixed costs. In fact, some estimates put the incremental cost of flying a single passenger as low as $30 (for the meal and baggage and ticket handling), so that once the airline has committed to flying the plane it is in their interest to sell a ticket for $30 rather than let a seat go empty. But they must keep those who can pay more from buying their ticket at low prices, a tough balancing act.

The airlines solve this problem in two ways, collectively called revenue management. The first is to use fare prices and fare rules to construct a system wherein the cheapest fares have restrictions that increase their perceived cost for a business traveler to the point where the business traveler will choose to buy more expensive fares. For example, cheap fares require round trip travel, prohibit non stop flights and ticket refunds, et cetera. But the cheap fares remain available for leisure travelers with more flexibility, for whom the extra restrictions are not so onerous. The second way, discussed later, consists of dynamically deciding whether to sell a given fare for a flight based on how much demand there is for the flight. For example, if a flight is not filling, lower priced fares are made available (on the grounds that it’s better to get some money than none) but on high-demand flights only the most expensive fares are available.

The end result is that even the basic subproblems are NP-complete, meaning it'd take quantum computers to solve them quickly. After you buy a plane ticket, and it has a price and itinerary well-defined, finding all the valid fare combination for the various legs of your flight is still worst-case NP-complete! (The paper says that particular subproblem is quick to solve in practice.) Accurately finding all valid routes for a general search is harder than "EXPSPACE-hard", which means that even quantum computing wouldn't be able to do them quickly! (I hadn't even heard of EXPSPACE-hard! That's how hard it is! :P)

You might think that seating availability would be simple. But you'd be wrong! Take a look at the seating availability section starting here. When you ask for seating availability, you don't just get one number. You get a list of several numbers for various pricing ranges, which are in turn constantly updated over time based in part on demand. To further complicate things, each flight might have different availabilities depending on which multi-leg flight it's part of.

The craziness! I think this is just barely a taste of the complexity of airline flights, too. This paper comes from a company founded by MIT graduates... and I only vaguely understood parts of it. :) My only question is: The paper makes flight searches sound all but impossible... so how are they performed in practice? When I use an online flight search engine, are they only finding a subset of flights I could be taking? Or are flight search computers just barely keeping up with the load right now, and this paper is just a warning that this load is increasing exponentially with no solution in sight?

Too Toasty

Lisa showed me The Story of Kogepan. He's a Sanrio character who's a burnt bun. Because he's burnt, nobody loves him. So sad!

Update Nov-28: So my commenters explain to me that Kogepan's from San-X, which has no relation to Sanrio. I was confused by the name. :)

On people expecting plot in the Matrix sequels

There were a lot of people who thougth the first Matrix movie had a wonderful plot. I wasn't one of them. I thought the plot was kind of obvious and silly... I don't mean to sound haughty, but the sort of philosophical issues it raised were things I've contemplated a lot ages ago, so I didn't find them so novel.

Mostly, I thought the first Matrix movie had cool action.

So when the second one rolled around and people started complaining about how it had such a crappy script.. I agreed. ("It is..our destiny!!!!!") But when they said that they couldn't even enjoy the movie because of that, I was like, "Huh?" I like action movies with actual characters (i.e. Aliens), but I don't have to have that to enjoy them.

So now I'm in a position where I'm actually having trouble finding people to go watch Revolutions with me, and I find that amazing. I mean.. dude.. it has live action power armor! For all its flaws, Reloaded still had much cooler style than any of its imitators. I expect the same in Revolutions. I'm thinking my low expectations will allow me to enjoy the third one just as they allowed me to enjoy the second. Did I mention that the third oneo has live action power armor?

Some people saw the Matrix as the modern day Star Wars. I never did, and so I was never disappointed when Reloaded turned out to be no Empire Strikes Back.

I'm still waiting for the next Star Wars. The cost of special effects have been going down, so I'm hopeful. I won't even mind if it doesn't have live action power armor.

Rendition of a Canadian

A Syrian-born Canadian citizen was arrested in the United States and "rendered" to Syria by the CIA, where he was tortured for months before finally being released. They also made him sign forms he couldn't read. He claims that he is innocent. Here are his own words. It is of course awful if he's innocent, but even if he isn't, it's still awful.

A new Kenneth Lu on the web

There's a new Kenneth Lu on the web! He's the number two Google hit for my name now. I guess I'll only boost his ranking by linking to him, but hey! I don't mind! Besides.. my biggest competition isn't him, but rather my old Cronos Infinitus story, hosted on a server at MIT. For some reason, that story is the number one hit, and my blog is only number 3. :\

I'm not even that happy with that story.. I wanted to make so many edits.. but I realized that I was no longer in the same mindset as I was when I wrote it, so it was hard to rewrite it. Oh well. At least it IS still technically me, albeit an incorporeal phantom ghostly ethereal spectral apparition of me.

P.S.: The preceding blog post did not imply any endorsement of my doppelgänger's automotive repair services.

About November 2003

This page contains all entries posted to the klog in November 2003. They are listed from oldest to newest.

October 2003 is the previous archive.

December 2003 is the next archive.

Many more can be found on the main index page or by looking through the archives.

Powered by
Movable Type 3.3