%%Do not change font size
\documentclass[12pt]{article}
\usepackage{amsthm,amssymb,fullpage}
\begin{document}
\begin{center}
\begin{tabular}{|c|}
%\hline
\hline
CS 5800: Algorithms \hspace{9cm} K.Lieberherr, V. Pavlu\\
\hfill Due: April.~14, 2014\\
%CS 5800: Algorithms \hspace{9cm} \\
% Instructor: Virgil Pavlu \hfill Due: Mar.~15, 2012\\
% \\
{\bfseries \large Homework Module 11}\\ \hline
\end{tabular}
\end{center}
%\section{Write here}
%\textbf{\large{Instructions}}
\section{Submission Rules}
\begin{verbatim}
http://www.ccs.neu.edu/home/lieber/courses/algorithms/
cs5800/sp14/homeworks/submission-rules.pdf
\end{verbatim}
\section{Problems}
%\textbf{\large{Problems}}
\begin{enumerate}
%\item (25 pts) Exercise 24.1-3.
\item (25 pts) Exercise 24.2-2. Shortest Paths for DAGs
\item (25 pts) Exercise 24.3-2. Dijkstra's algorithm
%\item (Extra credit 30 pts) Problem 24-2.
%\item (30 pts) Explain in few lines the concept of transitive closure.
%\item (20 pts) Exercise 25.1-6 (the book uses different notation for the matrices). Also explain how to use this result in order to display all-pair shortest paths, enumerating intermediary vertices (or edges) for each path.
%\item (20 pts) Exercise 25.2-1.
\item (20 pts) Exercise 25.1-4. Shortest Paths and Matrix Multiplication.
%\item (25 pts) Exercise 25.2-6. (Extra Credit)
%\item (20 pts) Exercise 26.1-3. (Network Flow)
%\item (20 pts) Exercise 26.1-4.
%\item (20 pts) Exercise 26.2-2.
%\item (25 pts) Exercise 26.2-10 (Extra Credit)
\item (20 points) Plan your Wedding. (Concluding hw 5)
\begin{verbatim}
http://www.ccs.neu.edu/home/lieber/courses/algorithms/
cs5800/sp14/labs/wedding-organization.html
\end{verbatim}
We are looking for your algorithm that is guaranteed to find the
maximum seating arrangements in polynomial time.
You are welcome to test your algorithm by doing debates
but in this case we only grade the final result: your algorithm
and your argument for correctness.
\item{Approximation of Maximum Generalized Satisfiability Problems using Randomization (40 points)}
Consider Maximum Generalized Satisfiability problems using one relation $R$
given by its truth table.
An instance $S$ consists of $n$ Boolean variables used in $m$ constraints all
using relation $R$.
We call such an instance $S$ an $R$-instance.
The goal is to find an assignment to the Boolean variables
that maximizes the fraction of satisfied constraints
in a given $R$-instance.
For most $R$ this maximization problem is NP-hard.
Notation:
\[
assignments(S) =
\]
the set of all Boolean assignments to variables of the constraints $S$.
\[
fsat(S,J) =
\]
the fraction of satisfied constraints in constraints $S$ under assignment $J$.
Consider the following claim:
\[
ConstraintThresholdClaim=
\forall R \in {\rm Boolean Relations}~
\exists t \in [0,1]:
CTC(R,t)
\]
where
\[
CTC(R,t) =
\]
\[
\forall S \in R{\rm -instances} ~ \exists J \in assignments(S): fsat(S,J) \ge t
\]
and
\[
\exists S_0 \in R-instances ~ \forall J_0 \in assignments(S_0):
fsat(S_0,J_0)