Bachelor Theses

Bachelor Theses in Discrete Optimization

In general, a bachelor thesis is based on a mathematical article that is reviewed and expressed with own words. Frequently, this comes along with small implementation tasks or computational experiments.

The time horizon of a bachelor thesis is six months. Before starting, be sure to read the Handout (opens in new tab) on bachelor theses in discrete optimization. The work is usually registered when the student became acquainted with the topic. For the preparation of the thesis, a TeX template is available in Downloads. Alternatively, you an also use the template of the“Arbeitstechniken” lecture from WS15/16.

Requirements

The successful pass of the course “Introduction to Optimization” is required; in addition, the active participation in an optimization seminar is strongly recommended.

Contact

Prof. Pfetsch, Prof. Disser and staff members of the research group

  • The sparest solution of the union of finite polytopes via its nonconvex relaxation
    (Prof. Pfetsch)
  • Latent Space Optimization: Solving Discrete, High-dimensional and Expensive Problems via the Latent Space of Deep Generative Models
    (Prof. Pfetsch)
  • The constraint Reliable Shortest Path Problem in stochastic Time-Dependent Networks
    (Prof. Pfetsch)
  • Multicommodity flows in symmetric digraphs
    (Prof. Pfetsch)
  • Analysis and Test of Algorithms for the Monoid Resource Constrained Shortest Path Problem
    (Prof. Pfetsch)
  • Generative Adversarial Nets
    (Prof. Pfetsch)
  • Algorithm to solve the Steiner tree problem
    (Prof. Pfetsch)
  • Robust regret combinatorial optimization for shortest path problems
    (Prof. Pfetsch)
  • Solving all-pair shortest path by single-source computations: Theory and Practice
    (Prof. Pfetsch)
  • Online Dial-a-Ride
    (Prof. Disser)
  • Solutions for Knapsack problem with conflict and forcing graphs of bounded clique-width
    (Prof. Pfetsch)
  • Algorithms to solve the Survivable-Network-Design-Problem
    (Prof. Pfetsch)
  • All pairs shortest path algorithm with single-source compution
    (Prof. Pfetsch)
  • Genetic Algorithms for the Dial-a-Ride Problem
    (Prof. Disser)
  • Solving the rectilinear distance problem
    (Prof. Pfetsch)
  • Scheduling for a processor sharing system with linear slowdown
    (Prof. Pfetsch)
  • Minimum equivalent precedence relation systems
    (Prof. Pfetsch)
  • Optimal ordering of statistically dependent tests
    (Prof. Pfetsch)
  • Hardness of the burning number of a graph
    (Prof. Pfetsch)
  • Exact algorithms for the solution of the grey pattern quadratic assignment problem
    (Prof. Pfetsch)
  • Proof of a O(log2k) bound for the K-Server problem on HST's
    (Prof. Disser)
  • Algorithms for non-linear and stochastic resource constrained shortest paths
    (Prof. Pfetsch)
  • Containment of Virus Expansion in Graphs
    (Prof. Disser)
  • State of the Art for the List Update Problem
    (Prof. Disser)
  • Shortest Distances on Undirected Graphs
    (Prof. Pfetsch)
  • Blocking Unions of arborescences
    (Prof. Pfetsch)
  • Efficient recovery of block-sparse signals
    (Prof. Pfetsch)
  • Matching Interdiction
    (Prof. Pfetsch)
  • Efficient solutions for weight-balanced partitioning problems
    (Prof. Pfetsch)
  • Approximation algorithms for maximum K-vertex cover
    (Prof. Pfetsch)
  • Machine Learning for Fraud Detection in E-Commerce
    (Prof. Pfetsch)
  • Shortest Paths for Planar Graphs
    (Prof. Pfetsch)
  • Covering problems in edge- and knot-weighted graphs
    (Prof. Pfetsch)
  • On the robust shortest path problems
    (Prof. Pfetsch)
  • An algorithm for solving parametric flow maximization problems
    (Prof. Pfetsch)
  • The K-Server Problem
    (Prof. Disser)
  • Single machine scheduling with supporting tasks
    (Prof. Pfetsch)
  • A testbed for online Dial-a-Ride on the line
    (Prof. Disser)
  • Anchored rectangle and square packings
    (Prof. Pfetsch)
  • Improving Bounds for Incremental Maximization
    (Prof. Disser)
  • Max Flows in O(nm) Time, or Better
    (Prof. Pfetsch)
  • Routing in Netzwerken mit Kapazitäten
    (Prof. Pfetsch)
  • Belegungsplanung mit ressourcenabhängigen Bearbeitungszeiten
    (Prof. Pfetsch)
  • Polynomielle Approximationsschemata für das budgetierte Matching-Problem und das budgetierte Matroid-Intersektions-Problem
    (Prof. Pfetsch)
  • Polynomieller Netzwerksimplexalgorithmus für Kosten-minimale Flüsse
    (Prof. Pfetsch)
  • Scheduling Unrelated Parallel Machines and Graph Balancing
    (Prof. Pfetsch)
  • Berechnung kürzester Wege auf Flächen
    (Prof. Pfetsch)
  • Optimale Approximation mit stückweise affinen Modellen
    (Prof. Pfetsch)
  • Gewichts-beschränkte kürzeste Wege Probleme
    (Prof. Pfetsch)
  • Der Seitenflächen-Algorithmus für lineare Optimierungsprobleme
    (Prof. Pfetsch)
  • Compact Flows
    (Prof. Pfetsch)
  • Solving Combinatorial Optimization Problems via Inclusion-Exclusion
    (Prof. Pfetsch)
  • The Stoer-Wagner algorithm for minimum cuts in undirected graphs
    (Prof. Pfetsch)
  • A recognition algorithm for unit interval graphs
    (Prof. Pfetsch)
  • Approximationsalgorithmen für das Scheduling auf parallelen Maschinen
    (Prof. Pfetsch)
  • Differences between maximum degrees and clique numbers in graphs
    (Prof. Pfetsch)
  • Image Segmentation via Minimum Cuts in Planar Graphs
    (Prof. Pfetsch)
  • MPEC-basierte Heuristiken für L0 -Minimierung
    (Prof. Pfetsch)
  • Solving Covering Problems with Violations and Probabilistic Constraints
    (Prof. Pfetsch)
  • Modelle des Steinerbaumproblems
    (Prof. Pfetsch)
  • Approximationsalgorithmen für verallgemeinerte Flüsse
    (Prof. Pfetsch)
  • Nichtnull-Strukturen von Hesse-Matrizen und Sternfärbung
    (Prof. Pfetsch)
  • Least Infeasible Flows
    (Prof. Pfetsch)
  • Robuste Optimierungsansätze für das Flugzeugumlaufproblem
    (Prof. Pfetsch)
  • Investigation of a parametric active set method applied to linear programs
    (Prof. Pfetsch)
  • Reducing Linear Programs to Basis Pursuit
    (Prof. Pfetsch)
  • Neue Algorithmen für verallgemeinerte Netzwerkflüsse
    (Prof. Pfetsch)
  • Lösung von konvexen Mehrgüterflussproblemen
    (Prof. Pfetsch)
  • Der Algorithmus von Truemper für verallgemeinerte Netzwerke
    (Prof. Pfetsch)
  • Algorithmen für Flüsse über die Zeit
    (Prof. Pfetsch)
  • Applications of Minimal Cuts in Graphs in Image Segmentation
    (Prof. Pfetsch)
  • Sparsification of matrices
    (Prof. Pfetsch)
  • Methoden zur Dünnbesetzung von Matrizen und ihre Auswirkungen auf die Performanz von l1-Lösern
    (Prof. Pfetsch)
  • Untersuchung der Eindeutigkeit der dünn besetztesten Lösungen linearer Gleichungssysteme
    (Prof. Pfetsch)
  • Vergleich des Orthogonal Matching und Basis Pursuit
    (Prof. Pfetsch)
  • Partiätsbedingungs-Codes mit geringer Dichte und Compressed Sensing
    (Prof. Pfetsch)
  • Experimentelle Untersuchung des Verfahrens von Juditsky und Nemirovski
    (Prof. Pfetsch)
  • Terminierungskriterien bei SPGL1 und CPLEX
    (Prof. Pfetsch)
  • Projektionen zur Lösung von l1-Problemen
    (Prof. Pfetsch)
  • Analyse und praktische Tests für Nesterov's Algorithmus (NESTA)
    (Prof. Pfetsch)
  • Optimales Schätzen von OD-Matrizen
    (Prof. Pfetsch)
  • Verallgemeinerung geometrischer Schnittebenen
    (Prof. Pfetsch)
  • Integrierte Klassifikation von Hyperebenen und Merkmal-Auswahl
    (Prof. Pfetsch)
  • Homotopy method for l1-minimization
    (Prof. Pfetsch)
  • Die Zhang und Donoho Kriterien zur Rekonstruktion via l1-Minimierung
    (Prof. Pfetsch)
  • Über dünnbesetzte Repräsentanten in beliebigen redundanten Basen
    (Prof. Pfetsch)
  • Dünnbesetzte Repräsentanten in Paaren von Basen
    (Prof. Pfetsch)
  • Empirische Untersuchung der Exact Recovery Condition (ERC)
    (Prof. Pfetsch)