\documentclass[]{article}
\usepackage[utf8]{inputenc}
\usepackage{amssymb}
\usepackage{siunitx}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{url}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{subcaption}
\usepackage[noadjust]{cite}
\usepackage{threeparttable}
\usepackage{framed}
\usepackage{fullpage}
\usepackage{geometry}
\usepackage{cancel}
\begin{document}
\begin{center}
\textbf{CSE248 Fall 2023 Exercise 2: Partitioning and
ancestor tree} \\
\end{center}
\noindent{\textbf{Due Time : 11:50pm, Friday 10/27, 2023}}
\textbf{Submit to Gradescope \\ Gradescope: \url{https://gradescope.com/} }\\
In this exercise, we investigate partitioning using network flow formulation and ancestor tree.
Problem 1 is a classic maximum flow and minimum cut exercise. However,
1.3 and 1.4 deviate from the classic formulation with a size constraint.
The constraint is common in practice.
Thus, we are interested in finding a solution.
For problem 2, we work on a retiming analysis. The minimum cost-to-time ratio
determines the timing behavior of the system.
For problem 3, we perform timing-driven partitioning with retiming.
For problem 4, we add replication capability to improve the partitioning results.
For problem 5, we practice the construction of the ancestor tree.
You can work on 4 out of 5 problems. The fifth will be
a bonus.\\
\noindent
1. Given a undirected graph $G(V,E)$ and two vertices $s, t \in V$, each edge $(i,j)\in E$ is attached with a weight $c_{i,j}$. We partition vertex set $V$ into two disjoint sets
$X$, and $\bar X$ such that $X \cup \bar X = V$ and vertex $s\in X$ and vertex $t\in \bar X$.
The objective is to minimize $C(X, \bar X)= \sum_{i\in X, j\in \bar X, and (i,j)\in E} c_{ij}$.
\noindent
1.1. Formulate the minimum cut problem as a network flow problem to maximize a flow $f$ from vertex $s$ to vertex $t$ with flow capacity $c_{i,j}$ on each edge $(i,j)\in E$. Write the formula in a standard convex optimization format.
\noindent
1.2. Derive the duality of the formula in 1.1. Show your steps.
\noindent
1.3. Suppose that we have a constraint that the cardinality $|X|$ of $X$ is limited
by two constants, i.e. $a \leq |X| \leq b$. Repeat items 1.1. and 1.2.
\noindent
1.4. Provide an example to demonstrate your formula of 1.3.
If the formula works, provide an argument as to why the formula works.
If the formula does not work, explain why not.\\
\noindent
2. Given a directed graph $G(V,E$), each vertex $i$ is attached with a
cost $d_i$ and each directed edge $(i,j)\in E$ is attached with a time shift $t_{i,j}$. For each cycle $p$ in $G$,
we define a cost-to-time ratio $R(p)=\sum_{i\in p} d_i / \sum_{(i,j)\in p} t_{i,j}$.
The problem is to find a cycle $p$ with the maximum cost-to-time ratio $R(p)$.
\noindent
2.1. Formulate the problem as a network flow problem.
\noindent
2.2. Derive the duality of the formula in 2.1. Show your derivation.\\
\noindent
3. Following problem 2, we are given two vertices $s,t \in V$. We want to partition the vertex set $V$ into two disjoint sets $X$ and $\bar X$
such that $X\cup \bar X = V$.
However, the partition adds cost to the edge that crosses the partition by
a constant $\delta$. The added cost increases the delay of the edge.
Our objective is to find a partition that maximizes the clock frequency.
\noindent
3.1. Formulate the problem as a network flow problem.
\noindent
3.2. Derive the duality of the formula in 2.1. Show your derivation.
\noindent
3.3. Provide an example to demonstrate your formula of 3.2.
If the formula works, provide an argument as to why the formula works.
If the formula does not work, explain why not.\\
\noindent
4. Following problem 3, we are now allowed to perform the partition with replication.
Repeat 3.1, 3.2, and 3.3.\\
\noindent
5. Create an undirected graph with 5 vertices and 8 edges.
Assign the edge weights ranging within [1, 9].
Derive the ancestor tree of the graph. Show your steps.
\end{document}