Skip to content

Reductions

April 26, 2013

Learning how to solve an algorithmic problem by using a solution to another similar problem is called reduction.

Sorting

Shortest Path

  • Parallel scheduling
  • Arbitrage
  • Shortest undirected graph – simply create directed edges of the same weight from and to each node.

Max Flow

  • Bipartite matching
  • Network reliability
  • Product distribution

Calculate cost of reduction

running time of reduction algorithm + cost of creating the reduction.

NOTE: Many problems defy classification, and therefore reduction.

Advertisements

From → Algorithms

Leave a Comment

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: