snowblowing is NP-complete

The recent winter storm left a lot of snow on my driveway. A lot. My driveway is the perfectly place for huge snowdrifts to form. A tweet of my shoveling resulted in the discovery of The Snowblower Problem  by Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Valentin Polishchuk (HT @fbahr)

The Snowblower Problem (SBP) answers the following question:

How does one optimally use a snowblower to clear a given polygonal region?

The snowblower problem is like the Traveling Salesman Problem (TSP): the  objective to find the shortest snow removing tour to remove all the snow from a domain (the polygonal region). The difference between TSP and SBP is that the snow is displaced into a nearby region in the SBP and that if the snow is piled too high, then the snowblower cannot clear the snow. SBP is NP-complete.

There are three model variants considered in the paper differ in how and where you can throw the snow: (1) the default model where snow can be thrown in any direction, (2) the adjustable throw direction (left, right, or center) and (3) left throw only. Changing the snow throw direction is cumbersome, so the fixed direction model variant (the left throw only) has more practical value.

Theorem: The SBP is NP-complete, both in the default model and in the adjustable throw model, for inputs that are polygonal domains with holes.

From the paper.

From The Snowblower Problem by Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Valentin Polishchuk.

The SBP is similar in spirit to various zombie research models: it’s a silly problem context that has real applications. The applications for SBP are in milling and lawn-mowing. And you guessed it: lawn mowing is also NP-complete.

The paper goes on to present various approximation algorithms for SBP. The algorithms used decompose the snowy region into Voronoi cells and then clear the domain cell-by-cell. It is difficult to succinctly summarize the results here without introducing a bunch of mathematical notation so I’ll refer you directly to the paper for mathematical details.  The conclusion notes that the approximation ratios are likely not the best possible, so there are opportunities for follow on work.

What is your snow removing algorithm and how close to optimality is it?

 

Update: this is my favorite comment about this post on twitter. I also shovel my snow the old fashioned way and agree!

 

Advertisements

3 responses to “snowblowing is NP-complete

  • Research shows snowblowing is NP-complete. While t… | carlhowe.com/blog

    […] Research shows snowblowing is NP-complete. While that may be true, snow shoveling is aptly described as HP-hard. punkrockor.wordpress.com/2015/02/09/sno… […]

  • thatguyer

    Shoveling is linear (albeit with a pretty big constant)

  • Ultra Trust Region (@UltraTrustOptim)

    Problem formulation and framing is (almost) everything. You’re solving the wrong problem. “How does one optimally use a snowblower to clear a given polygonal region?” If the polygonal region doesn’t have any snow, the optimal use of a snowblower to clear the given polygonal region is to not use a snowblower at all. I.e., get a faculty position head in a non-snowy clime. And if you don’t want to do that, just hire a plow to clear it for you. If co-author Joseph S. B. Mitchell had stayed in coastal California, where he went to graduate school, rather than moving to New York, he would never have even needed to solve this problem.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: