%% This LaTeX-file was created by <jl> Mon Apr 27 11:56:46 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

day 28 4/27/98

Today, we worked through homeworks.


\section{NP-hard approximation}


\subsection{Global wiring problem}

There is some array of locations. The goal is to connect some pairs of locations
in the array. The goal is to minimize the number of wires crossing a boundary
between adjacent locations.

Constraints:

\begin{itemize}
\item at most one bend. 
\end{itemize}
The problem is NP hard.

The problem can be rewritten as an integer programming problem.


\subsection{integer programming formulation}

For each pair, \( N_{i} \), of locations, introduce 2 variables, \( x_{i0},x_{i1} \).

Let:

\begin{itemize}
\item \( T_{b0}=\{i|N_{i}\textrm{ passes through b if }x_{i0}=1\} \)
\item \( T_{b1}=\{i|N_{i}\textrm{ passes through b if }x_{i1}=1\} \)
\end{itemize}
The integer programming problem is then:

minimize \( w \) where 

\begin{itemize}
\item \( x_{i0},x_{i1}\in \{0,1\}\forall N_{i} \) 
\item \( x_{i0}+x_{i1}=1 \) 
\item \( \sum _{i\in T_{b0}}x_{i0}+\sum _{i\in T_{b1}}x_{i1}\leq w \)
\end{itemize}

\subsection{linear program relaxation}

Replace the first constraint with \( 0\leq x_{i0},x_{i1}\leq 1 \) to turn the problem into a linear programming
problem. The linear programming solution must have \( W_{LP}\leq W_{IP} \), giving a lower bound on
the integer programming solution.

\end{document}