Lecture notes for Algorithm Design

Lecture Notes for Algorithm Design

Problem reductions, 11 November 1999

These are provisional lecture notes, expect changes.

reductions - solving on problem by using another
example - detecting cyclic shifts
1. one string a cyclic of another
2. a cyclic search or a linear search
example - system of distinct representations
1. given a set of k sets, find a k-element set containing one element from each component set
2. a matching problem
  1. undirected graph matching - unmatched vertices; perfect matching; maximum matching; maximal matching
  2. bipartite graphs
  3. maximum bipartite matching - alternating path algorithm
  4. directed-graph implementation
  5. use maximal bipartite matching to find a system of distinct representations
example - string editing
1. insert, delete, change one string into another at minimal cost
2. represent each option as a weighted edge - weight is cost
3. vertices represent partial edits
4. find the shortest path to the lower left corner
5. flexible, models many situations
example - finding triangles
1. given an undirected graph, does it have three nodes connected to one another
2. choose(n, 3) = n!/(n-3)!3! is O(n³)
3. represent the graph as an adjacency matrix
4. consider matrix multiplication
linear programming
1. minimizing or maximizing problems
  1. maximizing network flows - a directed graph with weighted edges; a source and sink
    1. an edge weight is the maximum flow capacity of the edge
    2. the sum of the flows into a vertex must equal the sum of the flows out of the vertex
    3. what is the largest flow possible between source and sink
  2. philanthropist problem - n donors and m recipients
    1. donor i will give at most max_ij to recipient j
    2. donor i will give no more than Dmax_i to all recipients
    3. recipient i will accept no more than Rmax_i from all donors
    4. maximize the sum of all amounts donated: sum(i = 1 to n, j = 1 to m; d_ij), where d_ij is the amount donor i gives to recipient j
2. the linear-programming problem
  1. maximize a linear objective function c(x) = sum(c_ix_i), where c_i is a constant and x is an n-element vector of values to be manipulated
  2. the vector x is usually subject to constraints:
    1. inequality constraints - dotp(a_i, x) <= b_i for 1 <= i <= m
    2. equality constraints - dotp(e_i, x) = d_i for 1 <= i <= k
    3. non-negative constraints - x_i >= 0 for i in the set P, a subset of {1, ..., n}
  3. there is much research, expertise and software around to solve linear programming problems
3. example reductions to linear programming problems
  1. network flows
    1. the element x_i of vector x represents the flow assigned to edge i
    2. maximize the flows out of the sink - c(x) = sum(a_ix_i), where a_i is 1 if edge i is adjacent to the source and 0 otherwise
    3. don't exceed edge capacities - x_i <= c_i
    4. flow conservation - dotp(e_v, x = 0), where e_i = 1 if edge i flows into vertex v, = -1 if edge i flows out of vertex v, and 0 otherwise
    5. all flows are non-negative - x_i >= 0
  2. static routing
    1. the element x_i of vector x represents the number of messages sent along edge i
    2. maximize messages in the network - c(x) = sum(x_i)
    3. don't exceed vertex buffers - dotp(e_v, x = 0), where e_i = 1 if edge i is incident to v and 0 otherwise
    4. all flows are non-negative - x_i >= 0
  3. philanthropist problem
    1. the element x_ij of vector x represents amount given to recipient j by donor i
    2. maximize the amount given by all donors - c(x) = sum(x_ij)
    3. don't exceed donor maximums - dotp(e, x) <= Dmax_i, where e_kj = 1 if k = i and 0 otherwise
    4. don't exceed recipient maximums - dotp(r, x) <= Rmax_i, where e_jk = 1 if k = i and 0 otherwise
    5. don't exceed donor i's maximum to recipient j - x_ij <= a_ij
    6. all donations are non-negative - x_ij >= 0
  4. assignment problem - like the philanthropist problem except each donor gives to one recipient and one recipient receives from one donor
    1. the element x_ij of vector x represents amount given to recipient j by donor i
    2. maximize the amount given by all donors - c(x) = sum(x_ij)
    3. one recipient per donor - dotp(d, x) = 1 where d_kj = 1 if k = i and 0 otherwise
    4. one donor per recipient - dotp(r, x) = 1, where r_jk = 1 if k = i and 0 otherwise
    5. don't exceed donor i's maximum to recipient j - x_ij <= a_ij
    6. all donations are non-negative - x_ij >= 0
    7. integer programming, an np-complete problem

This page last modified on 3 December 1999.