Algorithms & Complexity

Group

Research

Teaching

Theses

back to main page

Logbook Approximation Algorithms - Winter 2021/22

• Q & A - 17.02.2022




• Lecture 26 - 15.02.2022:
  Euclidean MinTSP, recap of algorithm and running time, proof of approximation ratio, random origin of the grid, small expected detour when turning C^* into a legal tour, with probability at least 1/2 the optimal legal tour has approximation ratio 1+ε, derandomization by running the algorithm for all O(n⁴) possible locations for the origin. Branch and bound, general idea, branching operator, bounding function, examples for Vertex Cover and Knapsack problems.

  Literature:
  • Notes: Section 3.4



• Lecture 25 - 10.02.2022:
  Euclidean MinTSP, preparation with moving, scaling, and rounding, recursive partition of ground sqaure results in a quad-tree, definition of doors and legal tour, visiting schemes for squares, recursive construction of tour by combination and optimization over compatible visiting schemes. Running time dominated by number of visiting schemes (exponential in the number of doors for a square), approximation ratio by random perturbation of grid

  Literature:
  • Notes: Section 3.4



• Lecture 24 - 08.02.2022:
  Shortest Common Superstring, cycle cover algorithm, recap, concatenation of cycle strings, total length of cycle covers v_k lower bounds the length of an optimal superstring, proof of approximation ratio 2 for non-periodic strings, proof of ratio 4 for general strings using an Overlap-Lemma. Euclidean MinTSP, definition, preparation of the instance with moving, scaling, and rounding.

  Literature:
  • Notes: Sections 2.7.2, 3.4



• Lecture 23 - 03.02.2022:
  Shortest Common Superstring, problem definition, superstring resulting from orderings of strings, greedy superstring algorithm, results and conjectures. Cycle cover algorithm, overlap graph, superstrings as Hamiltonian paths, cycle decomposition, computing a max-weight cycle decomposition in an overlap graph

  Literature:
  • Notes: Section 2.7



• Lecture 22 - 01.02.2022:
  Maximum coverage problem, example, greedy algorithm. Set functions, properties (normalized, monotone, submodular). Maximizing a submodular function subject to a cardinality constraint, greedy algorithm, proof of approximation ratio e/(e-1), extensions

  Due to a recording error, there is no video of this lesson.

  Literature:
  • Notes: Section 2.6



• Lecture 21 - 27.01.2022:
  Makespan scheduling on unrelated machines, graph representation, ILP formulation with integrality gap m. Parametric pruning of LP relaxation, find smallest upper bound T^* of the makespan that makes pruned LP feasible, round a corner of that LP. Proof of approximation ratio 2, properties of corners, graph H(x) for fractionally assigned tasks is a pseudo-forest, rounding via perfect matching in H(x).

  Literature:
  • Notes: Section 5.3.7



• Lecture 20 - 25.01.2022:
  Steiner tree problem, Steiner forest problem, ILP and LP dual, primal-dual algorithm, example execution. Polynomial-time implementation by maintaining only non-zero dual variables, proof of approximation ratio of 2 by showing "on-average" approximation of dual complementary slackness in each iteration of the algorithm.

  Literature:
  • Notes: Section 6.6



• Lecture 19 - 20.01.2022:
  Facility Location, recap problem definition, ILP and dual LP, primal-dual algorithm, polynomial time by computing the next time for any event, each client contributes dual payment to at most one opening cost, approximate primal complementary slackness when "rerouting" clients to some not-too-distant open facility, proof of approximation ratio 3.

  Literature:
  • Notes: Section 6.5



• Lecture 18 - 18.01.2022:
  Set Cover, greedy algorithm, proof of approximation ratio H_m using primal-dual arguments. Single-source single-sink shortest path problem, ILP using s-t-cuts, dual program, connection to set cover, primal-dual algorithm, proof of optimality, interpretation as Dijkstra's algorithm.

  Literature:
  • Notes: Sections 6.3.2, 6.4



• Lecture 17 - 13.01.2022:
  Primal-dual algorithms, idea and general structure, primal-dual algorithm for set cover, examples, proof of approximation ratio f. Primal and dual complementary slackness, violation of dual complementary slackness leads to approximation ratio. Greedy algorithm for set cover, approximation ratio, comments.

  Literature:
  • Notes: Sections 6.2, 6.3.1, 6.3.2



• Lecture 16 - 11.01.2022:
  Duality of linear programs, example, lower bounding argument for LPs in canonical form with non-negative variables. Construction of the dual in general, bounding argument for general LPs, examples. Weak duality, strong duality, types of pairs for primal and dual LPs (bounded, unbounded, infeasible). Complementary slackness conditions of optimal solutions.

  Literature:
  • Notes: Section 6.1



• Lecture 15 - 09.12.2021:
  Routing and path selection, ILP formulation, linear relaxation, path decomposition, rounding yields congestion W^* + $\sqrt{3\; W*\; ln(n²/\epsilon )}$ with probability at least 1-ε, proof using Chernoff bounds. Duality of linear programs, example, lower bounding argument for LPs in canonical form with non-negative variables.

  Literature:
  • Notes: Sections 5.3.6, 6.1



• Lecture 14 - 07.12.2021:
  Set Cover problem, proof that repeated randomized rounding yields a feasible set cover with constant probability. Integrality gap, examples. Max-Sat problem, linear program, simple rounding, LP rounding, bounds on the probability to satisfy a clause, proof of 4/3-approximation, bounds on the integrality gap.

  The bounds on the probabilities in Lemma 12 and Theorem 36 are corrected in the notes.

  Part I of the course ends with the discussion of integrality gap.

  Literature:
  • Notes: Sections 5.3.3, 5.3.4, 5.3.5



• Lecture 13 - 02.12.2021:
  Vertex Cover problem, deterministic rounding of fractional LP optimum yields a 2-approximation. Independent Set problem, fractional and integral optima differ in value by up to factor of Θ(n). MaxMatching problem, LP relaxation with incidence matrix as constraint matrix, total unimodularity for bipartite graphs, fractional LP optimum has integral entries. Set Cover problem, generalizes Vertex Cover, repeated randomized rounding, proof of approximation ratio O(ln m)

  Literature:
  • Notes: Section 5.3.1, 5.3.2, 5.3.3



• Lecture 12 - 30.11.2021:
  Linear programming, definitions, solution space is a convex polytope. Infeasible, unbounded, bounded LPs. Optimization by moving into (opposite) direction of c, definition of a corner via linearly independent constraints that are exactly fulfilled, neighboring corners. LP in standard form, transformation into standard form, corners via choice of non-basic variables that are set to 0, basic variables, computation of x_B via matrix inversion, Simplex algorithm, sketch of basis exchange as a move to a neighboring corner, exponential worst-case running time of Simplex, polynomial-time algorithms for LPs

  Literature:
  • Notes: Section 5.2



• Lecture 11 - 25.11.2021:
  Facility location problem, review of problem and algorithm, upper bound of 5 on the approximation ratio of local optima (second part), local search with significant improvement steps, approximate local optima, polynomial bound on the running time, approximation ratio transfers to approximate local optima. Linear programming, canonical form, examples.

  Literature:
  • Notes: Sections 4.4, 5.1



• Lecture 10 - 18.11.2021:
  Local search problems, complexity class PLS, PLS-reduction, PLS-completeness. Examples of PLS-complete problems: Minimum Balanced Cut with 2k-flip neighborhood, MinTSP with 2k-flip neighborhood. Facility Location, problem definition, swap neighborhood, local search algorithm, bounding the approximation ratio of local optima: Lower bound of 3-ε for every constant ε > 0, upper bound of 5 (first part).

  Literature:
  • Notes: Sections 4.3, 4.4



• Lecture 9 - 16.11.2021:
  k-Center problem, Greedy algorithm with ratio 2, hardness of approximation within ratio 2-ε, reduction from DominatingSet. k-Median problem, local search algorithm with ratio 5 (without proof). Local search, generic template for strict local search, discussion of starting solution, neighborhood relation, choice of neighhor. Examples: Gradient Descent, Vertex Cover

  Literature:
  • Notes: Sections 4.1, 4.2



• Lecture 8 - 11.11.2021:
  Dynamic programming, Weighted Interval Scheduling problem, optimal algorithm. Knapsack problem, dynamic program, running time O(nW) with W = sum of weights, pseudopolynomial time. FPTAS using weight scaling, bounds on running time and approximation ratio. Dynamic programs for trees, optimal algorithm for Weighted Vertex Cover on trees.

  Literature:
  • Notes: Sections 3.1, 3.2, 3.3



• Lecture 7 - 09.11.2021:
  Bin Packing, Next-Fit, First-Fit, First-Fit-Decreasing (FFD), approximation guarantees for Next-Fit and FFD, hardness of approximation within ratio 3/2-ε for small instances with b^* = 2. Asymptotic PTAS, auxiliary instance of big items using a small number of different item sizes, optimal solution of auxiliary instance by enumeration, assign small items with First-Fit. Bounds on running time and approximation guarantee.

  Literature:
  • Notes: Section 2.5



• Lecture 6 - 04.11.2021:
  MinTSP, hardness of approximation via reduction from the HamiltonianCycle problem. Metric MinTSP, definition, MST-based approximation algorithm with ratio 2, Christofides-Serdyukov algorithm with ratio 3/2, Nearest- and Farthest-Insertion, improved results for special cases.

  Literature:
  • Notes: Sections 2.4, 2.4.1, 2.4.2



• Lecture 5 - 02.11.2021:
  MatroidScheduling, two cases for the proof of extendability. k-matroids, weighted MaxMatching, Greedy has approximation ratio 2, properties of k-matroids (greedy k-optimality, k-extendability, k-maximal cardinality), k-exchange property, connection to matroids and k-matroids, MaxTSP yields a 3-matroid, intersection of k matroids is k-matroid. MinTSP, inapproximability in the general case.

  Literature:
  • Notes: Sections 2.3, 2.4, 2.4.1



• Lecture 4 - 28.10.2021:
  Three matroid properties hold for cycle-free subsets of edges, equivalence proof, examples: graphic, matrix, uniform matroid. MatroidScheduling, definition of independent sets, efficient implementation of Greedy, proof of matroid property (downward-closed and extendability).
  
  Extendability for MatroidScheduling requires some more arguments, see next lecture and notes (Lemma 2).

  Literature:
  • Notes: Section 2.2



• Lecture 3 - 26.10.2021:
  Greedy algorithms, priority algorithms, IntervalScheduling, optimal greedy algorithm, proof of optimality. MinSpanningTree, Kruskals algorithm is optimal greedy algorithm, proof of optimality. Downward-closed set systems, weights, examples. Three properties (greedy optimality, extendability, maximal cardinality) and their equivalence, matroid notion and definitions.

  Literature:
  • Notes: Sections 2.1, 2.2



• Lecture 2 - 21.10.2021:
  Definition PTAS and FPTAS, PTAS for Makespan Scheduling with constant number of machines, no FPTAS for problems with integral solution values of polynomial size (Vertex Cover, Clique, etc.), 2-approximation for Vertex Cover, lower bound on the approximation ratio for Clique, landscape of complexity classes

  Literature:
  • Notes: Sections 1.3, 1.4



• Lecture 1 - 19.10.2021:
  Makespan Scheduling, ListScheduling computes a solution of value at most (2-1/m) times the best makespan, there are instances where this guarantee is tight. Examples of optimization problems, Vertex Cover, Clique, Maximum Matching. Decision vs. optimization problems, if decision version is hard, optimization cannot be easy. Definition of approximation ratio for minimization and maximization problems.

  Literature:
  • Notes: Sections 1.1, 1.2