Friedrich Eisenbrand
EPFL SB MATH DISOPT
MA C1 553 (Bâtiment MA)
Station 8
1015 Lausanne
+41 21 693 25 60
+41 21 693 77 88
Office: MA C1 553
EPFL › SB › MATH › DISOPT
Site web: https://disopt.epfl.ch/
+41 21 693 25 60
Office: MA C1 553
EPFL › SB › SB-SMA › SMA-ENS
Site web: https://sma.epfl.ch/
+41 21 693 25 60
Office: MA C1 553
EPFL › IC › IC-DEC › IC-DO
Site web: https://ic.epfl.ch/page8797.html
+41 21 693 25 60
Office: MA C1 553
EPFL › VPA › VPA-AVP-DLE › AVP-DLE-EDOC › EDMA-ENS
+41 21 693 25 60
Office: MA C1 553
EPFL › VPA › VPA-AVP-DLE › AVP-DLE-EDOC › EDMA-GE
Site web: https://go.epfl.ch/phd-edma
Integer Linear Programming for Unsupervised Training Set Selection in Molecular Machine Learning
MACHINE LEARNING-SCIENCE AND TECHNOLOGY. 2025. DOI : 10.1088/2632-2153/adcd38.Integer points in the degree-sequence polytope
DISCRETE OPTIMIZATION. 2025. DOI : 10.1016/j.disopt.2024.100867.Forall-exist statements in pseudopolynomial time
2025. 2025 ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, US, 2025-01-12 - 2025-01-15. p. 2225 - 2233. DOI : 10.1137/1.9781611978322.73.Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
2024. 65th Annual Symposium on Foundations of Computer Science, Chicago, United States, 2024-10-27 - 2024-10-30. p. 1610 - 1620. DOI : 10.1109/focs61266.2024.00100.An Improved Bound on Sums of Square Roots via the Subspace Theorem
2024. 40 International Symposium on Computational Geometry, Athens, Greece, 2024-06-11 - 2024-06-14. DOI : 10.4230/LIPIcs.SoCG.2024.54.From approximate to exact integer programming
Mathematical Programming. 2024. DOI : 10.1007/s10107-024-02084-1.Machine-learning quantum-chemical properties of molecules and chemical reactions
Lausanne, EPFL, 2024. DOI : 10.5075/epfl-thesis-10980.Reducibility bounds of objective functions over the integers
Operations Research Letters. 2023. DOI : 10.1016/j.orl.2023.10.001.Geometric Considerations in Lattice Programming
Lausanne, EPFL, 2023. DOI : 10.5075/epfl-thesis-9934.Results on Sparse Integer Programming and Geometric Independent Sets
Lausanne, EPFL, 2023. DOI : 10.5075/epfl-thesis-10125.Metric learning for kernel ridge regression: assessment of molecular similarity
Machine Learning-Science And Technology. 2022. DOI : 10.1088/2632-2153/ac8e4f.Approximate CVPp in time 2(0.802n)
Journal Of Computer And System Sciences. 2022. DOI : 10.1016/j.jcss.2021.09.006.New Results in Integer and Lattice Programming
Lausanne, EPFL, 2020. DOI : 10.5075/epfl-thesis-7727.Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
Acm Transactions On Algorithms. 2020. DOI : 10.1145/3340322.An Improved Analysis of Local Search for Max-Sum Diversification
Mathematics Of Operations Research. 2019. DOI : 10.1287/moor.2018.0982.On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing
Lausanne, EPFL, 2019. DOI : 10.5075/epfl-thesis-9277.Faster Algorithms for Integer Programs with Block Structure
2018. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Rupublic. p. 49:1 - . DOI : 10.4230/LIPICS.ICALP.2018.49.The Support Of Integer Optimal Solutions
Siam Journal On Optimization. 2018. DOI : 10.1137/17M1162792.Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma
2018. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, Jan 07-10, 2018. p. 808 - 816. DOI : 10.1137/1.9781611975031.52.On some problems related to 2-level polytopes
Lausanne, EPFL, 2018. DOI : 10.5075/epfl-thesis-9025.Approximation algorithms for geometric dispersion
Lausanne, EPFL, 2016. DOI : 10.5075/epfl-thesis-7291.On largest volume simplices and sub-determinants
2015. ACM-SIAM Symposium on Discrete Algorithms, San Diego, California, USA, January 4-6, 2015. p. 315 - 323. DOI : 10.1137/1.9781611973730.23.Approximation algorithms for regret minimization in vehicle routing problems
Lausanne, EPFL, 2014. DOI : 10.5075/epfl-thesis-6163.Node-weighted network design and maximum sub-determinants
Lausanne, EPFL, 2014. DOI : 10.5075/epfl-thesis-6450.On Sub-determinants and the Diameter of Polyhedra
Discrete & Computational Geometry. 2014. DOI : 10.1007/s00454-014-9601-x.Bin Packing via Discrepancy of Permutations
Acm Transactions On Algorithms. 2013. DOI : 10.1145/2483699.2483704.Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
Top. 2013. DOI : 10.1007/s11750-013-0292-x.Testing additive integrality gaps
Mathematical Programming. 2013. DOI : 10.1007/s10107-012-0518-y.On sub-determinants and the diameter of polyhedra
2012. 28th Symposium on Computational Geometry (SoCG 2012), Chapel Hill, North Carolina, USA, June 17-20, 2012.Coloring fuzzy circular interval graphs
European Journal of Combinatorics. 2012. DOI : 10.1016/j.ejc.2011.09.016.New Results in the Theory of Linear and Integer Programming
Lausanne, EPFL, 2012. DOI : 10.5075/epfl-thesis-5613.Approximation Algorithms for Modern Multi-Processor Scheduling Problems
Lausanne, EPFL, 2012. DOI : 10.5075/epfl-thesis-5561.Real-time Avionics OptimizationMathematische Optimierung von Echtzeitsystemen im Flugzeugdesign
it - Information Technology. 2011. DOI : 10.1524/itit.2011.0653.Bin Packing via Discrepancy of Permutations
2011. Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, January 22-25, 2011.Covering Cubes and the Closest Vector Problem
2011. 27th Annual Symposium on Computational Geometry (SoCG 2011), Paris, France, June 13-15, 2011. p. 417 - 423. DOI : 10.1145/1998196.1998264.Testing additive integrality gaps
2010. 21st ACM-SIAM Symposium on Discrete Algorithms, Austin, Texas, January 17-19, 2010. p. 1227 - 1234. DOI : 10.1137/1.9781611973075.98.EDF-schedulability of synchronous periodic task systems is coNP-hard
2010. ACM-SIAM Symposium on Discrete Algorithms (SODA10), Austin, Texas, January 17-19, 2010. p. 1029 - 1034. DOI : 10.1137/1.9781611973075.83.Diameter of Polyhedra: Limits of Abstraction
Mathematics of Operations Research. 2010. DOI : 10.1287/moor.1100.0470.Connected facility location via random facility sampling and core detouring
Journal Of Computer And System Sciences. 2010. DOI : 10.1016/j.jcss.2010.02.001.Hypergraphic LP Relaxations for Steiner Trees
2010. 14th Conference on Integer Programming and Combinatorial Optimization (IPCO), Lausanne, Switzerland, June 9-11, 2010. p. 383 - 396. DOI : 10.1007/978-3-642-13036-6_29.Scheduling periodic tasks in a hard real-time environment
2010. 37th International Colloquium on Automata, Languages and Programming (ICALP2010), Bordeaux, France, July 5-10, 2010. p. 299 - 311. DOI : 10.1007/978-3-642-14165-2_26.Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods
2010. 18th Annual European Symposium on Algorithms (ESA2010), Liverpool, United Kingdom, September 6-8, 2010. p. 11 - 22. DOI : 10.1007/978-3-642-15775-2_2.Multiline Addressing by Network Flow
2009. 14th Annual European Symposium on Algorithms (ESA 2006), Zurich, SWITZERLAND, Sep 11-13, 2006. p. 583 - 596. DOI : 10.1007/s00453-008-9252-5.On the computational complexity of periodic scheduling
Lausanne, EPFL, 2009. DOI : 10.5075/epfl-thesis-4513.Diameter of Polyhedra: Limits of Abstraction
2009. 25th Annual ACM Symposium on Computational Geometry (SoCG'09), Aarhus, Denmark, June 8-10, 2009. p. 386 - 392. DOI : 10.1145/1542362.1542428.Constrained Minkowski Sums: A Geometric Framework for Solving Interval Problems in Computational Biology Efficiently
2009. 23rd Annual Symposium on Computational Geometry, Gyeongju, SOUTH KOREA, Jun 06-08, 2007. p. 22 - 36. DOI : 10.1007/s00454-009-9178-y.Network Formulations of Mixed-Integer Programs
Mathematics Of Operations Research. 2009. DOI : 10.1287/moor.1080.0354.New Hardness Results for Diophantine Approximation
2009. 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '09), UC Berkeley, USA, August 21-23, 2009. p. 98 - . DOI : 10.1007/978-3-642-03685-9.Coloring Fuzzy Circular Interval Graphs
2009. European Conference on Combinatorics, Graph Theory and Applications (EuroComb2009), Bordeaux, France, September 7-11, 2009. p. 543 - 548. DOI : 10.1016/j.endm.2009.07.090.Parametric integer programming in fixed dimension
Mathematics of Operations Research. 2008. DOI : 10.1287/moor.1080.0320.Approximating connected facility location problems via Random facility sampling and core detouring
2008. ACM-SIAM Symposium on Discrete Algorithms (SODA '08), San Francisco, California, 20-22.01.2008. p. 1174 - 1183.Convexly independent subsets of the Minkowski sum of planar point sets
Electronic Journal of Combinatorics. 2008.A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation
2008. Automata, Languages and Programming, 35th International Colloquium (ICALP 2008), Reykjavik, Iceland, July 7-11, 2008. p. 246 - 257. DOI : 10.1007/978-3-540-70575-8_21.Static-priority Real-time Scheduling: Response Time Computation is NP-hard
2008. IEEE Real-Time Systems Symposium (RTSS), Barcelona, Nov. 30-3 Dec., 2008. p. 397 - 406. DOI : 10.1109/RTSS.2008.25.The stable set polytope of quasi-line graphs
Combinatorica. 2008. DOI : 10.1007/s00493-008-2244-x.Parameterised integer programming, integer cones, and related problems
University of Paderborn, Germany, 2007.Algorithms for longer OLED lifetime
2007. p. 338 - 351. DOI : 10.1007/978-3-540-72845-0_26.0/1 vertex and facet enumeration with BDDs
2007. p. 158 - 165.Flow faster: efficient decision algorithms for probabilistic simulations
2007. Tools and Algorithms for the Construction and Analysis of Systems. 13th International Conference, TACAS 2007. Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007, Braga, Portugal, March 24 - April 1, 2007. p. 155 - 169. DOI : 10.1007/978-3-540-71209-1_14.A geometric framework for solving subsequence problems in computational biology efficiently
2007. Symposium on Computational Geometry 2007, Gyeongju, South Korea. p. 310 - 318. DOI : 10.1145/1247069.1247125.New approaches for virtual private network design
SIAM Journal on Computing. 2007. DOI : 10.1137/060654827.Network formulations of mixed-integer programs
2006Caratheodory bounds for integer cones
Operations Research Letters. 2006. DOI : 10.1016/j.orl.2005.09.008.Algorithms for Virtual Private Networks
2006Algorithmen für Virtuelle Private Netzwerke
2006Multiline addressing by network flow
2006. 14th Annual European Symposium on Algorithms (ESA 2006), Zurich, Switzerland, December 11-13, 2006. p. 744 - 766. DOI : 10.1007/11841036_66.Mapping task-graphs on distributed ECU networks: Efficient algorithms for feasibility and optimality
2006. p. 87 - 90. DOI : 10.1109/RTCSA.2006.42.Provisioning a virtual private network under the presence of non-communicating groups
2006. p. 105 - 114. DOI : 10.1007/11758471_13.On the complexity of integer programming in fixed dimension
2005. 10th International Conference on Operational Research-KOI 2004, Trogir, Croatia.BDDs in a branch and cut framework
2005. p. 452 - 463. DOI : 10.1007/11427186_39.Packing a trunk - Now with a twist!
2005. p. 197 - 206. DOI : 10.1145/1060244.1060266.An improved approximation algorithm for virtual private network design
2005. p. 928 - 932.A linear algorithm for integer programming in the plane
Mathematical Programming. 2005. DOI : 10.1007/s10107-004-0520-0.Energy-aware stage illumination
2005. p. 336 - 345. DOI : 10.1145/1064092.1064144.Circular Ones Matrices and the Stable set Polytopes of Quasi-Line Graphs
Lectures notes in Computer Science. 2005. DOI : 10.1007/11496915_22.New approaches for virtual private network design
2005. p. 1151 - 1162. DOI : 10.1007/11523468_93.Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs
2004Point containment in the integer hull of a polyhedron
2004. p. 929 - 933 (electronic).On the complexity of fixed parameter clique and dominating set
Theoretical Computer Science. 2004. DOI : 10.1016/j.tcs.2004.05.009.Fast integer programming in fixed dimension
2003. p. 196 - 207. DOI : 10.1007/978-3-540-39658-1_20.Primal separation for $0/1$ polytopes
Math. Program.. 2003. DOI : 10.1007/s10107-002-0309-y.A combinatorial algorithm for computing a maximum independent set in a $t$-perfect graph
2003. p. 517 - 522.A faster algorithm for two-variable integer programming
2003. p. 290 - 299. DOI : 10.1007/978-3-540-24587-2_31.Detecting directed 4-cycles still faster
Inform. Process. Lett.. 2003. DOI : 10.1016/S0020-0190(03)00252-7.A compact linear program for testing optimality of perfect matchings
Oper. Res. Lett.. 2003. DOI : 10.1016/S0167-6377(03)00052-X.Bounds on the Chvátal rank of polytopes in the $0/1$-cube
Combinatorica. 2003. DOI : 10.1007/s00493-003-0020-5.Short vectors of planar lattices via continued fractions
Inform. Process. Lett.. 2001. DOI : 10.1016/S0020-0190(00)00186-1.Fast reduction of ternary quadratic forms
2001. International Conference, CaLC 2001, Providence, RI, USA, March 29–30, 2001. p. 32 - 44. DOI : 10.1007/3-540-44670-2_4.Cutting planes and the elementary closure in fixed dimension
Math. Oper. Res.. 2001. DOI : 10.1287/moor.26.2.304.10555.Fast 2-variable integer programming
2001. 8th International IPCO Conference, Utrecht, The Netherlands, June 13–15, 2001. p. 78 - 89. DOI : 10.1007/3-540-45535-3_7.Combining logic and optimization in cutting plane theory
2000. Third International Workshop, FroCoS 2000, Nancy, France, March 22-24, 2000. p. 1 - 17. DOI : 10.1007/10720084_1.Gomory-chvatal cutting planes and the elementary closure of polyhedra
Universität des Saarlandes, 2000. DOI : 10.22028/D291-25909.On factor refinement in number fields
Mathematics of computation. 1999. DOI : 10.1090/S0025-5718-99-01023-6.Bounds on the Chvátal rank of polytopes in the $0/1$-cube
1999. 7th International IPCO Conference, Graz, Austria, June 9–11, 1999. p. 137 - 150. DOI : 10.1007/3-540-48777-8_11.On the membership problem for the elementary closure of a polyhedron
Combinatorica. 1999. DOI : 10.1007/s004930050057.On the Chvátal rank of polytopes in the $0/1$ cube
Discrete Appl. Math.. 1999. DOI : 10.1016/S0166-218X(99)00156-0.On factor refinement in quadratic number fields
Universität des Saarlandes, 1997.Parametric integer programming in fixed dimension
Mathematics of Operations Research. 2008. DOI : 10.1287/moor.1080.0320.The stable set polytope of quasi-line graphs
Combinatorica. 2008. DOI : 10.1007/s00493-008-2244-x.A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation
2008. Automata, Languages and Programming, 35th International Colloquium (ICALP 2008), Reykjavik, Iceland, July 7-11, 2008. p. 246-257. DOI : 10.1007/978-3-540-70575-8_21.New approaches for virtual private network design
SIAM Journal on Computing. 2007. DOI : 10.1137/060654827.Algorithms for longer OLED lifetime
2007. p. 338-351. DOI : 10.1007/978-3-540-72845-0_26.A linear algorithm for integer programming in the plane
Mathematical Programming. 2005. DOI : 10.1007/s10107-004-0520-0.Enseignement et PhD
Doctorant·es actuel·les
Ruben Manuel Skorupinski, Neta Singer, Lukas Vogl, Jiaye Wei
A dirigé les thèses EPFL de
Thomas Rothvoss, Nicolai Hähnle, Martin Niemeier, Adrian Aloysius Bock, Carsten Moldenhauer, Alfonso Bolívar Cevallos Manzano, Manuel Francesco Aprile, Igor Malinovic, Christoph Hunkenschröder, Moritz Andreas Venzin, Jana Tabea Cslovjecsek
A co-dirigé les thèses EPFL de
Cours
Algèbre linéaire avancée II - diagonalisation
MATH-115(a)
L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et de démontrer rigoureusement les résultats principaux de ce sujet.
Discrete optimization
MATH-261
Ce cours est une introduction à l'optimisation linéaire et discrète. Attention: ce cours s'adresse aux mathématiciens! Bien qu'une grande partie du cours soit de nature algorithmique, vous devrez toujours être en mesure de prouver des théorèmes.