\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS7800}{Advanced Algorithms}{Fall 2014}{29 November 2014}{23}

\begin{center}
\Large{\bf Problems of the Week -- 17 to 21}
\end{center}

{\bf 17. Maximum satisfiability}

In the maximum satisfiability problem, we are given a set ${\cal C}$
of $m$ clauses over $n$ variables and the goal is to determine a
boolean assignment to the $n$ variables that maximizes the number of
satisfied clauses.  In class, we saw a randomized $7/8$-approximation
for the special case where there are 3 literals per clause, and a
$1/2$-approximation for the general case.  Here, we consider an
alternative algorithm.

Write the maximum satisfiability problem as an integer linear program
by having an LP variable $x_i$ for each boolean variable $v_i$ and a
linear constraint for each clause.

Consider the following randomized algorithm.  Solve the linear
relaxation for the above integer linear program to obtain solution
$x^*$.  Set each boolean variable $v_i$ to $1$ with probability equal
to $x^*_i$.  Show that the expected number of clauses satisfied is at
least $\mbox{OPT}\cdot(1 - (1 - 1/q)^q)$, where $q$ is the maximum
number of literals in a clause and OPT is the optimal value.

{\bf 18. Greedy online learning}

In the online learning problem we studied in class, we have $n$
experts, each giving a binary prediction for an event in each step.
Suppose we consider a greedy procedure for combining their
predictions: in each step, we select the prediction of the expert that
has the highest correct predictions until that step; in case of ties,
we select the expert with the smallest index.

Show that an adversary can ensure that the ratio of the number of
mistakes made by the online learning algorithm to the number of
mistakes made by the best expert can be made to be at least $n$.

{\bf 19. Maximum cut with an additional constraint}

In class, we studied two $1/2$-approximation algorithms for the global
maximum cut problem, the problem of finding a maximum-size cut in a
given graph.  One algorithm was a greedy algorithm, and the other a
randomized algorithm.

Consider the maximum cut problem with the additional constraint that
for two given sets $S_1$ and $S_2$ of pairs of vertices, we need to
ensure that every pair of vertices in $S_1$ is on the same side of the
cut, while every pair of vertices in $S_2$ is separated by the cut.

Extend the randomized algorithm to the above problem, and analyze its
approximation ratio.

{\bf 20. Trading currencies}

You are embarking on a trip to Europe and would like to purchase the
maximum number of Euros possible for $D$ US Dollars.  Given the rate
at which dollar is sliding with respect to many currencies, you try to
perform this exchange through a collection of trades through other
currencies.  For instance, you may exchange some of your dollars for
British pound, some of which you exchange for Japanese yen, which you
convert to Euros.

You log on to your currency trading account on oanda.com with the goal
of maximizing the number of Euros you can get for $D$ US Dollars
today.  Oanda offers you a fixed rate $r_{ij}$ for converting any
currency $i$ into any other currency $j$, but imposes a limit
$\ell_{ij}$ on how much of currency $i$ you can convert to currency
$j$ on a given day, for all ordered pairs $(i,j)$.  Assume that there
are no arbitrage opportunities -- that is, there is no directed cycle
of currency trades whose product of rates exceeds 1.  (Also assume
that there are no other individual transaction fees.)

Give a polynomial-time algorithm to solve the above problem.  Show
that it is possible to achieve your objective without ever borrowing
currency, and ending the day with no other currency except Euros and
possibly US Dollars.

{\bf 21. Cheapest short paths}

Let $G = (V,E)$ be a directed graph, and $\ell: E \rightarrow N$ and
$c: E \rightarrow N$ be two functions, where $N$ is the set of
positive integers.  We call $\ell(e)$ to be the length of edge $e$ and
$c(e)$ to be the cost of edge $e$.  

Given $G$, $\ell$, $c$, a source $s \in V$, a destination $t \in V$,
and an integer $L$, design an algorithm for finding a path from $s$ to
$t$ with length at most $L$ and whose cost is smallest among all paths
from $s$ to $t$ of length at most $L$.  (If no such path exists, then
your algorithm should indicate so.)  The worst-case running time of
your algorithm must be polynomial in $|V|$, $|E|$, $L$, and the sizes
of $\ell$ and $c$.
\end{document}