Skip to content


April 26, 2013

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


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.


From → Algorithms

Leave a Comment

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: