Technische Universität Berlin

Research Seminar

The DISCOGA Research Seminar is a joint weekly seminar with the Discrete Optimization Group of Max Klimm at TUB. Speakers might talk about their own research, present open problems, give a survey about a specific topic, present a recent paper by other authors, or anything else that is interesting for the participating groups.

usual Time: Tuesday 14:00
usual Room: MA 313/314
Contact Martin Knaack for questions, suggestions, Zoom links, etc.

Past and Upcoming Talks

31.05.2022Equilibria in Multiclass and Multidimensional Atomic Congestion GamesMax Klimm (DISCO)own results
17.05.2022From Combinatorial Optimization to Gray codesArturo Merino (COGA)own results
10.05.2022Lower Bounds for Approximation Algorithms for the Steiner Tree ProblemEkin Ergen (COGA)own results
26.04.2022Parametric Min Cut ComplexityTom McCormickown results
19.04.2022Connectivity thresholds in random temporal graphsMalte Renken (TU Berin)own results
09.03.2022A time-expanded Knapsack Problem with quadratic constraintsChiara Fusar Bassinimaster thesis
15.12.2021Machine-Learned Prediction Equilibrium for Dynamic Traffic AssignmentTobias Harks (Uni Augsburg)own results
15.12.2021Training Neural Networks is even harderLinda Kleist (TU Braunschweig)own results
08.12.2021Convergence of a Packet Routing Model to Flows Over TimeLaura Vargas Koch (ETH Zürich)own results
01.12.2021Optimisation with Squared Lasso PenaltyValentin Kirchner (TU Berlin)own results
24.11.2021Efficient generation of elimination trees and Hamilton paths on graph associahedraArturo Merino (COGA)own results
17.11.2021Book Embeddings of Nonplanar Graphs with Small Faces in Few PagesSvenja Griesbach (DISCO)own results
10.11.2021Fractionally Subadditive Maximization under an Incremental Knapsack ConstraintDavid Weckbecker (TU Darmstadt)own results
10.11.2021Stochastic Probing with Increasing PrecisionKevin Schewior (Uni Köln)own results
27.10.2021Evaluating the Potential of Reinforcement Learning for Stochastic Machine Scheduling ProblemsMohammed Majthoub Almoghrabi (COGA)own results
20.10.2021Multidimensional Apportionment through Discrepancy TheoryJavier Cembrano (DISCO)own results
13.10.2021Additive approximation schemes for load balancing problemsMoritz Buchem (Maastricht University)own results
21.09.2021An Algorithm-Independent Measure of Progress for Linear Constraint PropagationBoro Sofranac (IOL)own results
14.09.2021Combinatorial Diameter of Random PolyhedraSophie Huiberts
17.08.2021A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton MethodKhai Van Tran (COGA)own results
20.07.2021Computational experiments and multiscale optimizationFrieder Smolny (COGA)own results
06.07.2021Restricted Adaptivity in Stochastic SchedulingDaniel Schmidt genannt Waldschmidt (COGA)own results
22.06.2021Evolution of BoostingMax-Georg Schorr (IOL)
15.06.2021Nash flows over time in MATSim?Theresa Ziemke (COGA)own result
08.06.2021Greedy strategies for exhaustive generationArturo Merino (COGA)survey
25.05.2021Borsuk’s problemPaco Criado (IOL)survey
11.05.2021Tackling Neural Network Expressivity via (virtual Newton) polytopesChristoph Hertrich (COGA)open problem
25.03.2021A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobsMartin Skutella (COGA)own results
18.03.2021Static and dynamic pricing of identical itemsMax Klimm (DISCO)own results
18.03.2021Robust conic optimization in PythonMaximilian Stahlberg (DISCO)master thesis
11.03.2021Set Curvature in Machine LearningThomas Kerdreux (IOL)own results
11.03.2021Differential Privacy for Machine LearningValentin Hartmann (EPFL)survey
04.03.2021Scheduling under Contact Restrictions - A Problem Arising in PandemicsDaniel Schmidt genannt Waldschmidt (COGA)own results
18.02.2021Greedy Batch-SchedulingGuillaume Sagnol (COGA)own results
04.02.2021Differentiable Optimization & Integration within Differentiable ProgrammingMathieu Besançon (IOL)survey
28.01.2021Online Scheduling of Deterministic and Stochastic Jobs on Unrelated MachinesSven Jäger (COGA)own results
21.01.2021Parametric Computation of Minimum Cost FlowsPhilipp Warode (DISCO)own results
14.01.2021Robust Optimization and LearningKartikey Sharma (IOL)own results
14.01.2021Neural Network Approximation TheoryShpresim Sadiku (IOL)survey
07.01.2021Contractibility vs CollapsibilityDavide Lofano (COGA)survey / own results
17.12.2020Efficient generation of rectangulations via permutation languagesArturo Merino (COGA)own results
10.12.2020Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse MatricesBoro Sofranac (IOL)own results
03.12.2020Local Acceleration of Conditional GradientsAlejandro Carderera (IOL, Georgia Tech)own results
26.11.2020Multidimensional Packing under Convex Quadratic ConstraintsRico Raber (COGA)own results
19.11.2020Learning Relations From Data With Conditional GradientsElias Wirth (IOL)own results
17.11.2020Understanding Neural Network Decisions is Hard - From Probabilistic Prime Implicants to Arc BendingStephan Wäldchen (TU Berlin)guest speaker
12.11.2020The artification of the so-called A.I. art and the creative industryThomas Kerdreux (IOL)discussion
12.11.2020Improved Bounds on the Competitive Ratio for Symmetric Rendezvous-on-the-Line with Unknown Initial DistanceKhai Van Tran (COGA)own results
05.11.2020Computing the Maximum Function with ReLU Neural NetworksChristoph Hertrich (COGA)own results
27.10.2020Frank-Wolfe with New and Practical Descent DirectionsCyrille Combettes (IOL, Georgia Tech)own results
09.10.2020Komplexität und Berechenbarkeit von robusten Schnitten in GraphenSebastian Ortmannsthesis talk
25.06.2020On the two-dimensional knapsack problem for convex polygonsArturo Merinoown results
12.06.2020Screening rules for Lasso and Optimal DesignsGuillaume Sagnolown results
05.06.2020Non-Clairvoyant Precedence Constrained SchedulingSven Jägerpaper presentation
26.05.2020Minimum-cost integer circulations in given homology classesSarah Morellown results
19.05.2020The Santa Claus ProblemDaniel Schmidt genannt Waldschmidtsurvey talk
05.05.2020Multi-commodity Nash flowsLeon Seringown results
28.04.2020The Maximum Leaf Spanning Tree Problem on Grid GraphsKarl Däubelopen problem
21.04.2020Derandomizing Unconstrained Submodular Function MaximizationKhai Van Tranpaper presentation
14.04.2020Representation Benefits of Deep Feedforward NetworksChristoph Hertrichpaper presentation
07.04.2020On the Robustness of Potential-Based Flow NetworksRico Raberown results
31.03.2020Some Aspects of Graph Sparsification in Theory and PracticeKarl Däubelown results
03.03.2020Symmetric Rendezvous-on-the-Line with Unkown Initial DistanceKhai Van Tranown results
03.03.2020Characterizing equatable graphs – node balancing by edge increments and decrementsNicolas Schneiderbachelor thesis
25.02.2020The complexity of cake cutting with unequal sharesÁgnes Csehguest speaker
13.02.2020Recognizing spaces in PolymakeDavide Lofanosurvey talk
28.01.2020On Equilibria in Atomic Splittable Flow Over Time GamesAntonia AdamikMaster's thesis
17.12.2019Modeling and Optimization for the Snapshot Imaging PolarimeterZhen Liusurvey talk
10.12.2019Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block LaplaciansPhilipp Warodeconference talk
03.12.2019Second-Order Stochastic Dominance and Applications in SchedulingGuillaume Sagnolsurvey talk
19.11.2019 Design of Computer Experiments based on Bayesian QuadratureLuc Pronzatoguest speaker
19.11.2019Percolation and its convergence to Stochastic Loewner EvolutionAlexandra Quitmannguest speaker
14.11.2019Degree-Bounded Polymatroids, with Applications to the Many-Visits TSPMatthias Mnichguest speaker
05.11.2019Scheduling stochastic jobs with release dates on a single machineSven Jägerown results
29.10.2019The minimum cost query problem on matroids with uncertainty areasArturo Merinoown results
22.10.2019Theoretical Aspects of Neural Networks for Solving Combinatorial Optimization ProblemsChristoph Hertrichown results
06.08.2019Orthogonal symmetric chain decompositionsSven Jägerconference talk
09.07.2019An Improved Upper Bound for the Ring Loading ProblemKarl Däubelown results
09.07.2019On the price of anarchy for flows over time with spillbackJonas IsraelMaster's thesis
02.07.2019Knapsack problem with quadratic constraintRico Raberown results
18.06.2019An unexpected connection between A-optimal designs and the Group LassoGuillaume Sagnolown results
28.05.2019The price of fixed assignments in stochastic extensible bin packingDaniel Schmidt genannt Waldschmidtconference talk
21.05.2019Approximating Total Weighted Completion Time on Identical Parallel Machines with Precedence Constraints and Release DatesSven Jägerown results
15.05.2019Nash flows over time with spillbackLeon Seringconference talk
07.05.2019Discrete Morse TheoryDavide Lofanosurvey
03.05.2019Monte Carlo approximation certificates for k-means clusteringSoledad Villarguest speaker
23.04.2019Single-source unsplittable flowsSarah Morellown results
03.04.2019Deep LearningChristoph Hertrichsurvey
23.01.2019First order methods for convex optimizationGuillaume Sagnollecture
04.12.2018Matching extendability in hypercubesJiri Finkguest speaker
20.11.2018 -
Reading Group: Machine LearningCOGAreading group
15.11.2018Scheduling a Proportionate Flow Shop of Batching MachinesChristoph Hertrichown results
24.10.2018Generalized flow, the net present value problem, and an open question in arithmetic computationNeil Olverguest speaker
16.08.2018Symmetry Handling for Integer ProgramsMarc Pfetschguest speaker
26.07.2018Fullerenes and Graphene PatchesElizabeth Hartungguest speaker
19.07.2018Gray Codes and Universal Cycles: Thinking Locally instead of GloballyAaron Williamsguest speaker
12.07.2018A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into BoxesAndreas Wieseguest speaker
28.06.2018Multiscale optimization of logistics networksFrieder Smolnyconference talk
21.06.2018Design of Optimal Experiments with Model UncertaintyGuillaume Sagnolsurvey
14.06.2018Fußball ist MathematikMartin Skutellarecreational
31.05.2018Distance-Preserving Graph ContractionsKarl Däubelown results
24.05.2018Gray codes and symmetric chainsSven Jägerconference talk
09.05.2018Diversity maximization in doubling metricsSarah Morellguest speaker
03.05.2018Scheduling a Proportionate Flowshop of Batching MachinesChristoph Hertrichguest speaker
19.04.2018Summary of the item relocation problemPaul Fournelown results
15.02.2018On the Complexity of Instationary Gas FlowsMartin Skutellaown results
08.02.2018Sparse Kneser graphs are HamiltonianTorsten Mützeown results
01.02.2018Algorithms for Massive GraphsAaron Bernsteinown results
25.01.2018Stochastic Machine Scheduling, Gammoids and Time-Expanded NetworksRico Raber, Khai Van Tranown results
18.01.2018Online Bipartite Matching with Amortized O(log^2 N) ReplacementsAaron Bernsteinown results
14.12.2017Incremental Cycle Detection and Topological Sort, Distance-preserving graph contractionsAaron Bernstein, Frieder Smolnyconference talks
07.12.2017A Comparison-Based Approach to Spanners and ContractionsKarl Däubelown results
30.11.2017Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine schedulingSven Jägerown results
23.11.2017Earliest Arrival Transshipments in Networks With Multiple SinksMiriam Schlöterown results
16.11.2017The Price of Fixed Assignments in Stochastic Extensible Bin PackingGuillaume Sagnolown results
09.11.2017Nash Flows with time-varying capacitiesJulian StegerMaster's thesis
09.11.2017Multi-Source Mult-Sink Nash Flows over TimeLeon Seringown results
19.10.2017Scheduling with Position-Dependent SpeedDaniel Schmidt genannt Waldschmidtown results
20.07.2017Graph Algorithms at ICALP 2017Frieder Smolnyconference report
04.07.2017Virtual Network Embedding Approximations: Leveraging Decomposable LP Formulations and Randomized RoundingMatthias Rostguest speaker
28.06.2017An improved deterministic algorithm for dynamic single source shortest pathsAaron Bernsteinown results
20.06.2017MST under Uncertainty in Theory and ExperimentsJulie Meißnerown results
08.06.2017Scheduling Maintenance Jobs in NetworksJulie Meißnerown results
30.05.2017Proximity results and faster algorithms for Integer Programming using the Steinitz LemmaRobert Weismantelguest speaker
23.05.2017Stochastic Scheduling of Heavy-Tailed JobsSven Jägerpaper presentation
09.05.2017Stochastic Machine SchedulingRico RaberMaster's thesis
07.03.2017Graph Contraction and Dynamic ProgrammingFrieder Smolnyown results
28.02.2017Worst case bound of the LRF rule for minimizing total weighted completion time on identical parallel machinesSven Jägerpaper presentation
07.02.2017A Combinatorial Upper Bound on the Length of Twang CascadesLeon Seringown results
03.01.2017Graph Compression and Linear ProgrammingKarl Däubelown results
13.12.2016Trimming and gluing Gray codesTorsten Mützeown results
05.12.2016Tight Bounds for Online TSP on the LineJan Hackfeldown results
21.11.2016A 2.542-Approximation for Precedence Constrained Single Machine Scheduling with Release Dates and Total Weighted Completion Time ObjectiveMartin Skutellaown results
17.05.2016Packing While Traveling: Mixed Integer Programming for a Class of Nonlinear Knapsack ProblemsFrank Neumannguest speaker
03.05.2016Quickest Transshipments & Submodular Function MinimizationMiriam Schlöterown results
19.04.2016Truthful Outcomes from Non-Truthful Position AuctionsFelix Fischerown results
05.04.2016Iterative Algorithms for Integrated Optimization ProblemsSven Jägerguest speaker
29.03.2016Recent developments in robust network flowsJannik Matuschkeown results
08.03.2016Online scheduling models with machine costCsanad Imrehguest speaker
26.01.2015Combinatorial Gray codes and the Chung-Feller theoremTorsten Mützeown results
08.12.2015Dealing with Big Data - An Introduction to Streaming AlgorithmsMartin Großreading group
24.11.2015On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner TreeAndreas Feldmannguest speaker
16.11.2015The Online Matrix-Vector Multiplication ConjectureYann Disserreading group
27.10.2015A Theory of Hardness for Polynomial TimeMartin Skutellareading group
13.10.2015Hamilton cycles in (bipartite) Kneser graphsTorsten Mützeguest speaker
19.06.2015Improved Online Algorithms for the Machine Covering Problem with Bounded MigrationWaldo Gálvezguest speaker
05.06.2015Mechanism Design for Crowdsourcing: An Optimal 1–1/e Competitive Budget-Feasible Mechanism for Large MarketsMiriam Schlöterreading group
05.05.2015Global EDF Scheduling of Systems of Conditional Sporadic DAG TasksAlberto Marchetti-Spaccamelaguest speaker
28.04.2015Lower bounds on the sizes of integer programs without additional variablesAlexander Richterreading group
07.04.2015Towards Understanding the Smoothed Approximation Performance of the 2-OPT heuristicMarvin Künnemannguest speaker
31.03.2015Polynomiality for Bin Packing with a Constant Number of Item Types (part II)Lin Chenreading group
24.03.2015Polynomiality for Bin Packing with a Constant Number of Item Types (part I)Lin Chenreading group
17.03.2015On the power of sampling in stochastic optimizationRoman Rischkereading group
10.03.2015A strongly polynomial time algorithm for multicriteria global minimum cuts (part II)Sebastian Schenkerreading group
17.02.2015A strongly polynomial time algorithm for multicriteria global minimum cuts (part I)Sebastian Schenkerreading group
03.02.2015Undirected connectivity in log-spaceJan Hackfeldreading group
27.01.2015Network improvement for equilibrium routingAntje Bjeldereading group
20.01.2015The Burden of Risk Aversion in Selfish RoutingEvdokia Nikolovaguest speaker
13.01.2015Subgame-perfect equilibriaChristoph Hansknechtreading group
09.12.2014Threesomes, Degenerates, and Love TrianglesJan-Philipp Kappmeierreading group
02.12.2014An improved approximation algorithm for the stable marriage problem with one-sided tiesÁgnes Csehreading group
25.11.2014Faster Maximum-Flow Computation via Electrical FlowsKevin Schewiorreading group
18.11.2014Optimal Coordination Mechanisms for Multi-Job Scheduling GamesFidaa Abed (MPII)guest speaker
11.11.2014Recent Improvements for the s-t path TSPJulie Meißnerreading group
04.11.2014The Complexity of the parity argument and other inefficient proofs of existenceMax Klimmreading group
28.10.2014A strongly polynomial algorithm for generalized flow maximizationMartin Großreading group
21.10.2014A short introduction to extended formulationsJannik Matuschkereading group
14.10.2014The Power of a Pebble: Exploring and Mapping Directed GraphsYann Disserreading group
07.10.2014Integer multi-commodity flows and the cut conditionMartin Skutellareading group