105 lines
3.0 KiB
Typst
105 lines
3.0 KiB
Typst
#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
|
|
$
|