Home COMP 360 Midterm review

Midterm review CC-BY-NC

Maintainer: admin

Under construction

1Network flow

1.1Introduction to flow problems

You have a graph with edges and vertices. Each edge has a capacity. There is a source vertex from which flow magically pours out and a sink vertex into which flow disappears. You want to maximise the amount of flow through the edges coming out of the source (or into the sink, same thing). Note that the flow going into any edge must be equal to the flow coming out of it.

1.2Ford-Fulkerson

The runtime is $O(nf)$ where $n$ is the number of edges and $f$ is the maximum flow.

The algorithm will always terminate if the capacities are rational numbers.

There is another version of Ford-Fulkerson that does run in polynomial time. It involves augmenting differently. Something to do with scaling max flow.

1.2.1Residual graphs

what is this

1.2.2Min-cut max-flow

The value of any flow is bounded above by the value of any cut.

The maximum flow is equal to the minimum cut.

1.3Applications

1.3.1Bipartite matching

A matching is a set of edges in a bipartite graph (with the vertices partitioned into disjoint sets $A$ and $B$) such that no vertex is connected to more than one edge. A perfect matching is a matching that includes all vertices.

In a bipartite matching problem, the input is a bipartite graph; the output, the largest possible matching.

First, we convert the graph into a flow network, such that the maximum flow in the network corresponds to a maximum matching in the graph.

Add a source vertex, $s$, and connect it with a directed edge of capacity 1 to every vertex in set $A$. Add a sink vertex, $t$, and connect every vertex in set $B$ to it with a directed edge of capacity 1. Assign a capacity of 1 to every edge between $A$ and $B$. Now, run FF to find the maximum flow. A flow of 1 through any edge corresponds to that edge being part of a maximum matching.

1.3.2Vertex cover

Choose a set of vertices such that every edge is connected to a vertex in the set.

This is actually a special case of BMP (above), just make the capacities of the existing edges infinite instead of 1 so that it's easier to find the min cut. The min vertex cover is given by the min cut. This is also given by the maximum matching.

1.3.3Disjoint path problem

Find the maximum number of edge-disjoint paths from $s$ to $t$ (with no vertex or edge visited more than once)

1.3.4Networks with multiple sources or sinks

Add a "super source" or "super sink". QED

1.3.5Circulation with demands

No one source or sink - instead, every vertex is either a source or a sink. Directed graph, non-negative capacities, every vertex has a demand. If this demand is positive, the vertex "demands" this much flow. If it is negative, the vertex supplies this much flow. A valid flow (i.e. circulation) must satisfy the capacity condition for the edges, as well as a new demand condition (flow in - flow out = demand).

If it is, we can check whether or not circulation is possible by converting it into a flow network problem. Add a super source, $s$, and connect it to all the vertices with a supply (i.e. negative demand), with capacity equal to the magnitude of the demand. Add a super sink, $t$, and connect all the vertices with a positive demand to it, with capacity equal to the magnitude of the demand. Then, find the max flow.

We note immediately that a valid circulation is only feasible when the sum of all the demands is 0. That is, the sum of all the "demands" must be equal in magnitude to the sum of all the "supplies". Moreover, if the maximum flow is equal to sum of all the "demands", then a valid circulation is feasible.

1.3.5.1Circulation with demands and lower bounds

To add the lower bounds in, just subtract the capacity of each edge by the lower bound, etc.

1.3.5.2Survey design

$n$ customers, $m$ products. Each customer knows about a particular subset of products. We want to ask each customer at most $c$ questions, and we want to ask between $p$ and $q$ questions per product. Each customer can be asked 0 or 1 questions about any given product. We can convert this bipartite into a circulation with demands and lower bounds problem

1.3.5.3Airline scheduling

Given a schedule consisting of $k$ airplanes, $m$ flights (given departure/arrival time, origin, destination), and we know how long it takes to get from one city to another. Is a given schedule feasible? (Note that we can initially put airplanes anywhere we want. We can also fly empty planes if we need to.)

We can convert this into a circulation with demands and lower bounds problem. For every flight, we add two nodes with an edge between them, with lower bound and capacity 1 (signifying the departure and the destination airport respectively). We then add a directed edge from a destination airport to a source airport if there is sufficient time to fly a plane from the destination airport to the source airport, with a lower bound of 0 and capacity 1. Every node has a demand and supply of 0. We connect $s$ to all origin airport notes, and $t$ to all destination airport nodes, low/cap of (0, 1).

If there is a possible schedule, then there will be a valid circulation. We can convert a circulation into a schedule by taking every edge that has 1 unit of flow through it as a flight taking place (so we trace the edge-disjoint paths from $s$ to $t$).

1.3.6Project selection

There is a set of projects, each of which has a certain revenue (positive: gain money, negative: lose money). Certain projects are prerequisites for others. The goal is to pick a set of projects to maximise revenue, with the condition that there is no edge from this set to outside this set (the prereq condition).

We can convert this into a flow network problem by adding an edge from any project to its prereq (feels a bit unintuitive), with capacity infinity. We then connect $s$ to every project with a positive revenue, with a capacity equal to that revenue; same for $t$ (negative revenue). Then, we just need to find a min cut.

1.3.7Baseball elimination

Given certain baseball teams, and a count of how many wins each team has had, and a network illustrating what games are yet to be played: can we tell if a particular team can finish in first place?

Yes: flow network. Create a node for each game, and a node for each team. Connect each game node to both team nodes (in that game), infinite capacity. Source: capacity equal to the number of games left, connected to all the games. Connect each team node to a sink, capacity equal to the number of games that team is allowed to win without beating the team that should come in first (or just the number of games it has left, for the team we're interested in). If the max flow is not equal to the sum of the capacities of the edges leaving the source then the team we're looking at cannot place first.

2Linear programming

2.1Concepts of linear programming

Assign values to a set of variables to maximise or minimise an objective function such that a set of linear constraints is satisfied.

The cost of an assignment is the value of the objective function given this assignment.

2.2Sample linear programming problems

Maximise $x_1 + x_2 + x_3$, subject to the constraints:

$$\begin{cases} & x_1 + 2x_2 \leq 1 \\ & 2x_1 + x_2 \leq 1 \\ & 3x_3 = 1 \\ & x_1, x_2, x_3 \geq 0 \end{cases}$$

In this case, the maximum is 1 (when $x_1 = x_2 = x_3 = 1/3$).

2.3Relation to network flow problems

We can convert a maximum flow problem into a linear programming problem as follows:

  • Variables: the amount of flow through the edges
  • Cost: maximise the flow through the edges coming out of the source
  • Constraints: $f(e) \leq c_e$ (capacity constraint), conservation constraint

If there are $n$ vertices and $m$ edges, then there are $n + 2m$ constraints.

For example, if we had a graph that looked like this:

      a
     > \
    /   \
   2     1
  /       \
 /         >
s --- 3 ---> t
I'll replace this diagram with a better one eventually, don't mock me

We could convert it into a linear programming problem:

  • Objective function: $f(sa) + f(st)$
  • Constraints: $\begin{cases} & f(sa) \leq 2 \\ & f(st) \leq 3 \\ & f(at) \leq 1 \\ & f(sa) = f(at) \\ & f(sa), f(st), f(at) \geq 0 \end{cases}$

2.3.1Flow networks with lower bounds

If the flow network had lower bounds, we could replace the last $\geq 0$ constraint with the true lower bound, etc.

2.3.2Flow networks with costs

Passing $f(e)$ through edge $e$ costs $f(e)P_e$.

The goal is to minimise the cost given a flow value $\alpha$.

  • Objective function: $\displaystyle \sum_{e \in G} f(e) \cdot P_e$
  • Constraint: flow leaving the source is equal to $\alpha$ (plus the other usual constraints)

The example given in class had to do with a city, and placing food in only some cities. An example that feels more logical to me involves access to banks since food is a depletable resource, but whatever.

2.4The simplex algorithm

Using a geometrical interpretation of the constraints, check all the vertices of the polygon (or polyhedron, depending on the number of constraints) and take the maximum value of the objective function that results.

If there are 3 variables, then there are 3 dimensions and each inequality corresponds to a plane that splits the space into two. We need at least 4 inequalities in order to form a polyhedron (a bounded solid). Each vertex corresponds to the point at which three inequalities meet.

If there are 2 variables, then there are 2 dimensions and each inequality corresponds to a line that splits the plane into two. We need at least 3 inequalities in order to form a (bounded) polygon. Each vertex corresponds to the point at which two inequalities meet.

In the average case, this algorithm runs in polynomial time, although in the worst case it runs in exponential time.

2.5Canonical form

Any linear program can be converted into canonical form, which looks like this (for a maximising problem):

$$ \text{Constraints: } \begin{cases} & a_{1,1}x_{1,1} + \ldots a_{1,n} x_{1,n} \leq b_1 \\ & \ldots \\ & a_{m,1} x_{m,1} + \ldots a_{m, n} x_{m, n} \leq b_m \end{cases} $$

Objective function (the thing to maximise): $c_1 x_1 + \ldots c_n x_n$

Other constraints: $x_1, \ldots, x_n \geq 0$

For a minimising problem, flip the $\leq$ signs in the constraints.

2.5.1Strategies for converting into canonical form

  • If the $\leq$ sign is in the wrong direction, multiply both sides by -1.
  • Replace inequalities with two inequalities (in opposite directions)
  • If we have $x \leq 0$, replace it by $x'$ which is equal to $-x$
  • If we have $x \geq a$ where $a \neq 0$, replace $x$ by $x' = x-a$
  • If we don't have $x \geq 0$ at all, then we replace it by $x' - x''$, where $x', x'' \geq 0$ (so their difference spans all of $\mathbb{Z}$, which is what the original $x$ needs)

2.6Duality of linear programs

To prove that a feasible solution for a linear program is indeed the optimal solution, we can basically combine the inequalities to get another linear system of inequalities - its dual (so a linear program within a linear program, only it becomes a maximising problem instead of a minimising one, or vice versa). The solution for this is equal to the solution to the original linear program. This is reminiscent of the max-flow min-cut theorem.

Also, if one linear program is unbounded, so is its dual; if one is feasible and bounded, same thing.

Original: primal; the other: dual.