#import "@preview/simple-ntnu-report:0.1.2": ntnu-report, un
#import "@preview/zero:0.5.0": num
#import "@preview/physica:0.9.8": *

#let text-size = 12pt
#let white = rgb("#F8F8F2")
#let black = rgb("#282A36")
#let red = rgb("#FF5555")
#let orange = rgb("#FFB86C")
#let yellow = rgb("#F1FA8C")
#let green = rgb("#50FA7B")
#let cyan = rgb("#8BE9FD")
#let purple = rgb("#BD93F9")
#let pink = rgb("#FF79C6")

#set page(fill: black)

#set text(size: text-size, fill: white)

#show: ntnu-report.with(
  length: "short",

  title: "assignment 2",
  subtitle: "tdt4125 - algorithm construction",
  authors: (
    (
      name: "fredrik robertsen",
    ),
  ),

  date: datetime.today(),

  language: "english",
  column-number: 2,

  number-headings: false,
  
  show-toc: false,
  show-figure-index: false,
  show-table-index: false,
  show-listings-index: false,
)

#set text(size: text-size, fill: white)
#set math.equation(numbering: none)

#show heading: set text(style: "italic")
#show heading.where(level: 2): it => {box(
    height: text-size * 1.3,
    width: 100%,
    outset: 2.5%,
    radius: 25%,
    fill: green,
    align(horizon, text(fill: black, it.body))
)}
#show heading.where(level: 3): it => {
  box(strong(it.body) + h(0.5em))
}

#let ll(l, t) = text(cyan)[#link(l)[#t]]

== task 1
this sounds like the #ll("https://en.wikipedia.org/wiki/Vertex_cover")[vertex cover problem], but with additional vertex weights to minimize.

=== a)
recall the general key components of a linear program
- problem input vector $x$
- coefficient vector $c$
- constraint matrix $A$
- target vector $b$
such that we minimize $c^TT x$ with respect to $A x >= b$.

here we can interpret the input vector $x$ as a binary vector where the $i$-th bit encodes the inclusion of a given node $v_i in V$ in the subset $C$. $x$ has as many bits as there are vertices.

furthermore, the vector $c$ represents the weights of the vertices such that $
c^TT x = sum_(v in V) c_v x_v = sum_(v in C) c_v
$ becomes the minimization goal.

we can express the binary string $x$ through constraints
- $x_u + x_v >= 1 quad forall (u, v) in E$
- $x_v in {0, 1} quad forall v in V$

the former constraint ensures that every edge is covered by at least one endpoint.

bringing it all together
$
    min sum_(v in V) c_v x_v \
    "s.t." quad x_u + x_v >= 1 quad forall (u, v) in E \
    x_v in {0, 1} quad forall v in V
$
is our complete linear integer program.

we have implicitly defined $A$ to be the $|E| times |V|$-matrix that has $1$-entries for vertices $v$ where $e = (u, v)$. it is zero otherwise. 

=== b)
by relaxing the linear integer program we let $0 <= x_v <= 1$. this can be shortened to saying $x_v >= 0$ since the first constraint forces $x_v <= 1$. requiring a positive value is a common restriction on linear programs and allows us to take the dual. 

we then obtain the dual program
$
    max bold(1)^TT y = sum_(e in E) y_e \
    "s.t." quad A^TT y <= c \
    <=> sum_(v in e) y_e <= c_v \
    quad forall v in V, quad y >= 0
$