- On the Robustness of Potential-Based Flow Networks (Max Klimm, Marc E. Pfetsch, Rico Raber and Martin Skutella)
Math. Program., 197(1):337–374, 2023.
@article{KlimmPfetschRaber+2023,
author = {Klimm, Max and Pfetsch, Marc E. and Raber, Rico and Skutella, Martin},
title = {On the Robustness of Potential-Based Flow Networks},
journal = {Math. Program.},
year = {2023},
volume = {197},
number = {1},
pages = {337--374},
doi = {10.1007/s10107-021-01760-w},
}
- A Note on the Quickest Minimum Cost Transshipment Problem (Martin Skutella)
Oper. Res. Lett., 51(3):255–258, 2023.
@article{Skutella2023,
author = {Skutella, Martin},
journal = {Oper. Res. Lett.},
title = {A Note on the Quickest Minimum Cost Transshipment Problem},
year = {2023},
volume = {51},
number = {3},
pages = {255--258},
doi = {10.1016/j.orl.2023.03.005},
}
- Total Completion Time Scheduling Under Scenarios (Thomas Bosman, Martijn van Ee, Ekin Ergen, Csanád Imreh, Alberto Marchetti-Spaccamela, Martin Skutella and Leen Stougie)
WAOA 2023 – Proc. 21st Workshop on Approximation and Online Algorithms, pp. 104–118.
@inproceedings{BosmanEtAl2023,
title = {Total Completion Time Scheduling Under Scenarios},
author = {Bosman, Thomas and van Ee, Martijn and Ergen, Ekin and Imreh, Csan{\'a}d and Marchetti-Spaccamela, Alberto and Skutella, Martin and Stougie, Leen},
booktitle = {WAOA 2023 – Proc. 21st Workshop on Approximation and Online Algorithms},
pages = {104--118},
year = {2023},
}
- Single source unsplittable flows with arc-wise lower and upper bounds (Sarah Morell and Martin Skutella)
Math. Program., 192(1):477–496, 2022.
Extended abstract appeared in Proc. of IPCO 2020
@article{MorellSkutella2021,
author = {Morell, Sarah and Skutella, Martin},
journal = {Math. Program.},
title = {Single source unsplittable flows with arc-wise lower and upper bounds},
pages = {477--496},
year = {2022},
volume = {192},
number = {1},
doi = {10.1007/s10107-021-01704-4},
}
- Packing Under Convex Quadratic Constraints (Max Klimm, Marc E. Pfetsch, Rico Raber and Martin Skutella)
Math. Program., 192(1):361–386, 2022.
Extended abstract appeared in Proc. of IPCO 2020
@article{KlimmPfetschRaber+2021,
author = {Max Klimm and Marc E. Pfetsch and Rico Raber and Martin Skutella},
journal = {Math. Program.},
volume = {192},
number = {1},
title = {Packing Under Convex Quadratic Constraints},
year = {2022},
pages = {361--386},
doi = {10.1007/s10107-021-01675-6},
}
- Competitive Algorithms for Symmetric Rendezvous on the Line (Max Klimm, Guillaume Sagnol, Martin Skutella and Khai Van Tran)
SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms, pp. 329–347.
@inproceedings{KlimmSagnolSkutella+2022,
author = {Klimm, Max and Sagnol, Guillaume and Skutella, Martin and Van Tran, Khai},
booktitle = {SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms},
title = {Competitive Algorithms for Symmetric Rendezvous on the Line},
doi = {10.1137/1.9781611977073.16},
pages = {329--347},
year = {2022},
url = {https://epubs.siam.org/doi/reader/10.1137/1.9781611977073.16},
}
- A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method (Miriam Schlöter, Martin Skutella and Khai Van Tran)
SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms, pp. 90–102.
@inproceedings{SchloeterSkutTran2022,
author = {Schl\"oter, Miriam and Skutella, Martin and Tran, Khai Van},
booktitle = {SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms},
pages = {90--102},
doi = {10.1137/1.9781611977073.5},
title = {A Faster Algorithm for Quickest Transshipments via an Extended Discrete {N}ewton Method},
year = {2022},
}
- A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs (Joseph Cheriyan, R. Ravi and Martin Skutella)
Oper. Res. Lett., 49(6):842–843, 2021.
@article{CheriyanRaviSkutella2021,
author = {Cheriyan, Joseph and Ravi, R. and Skutella, Martin},
journal = {Oper. Res. Lett.},
pages = {842--843},
title = {A simple proof of the {M}oore-{H}odgson Algorithm for minimizing the number of late jobs},
volume = {49},
number = {6},
year = {2021},
doi = {10.1016/j.orl.2021.09.005},
}
- Flows Over Time as Continuous Limits of Packet-Based Network Simulations (Theresa Ziemke, Leon Sering, Laura Vargas Koch, Max Zimmer, Kai Nagel and Martin Skutella)
Transportation Research Procedia, 52:123–130, 2021.
@article{ZiemkeSeringVargas+2021,
author = {Ziemke, Theresa and Sering, Leon and V{argas Koch}, Laura and Zimmer, Max and Nagel, Kai and Skutella, Martin},
journal = {Transportation Research Procedia},
doi = {10.1016/j.trpro.2021.01.014},
pages = {123--130},
title = {Flows Over Time as Continuous Limits of Packet-Based Network Simulations},
volume = {52},
year = {2021},
}
- Towards Lower Bounds on the Depth of ReLU Neural Networks (Chistoph Hertrich, Amitabh Basu, Marco Di Summa and Martin Skutella)
NeurIPS 2021 – Proc. 35th Conference on Neural Information Processing Systems, pp. 3336–3348.
@inproceedings{HertrichBasuDiSumma+2021,
author = {Hertrich, Chistoph and Basu, Amitabh and Di Summa, Marco and Skutella, Martin},
booktitle = {NeurIPS 2021 – Proc. 35th Conference on Neural Information Processing Systems},
title = {Towards Lower Bounds on the Depth of ReLU Neural Networks},
year = {2021},
pages = {3336--3348},
url = {https://proceedings.neurips.cc/paper/2021/file/1b9812b99fe2672af746cefda86be5f9-Paper.pdf},
}
- Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size (Christoph Hertrich and Martin Skutella)
AAAI 2021 – Proc. 35th AAAI Conference on Artificial Intelligence, pp. 7685–7693.
Full paper to appear in INFORMS J. Comput.
@inproceedings{HertrichSkutella2021,
author = {Hertrich, Christoph and Skutella, Martin},
booktitle = {AAAI 2021 – Proc. 35th AAAI Conference on Artificial Intelligence},
pages = {7685--7693},
title = {Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size},
year = {2021},
}
- The Simplex Algorithm is NP-Mighty (Yann Disser and Martin Skutella)
ACM Trans. Algorithms, 15(1):5:1–5:19, 2019.
Extended abstract appeared in Proc. of SODA 2015
@article{DisserSkutella2019,
author = {Disser, Yann and Skutella, Martin},
title = {The Simplex Algorithm is NP-Mighty},
journal = {ACM Trans. Algorithms},
volume = {15},
number = {1},
pages = {5:1--5:19},
year = {2019},
doi = {10.1145/3280847},
}
- Paths to stable allocations (Ágnes Cseh and Martin Skutella)
Int. J. Game Theory, 48(3):835–862, 2019.
@article{CsehSkutella2019,
author = {Cseh, {\'{A}}gnes and Skutella, Martin},
title = {Paths to stable allocations},
journal = {Int. J. Game Theory},
volume = {48},
number = {3},
pages = {835--862},
year = {2019},
doi = {10.1007/s00182-019-00664-6},
}
- Maximizing the storage capacity of gas networks: a global MINLP approach (Robert Burlacu, Herbert Egger, Martin Groß, Alexander Martin, Marc E. Pfetsch, Lars Schewe, Mathias Sirvent and Martin Skutella)
Optim. Eng., 20:543–573, 2019.
@article{BurlascuEggerGrossEtAl-2019,
author = {Burlacu, Robert and Egger, Herbert and Gro{\ss}, Martin and Martin, Alexander and Pfetsch, Marc~E. and Schewe, Lars and Sirvent, Mathias and Skutella, Martin},
doi = {10.1007/s11081-018-9414-5},
journal = {Optim. Eng.},
pages = {543--573},
title = {Maximizing the storage capacity of gas networks: a global {MINLP} approach},
volume = {20},
year = {2019},
}
- Algorithmic results for potential-based flows: Easy and hard cases (Martin Groß, Marc E. Pfetsch, Lars Schewe, Martin Schmidt and Martin Skutella)
Networks, 73(3):306–324, 2019.
@article{GrossPfetschSchewe+2019,
author = {Gro{\ss}, Martin and Pfetsch, Marc E. and Schewe, Lars and Schmidt, Martin and Skutella, Martin},
title = {Algorithmic results for potential-based flows: Easy and hard cases},
journal = {Networks},
volume = {73},
number = {3},
pages = {306--324},
year = {2019},
doi = {10.1002/net.21865},
}
- Robust Randomized Matchings (Jannik Matuschke, Martin Skutella and José A. Soto)
Math. Oper. Res., 43(2):675–692, 2018.
Extended abstract appeared in Proc. of SODA 2015
@article{MatuschkeSkutellaSoto2018,
author = {Matuschke, Jannik and Skutella, Martin and Soto, José A.},
title = {Robust Randomized Matchings},
journal = {Math. Oper. Res.},
volume = {43},
number = {2},
pages = {675--692},
year = {2018},
doi = {10.1287/moor.2017.0878},
}
- On the complexity of instationary gas flows (Martin Groß, Marc E. Pfetsch and Martin Skutella)
Oper. Res. Lett., 46(3):286–290, 2018.
@article{GrossPfetschSkutella2018,
author = {Gro{\ss}, Martin and Pfetsch, Marc E. and Skutella, Martin},
title = {On the complexity of instationary gas flows},
journal = {Oper. Res. Lett.},
volume = {46},
number = {3},
pages = {286--290},
year = {2018},
doi = {10.1016/j.orl.2018.01.007},
}
- Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling (Sven Jäger and Martin Skutella)
STACS 2018 – Proc. 35th International Symposium on Theoretical Aspects of Computer Science, pp. 43:1–43:14.
@inproceedings{JagerSkutella2018,
author = {J{\"{a}}ger, Sven and Skutella, Martin},
title = {Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling},
booktitle = {STACS 2018 – Proc. 35th International Symposium on Theoretical Aspects of Computer Science},
pages = {43:1--43:14},
year = {2018},
doi = {10.4230/LIPIcs.STACS.2018.43},
}
- Multi-Source Multi-Sink Nash Flows over Time (Leon Sering and Martin Skutella)
ATMOS 2018 – Proc. 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, pp. 12:1–12:20.
@inproceedings{SeringSkutella2018,
author = {Sering, Leon and Skutella, Martin},
title = {Multi-Source Multi-Sink Nash Flows over Time},
booktitle = {ATMOS 2018 – Proc. 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {12:1--12:20},
year = {2018},
doi = {10.4230/OASIcs.ATMOS.2018.12},
}
- A Fully Polynomial Time Approximation Scheme for Packing While Traveling (Frank Neumann, Frank Polyakovskiy, Martin Skutella, Leen Stougie and Junhua Wu)
ALGOCLOUD 2018 – Proc. 4th International Symposium on Algorithmic Aspects of Cloud Computing, pp. 59–72.
@inproceedings{NeumannPolyakovskiySkutella2018,
author = {Neumann, Frank and Polyakovskiy, Frank and Skutella, Martin and Stougie, Leen and Wu, Junhua},
title = {A Fully Polynomial Time Approximation Scheme for Packing While Traveling},
booktitle = {ALGOCLOUD 2018 – Proc. 4th International Symposium on Algorithmic Aspects of Cloud Computing},
pages = {59--72},
year = {2018},
doi = {10.1007/978-3-030-19759-9\_5},
}
- Randomization Helps Computing a Minimum Spanning Tree under Uncertainty (Nicole Megow, Julie Meißner and Martin Skutella)
SIAM J. Comput., 46(4):1217–1240, 2017.
Extended abstract appeared in Proc. of ESA 2015
@article{MegowMeissnerSkutella2017,
author = {Megow, Nicole and Mei{\ss}ner, Julie and Skutella, Martin},
title = {Randomization Helps Computing a Minimum Spanning Tree under Uncertainty},
journal = {SIAM J. Comput.},
volume = {46},
number = {4},
pages = {1217--1240},
year = {2017},
doi = {10.1137/16M1088375},
}
- Protection of flows under targeted attacks (Jannik Matuschke, S. Thomas McCormick, Gianpaolo Oriolo, Britta Peis and Martin Skutella)
Oper. Res. Lett., 45(1):53–59, 2017.
@article{MatuschkeMcCormickOriolo+2017,
author = {Matuschke, Jannik and McCormick, S. Thomas and Oriolo, Gianpaolo and Peis, Britta and Skutella, Martin},
title = {Protection of flows under targeted attacks},
journal = {Oper. Res. Lett.},
volume = {45},
number = {1},
pages = {53--59},
year = {2017},
doi = {10.1016/j.orl.2016.11.005},
}
- Fast and Memory-Efficient Algorithms for Evacuation Problems (Miriam Schlöter and Martin Skutella)
SODA 2017 – Proc. 28th ACM-SIAM Symposium on Discrete Algorithms, pp. 821–840.
@inproceedings{SchloeterSkutella2017,
author = {Schl{\"{o}}ter, Miriam and Skutella, Martin},
title = {Fast and Memory-Efficient Algorithms for Evacuation Problems},
booktitle = {SODA 2017 – Proc. 28th ACM-SIAM Symposium on Discrete Algorithms},
pages = {821--840},
year = {2017},
doi = {10.1137/1.9781611974782.52},
}
- Unrelated Machine Scheduling with Stochastic Processing Times (Martin Skutella, Maxim Sviridenko and Marc Uetz)
Math. Oper. Res., 41(3):851–864, 2016.
Extended abstract appeared in Proc. of STACS 2014
@article{SkutellaSviridenkoUetz2016,
author = {Skutella, Martin and Sviridenko, Maxim and Uetz, Marc},
journal = {Math. Oper. Res.},
pages = {851--864},
title = {Unrelated Machine Scheduling with Stochastic Processing Times},
volume = {41},
number = {3},
doi = {10.1287/moor.2015.0757},
year = {2016},
}
- Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures (Martin Skutella and José Verschae)
Math. Oper. Res., 41(3):991–1021, 2016.
@article{SkutellaVerschae2016,
author = {Skutella, Martin and Verschae, José},
title = {Robust Polynomial-Time Approximation Schemes for Parallel Machine
Scheduling with Job Arrivals and Departures},
journal = {Math. Oper. Res.},
volume = {41},
number = {3},
pages = {991--1021},
year = {2016},
doi = {10.1287/moor.2015.0765},
}
- The Power of Recourse for Online MST and TSP (Nicole Megow, Martin Skutella, José Verschae and Andreas Wiese)
SIAM J. Comput., 45(3):859–880, 2016.
Extended abstract appeared in Proc. of ICALP 2012
@article{MegowSkutellaVerschae+2016,
author = {Megow, Nicole and Skutella, Martin and Verschae, José and Wiese, Andreas},
title = {The Power of Recourse for Online {MST} and {TSP}},
journal = {SIAM J. Comput.},
volume = {45},
number = {3},
pages = {859--880},
year = {2016},
doi = {10.1137/130917703},
}
- A Note on the Ring Loading Problem (Martin Skutella)
SIAM J. Discret. Math., 30(1):327–342, 2016.
Extended abstract appeared in Proc. of SODA 2015
@article{Skutella2016a,
author = {Skutella, Martin},
title = {A Note on the Ring Loading Problem},
journal = {SIAM J. Discret. Math.},
volume = {30},
number = {1},
pages = {327--342},
year = {2016},
doi = {10.1137/14099588X},
}
- A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective (Martin Skutella)
Oper. Res. Lett., 44(5):676–679, 2016.
@article{Skutella2016,
author = {Skutella, Martin},
title = {A 2.542-approximation for precedence constrained single machine scheduling
with release dates and total weighted completion time objective},
journal = {Oper. Res. Lett.},
volume = {44},
number = {5},
pages = {676--679},
year = {2016},
doi = {10.1016/j.orl.2016.07.016},
}
- PolySCIP (Ralf Borndörfer, Sebastian Schenker, Martin Skutella and Timo Strunk)
ICMS 2016 – Proc. 5th International Congress on Mathematical Software, pp. 259–264.
@inproceedings{BorndoerferSchenkerSkutella+2016,
author = {Borndörfer, Ralf and Schenker, Sebastian and Skutella, Martin and Strunk, Timo},
title = {PolySCIP},
booktitle = {ICMS 2016 – Proc. 5th International Congress on Mathematical Software},
pages = {259--264},
year = {2016},
doi = {10.1007/978-3-319-42432-3\_32},
}
- A tight bound on the speed-up through storage for quickest multi-commodity flows (Martin Groß and Martin Skutella)
Oper. Res. Lett., 43(1):93–95, 2015.
@article{GrossSkutella2015,
author = {Gro{\ss}, Martin and Skutella, Martin},
title = {A tight bound on the speed-up through storage for quickest multi-commodity
flows},
journal = {Oper. Res. Lett.},
volume = {43},
number = {1},
pages = {93--95},
year = {2015},
doi = {10.1016/j.orl.2014.12.008},
}
- Graph orientation and flows over time (Ashwin Arulselvan, Martin Groß and Martin Skutella)
Networks, 66(3):196–209, 2015.
Extended abstract appeared in Proc. of ISAAC 2014
@article{ArulselvanGrossSkutella2015,
author = {Arulselvan, Ashwin and Gro{\ss}, Martin and Skutella, Martin},
title = {Graph orientation and flows over time},
journal = {Networks},
volume = {66},
number = {3},
pages = {196--209},
year = {2015},
doi = {10.1002/net.21623},
}
- An incremental algorithm for the uncapacitated facility location problem (Ashwin Arulselvan, Olaf Maurer and Martin Skutella)
Networks, 65(4):306–311, 2015.
@article{ArulselvanMaurerSkutella2015,
author = {Arulselvan, Ashwin and Maurer, Olaf and Skutella, Martin},
title = {An incremental algorithm for the uncapacitated facility location problem},
journal = {Networks},
volume = {65},
number = {4},
pages = {306--311},
year = {2015},
doi = {10.1002/net.21595},
}
- Robust randomized matchings (Jannik Matuschke, Martin Skutella and José A. Soto)
SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pp. 1904–1915.
Full paper appeared in SIAM J. Comput. 2018
@inproceedings{MatuschkeSkutellaSoto2015,
author = {Matuschke, Jannik and Skutella, Martin and Soto, José A.},
title = {Robust randomized matchings},
booktitle = {SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms},
pages = {1904--1915},
year = {2015},
doi = {10.1137/1.9781611973730.127},
}
- The Simplex Algorithm is NP-Mighty (Yann Disser and Martin Skutella)
SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pp. 858–872.
Full paper appeared in ACM Trans. Algorithms 2019
@inproceedings{DisserSkutella2015,
author = {Disser, Yann and Skutella, Martin},
title = {The Simplex Algorithm is NP-Mighty},
booktitle = {SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms},
pages = {858--872},
year = {2015},
doi = {10.1137/1.9781611973730.59},
}
- A note on the ring loading problem (Martin Skutella)
SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pp. 37–46.
Full paper appeared in SIAM J. Discret. Math. 2016
@inproceedings{Skutella2015,
author = {Skutella, Martin},
title = {A note on the ring loading problem},
booktitle = {SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms},
pages = {37--46},
year = {2015},
doi = {10.1137/1.9781611973730.4},
}
- Randomization Helps Computing a Minimum Spanning Tree under Uncertainty (Nicole Megow, Julie Meißner and Martin Skutella)
ESA 2015 – Proc. 23rd European Symposium on Algorithms, pp. 878–890.
Full paper appeared in SIAM J. Comput. 2017
@inproceedings{MegowMeissnerSkutella2015,
author = {Megow, Nicole and Mei{\ss}ner, Julie and Skutella, Martin},
title = {Randomization Helps Computing a Minimum Spanning Tree under Uncertainty},
booktitle = {ESA 2015 – Proc. 23rd European Symposium on Algorithms},
pages = {878--890},
year = {2015},
doi = {10.1007/978-3-662-48350-3\_73},
}
- Node-Balancing by Edge-Increments (Friedrich Eisenbrand, Shay Moran, Rom Pinchasi and Martin Skutella)
ESA 2015 – Proc. 23rd European Symposium on Algorithms, pp. 450–458.
@inproceedings{EisenbrandMoranPinchasi+2015,
author = {Eisenbrand, Friedrich and Moran, Shay and Pinchasi, Rom and Skutella, Martin},
title = {Node-Balancing by Edge-Increments},
booktitle = {ESA 2015 – Proc. 23rd European Symposium on Algorithms},
pages = {450--458},
year = {2015},
doi = {10.1007/978-3-662-48350-3\_38},
}
- Convex Quadratic Programming in Scheduling (Martin Skutella)
Chapter in Gems of Combinatorial Optimization and Graph Algorithms, 2015.
@incollection{Skutella2015a,
author = {Skutella, Martin},
title = {Convex Quadratic Programming in Scheduling},
booktitle = {Gems of Combinatorial Optimization and Graph Algorithms},
pages = {125--132},
year = {2015},
doi = {10.1007/978-3-319-24971-1\_12},
}
- Earliest arrival flows in networks with multiple sinks (Melanie Schmidt and Martin Skutella)
Discret. Appl. Math., 164:320–327, 2014.
@article{SchmidtSkutella2014,
author = {Schmidt, Melanie and Skutella, Martin},
title = {Earliest arrival flows in networks with multiple sinks},
journal = {Discret. Appl. Math.},
volume = {164},
pages = {320--327},
year = {2014},
doi = {10.1016/j.dam.2011.09.023},
}
- Stochastic Scheduling on Unrelated Machines (Martin Skutella, Maxim Sviridenko and Marc Uetz)
STACS 2014 – Proc. 31st International Symposium on Theoretical Aspects of Computer Science, pp. 639–650.
Full paper appeared in Math. Oper. Res. 2016
@inproceedings{SkutellaSviridenkoUetz2014,
author = {Skutella, Martin and Sviridenko, Maxim and Uetz, Marc},
title = {Stochastic Scheduling on Unrelated Machines},
booktitle = {STACS 2014 – Proc. 31st International Symposium on Theoretical Aspects of Computer Science},
pages = {639--650},
year = {2014},
doi = {10.4230/LIPIcs.STACS.2014.639},
}
- Paths to Stable Allocations (Ágnes Cseh and Martin Skutella)
SAGT 2014 – Proc. 7th International Symposium on Algorithmic Game Theory, pp. 61–73.
Full paper appeared in Int. J. Game Theory 2019
@inproceedings{CsehSkutella2014,
author = {Cseh, {\'{A}}gnes and Skutella, Martin},
title = {Paths to Stable Allocations},
booktitle = {SAGT 2014 – Proc. 7th International Symposium on Algorithmic Game Theory},
pages = {61--73},
year = {2014},
doi = {10.1007/978-3-662-44803-8\_6},
}
- Graph Orientation and Flows over Time (Ashwin Arulselvan, Martin Groß and Martin Skutella)
ISAAC 2014 – Proc. 25th International Symposium on Algorithms and Computation, pp. 741–752.
Full paper appeared in Networks 2015
@inproceedings{ArulselvanGrossSkutella2014,
author = {Arulselvan, Ashwin and Gro{\ss}, Martin and Skutella, Martin},
title = {Graph Orientation and Flows over Time},
booktitle = {ISAAC 2014 – Proc. 25th International Symposium on Algorithms and Computation},
pages = {741--752},
year = {2014},
doi = {10.1007/978-3-319-13075-0\_58},
}
- Stable Flows over Time (Ágnes Cseh, Jannik Matuschke and Martin Skutella)
Algorithms, 6(3):532–545, 2013.
@article{CsehMatuschkeSkutella2013,
author = {Cseh, {\'{A}}gnes and Matuschke, Jannik and Skutella, Martin},
title = {Stable Flows over Time},
journal = {Algorithms},
volume = {6},
number = {3},
pages = {532--545},
year = {2013},
doi = {10.3390/a6030532},
}
- Algorithms and Linear Programming Relaxations for Scheduling Unrelated Parallel Machines (Martin Skutella)
SEA 2013 – Proc. 12th International Symposium on Experimental Algorithms, pp. 1–3.
@inproceedings{Skutella2013,
author = {Skutella, Martin},
title = {Algorithms and Linear Programming Relaxations for Scheduling Unrelated
Parallel Machines},
booktitle = {SEA 2013 – Proc. 12th International Symposium on Experimental Algorithms},
pages = {1--3},
year = {2013},
doi = {10.1007/978-3-642-38527-8\_1},
}
- Task assignment, sequencing and path-planning in robotic welding cells (Chantal Landry, René Henrion, Dietmar Hömberg, Martin Skutella and Wolfgang Welz)
MMAR 2013 – Proc. 18th International Conference on Methods and Models in Automation and Robotics, pp. 252–257.
@inproceedings{LandryHenrionHoemberg+2013,
author = {Landry, Chantal and Henrion, Ren{\'{e}} and H{\"{o}}mberg, Dietmar and Skutella, Martin and Welz, Wolfgang},
title = {Task assignment, sequencing and path-planning in robotic welding cells},
booktitle = {MMAR 2013 – Proc. 18th International Conference on Methods and Models in Automation and Robotics},
pages = {252--257},
year = {2013},
doi = {10.1109/MMAR.2013.6669915},
}
- Universal Sequencing on an Unreliable Machine (Leah Epstein, Asaf Levin, Alberto Marchetti-Spaccamela, Nicole Megow, Julián Mestre, Martin Skutella and Leen Stougie)
SIAM J. Comput., 41(3):565–586, 2012.
Extended abstract appeared in Proc. of IPCO 2010
@article{EpsteinLevinMarchetti-Spaccamela+2012,
author = {Epstein, Leah and Levin, Asaf and Marchetti{-}Spaccamela, Alberto and Megow, Nicole and Mestre, Juli{\'{a}}n and Skutella, Martin and Stougie, Leen},
title = {Universal Sequencing on an Unreliable Machine},
journal = {SIAM J. Comput.},
volume = {41},
number = {3},
pages = {565--586},
year = {2012},
doi = {10.1137/110844210},
}
- The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders (José R. Correa, Martin Skutella and José Verschae)
Math. Oper. Res., 37(2):379–398, 2012.
Extended abstract appeared in Proc. of APPROX 2009
@article{CorreaSkutellaVerschae2012,
author = {Correa, José R. and Skutella, Martin and Verschae, José},
title = {The Power of Preemption on Unrelated Machines and Applications to
Scheduling Orders},
journal = {Math. Oper. Res.},
volume = {37},
number = {2},
pages = {379--398},
year = {2012},
doi = {10.1287/moor.1110.0520},
}
- The Power of Recourse for Online MST and TSP (Nicole Megow, Martin Skutella, José Verschae and Andreas Wiese)
ICALP 2012 – Proc. 39th International Colloquium on Automata, Languages and Programming, pp. 689–700.
Full paper appeared in SIAM J. Comput. 2016
@inproceedings{MegowSkutellaVerschae+2012,
author = {Megow, Nicole and Skutella, Martin and Verschae, José and Wiese, Andreas},
title = {The Power of Recourse for Online {MST} and {TSP}},
booktitle = {ICALP 2012 – Proc. 39th International Colloquium on Automata, Languages and Programming},
pages = {689--700},
year = {2012},
doi = {10.1007/978-3-642-31594-7\_58},
}
- Maximum Multicommodity Flows over Time without Intermediate Storage (Martin Groß and Martin Skutella)
ESA 2012 – Proc. 20th European Symposium on Algorithms, pp. 539–550.
@inproceedings{GrossSkutella2012,
author = {Gro{\ss}, Martin and Skutella, Martin},
title = {Maximum Multicommodity Flows over Time without Intermediate Storage},
booktitle = {ESA 2012 – Proc. 20th European Symposium on Algorithms},
pages = {539--550},
year = {2012},
doi = {10.1007/978-3-642-33090-2\_47},
}
- Flows over Time with Negative Transit Times and Arc Release Dates (Sandro Bosio, Jan-Philipp W. Kappmeier, Jannik Matuschke, Britta Peis and Martin Skutella)
CTW 2012 – Proc. 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp. 30–33.
@inproceedings{BosioKappmeierMatuschke+2012,
author = {Bosio, Sandro and
Kappmeier, Jan{-}Philipp W. and
Matuschke, Jannik and
Peis, Britta and
Skutella, Martin},
title = {Flows over Time with Negative Transit Times and Arc Release Dates},
booktitle = {CTW 2012 – Proc. 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization},
pages = {30--33},
year = {2012},
}
- Computing Minimum Cuts by Randomized Search Heuristics (Frank Neumann, Joachim Reichel and Martin Skutella)
Algorithmica, 59(3):323–342, 2011.
Extended abstract appeared in Proc. of GECCO 2008
@article{NeumannReichelSkutella2011,
author = {Neumann, Frank and Reichel, Joachim and Skutella, Martin},
title = {Computing Minimum Cuts by Randomized Search Heuristics},
journal = {Algorithmica},
volume = {59},
number = {3},
pages = {323--342},
year = {2011},
doi = {10.1007/s00453-009-9370-8},
}
- Continuous and discrete flows over time - A general model based on measure theory (Ronald Koch, Ebrahim Nasrabadi and Martin Skutella)
Math. Methods Oper. Res., 73(3):301–337, 2011.
@article{KochNasrabadiSkutella2011,
author = {Koch, Ronald and Nasrabadi, Ebrahim and Skutella, Martin},
title = {Continuous and discrete flows over time - {A} general model based
on measure theory},
journal = {Math. Methods Oper. Res.},
volume = {73},
number = {3},
pages = {301--337},
year = {2011},
doi = {10.1007/s00186-011-0357-2},
}
- A note on the generalized min-sum set cover problem (Martin Skutella and David P. Williamson)
Oper. Res. Lett., 39(6):433–436, 2011.
@article{SkutellaWilliamson2011,
author = {Skutella, Martin and Williamson, David P.},
title = {A note on the generalized min-sum set cover problem},
journal = {Oper. Res. Lett.},
volume = {39},
number = {6},
pages = {433--436},
year = {2011},
doi = {10.1016/j.orl.2011.08.002},
}
- Nash Equilibria and the Price of Anarchy for Flows over Time (Ronald Koch and Martin Skutella)
Theory Comput. Syst., 49(1):71–97, 2011.
Extended abstract appeared in Proc. of SAGT 2009
@article{KochSkutella2011,
author = {Koch, Ronald and Skutella, Martin},
title = {Nash Equilibria and the Price of Anarchy for Flows over Time},
journal = {Theory Comput. Syst.},
volume = {49},
number = {1},
pages = {71--97},
year = {2011},
doi = {10.1007/s00224-010-9299-y},
}
- Real-time Avionics Optimization (Friedrich Eisenbrand, Martin Niemeier, Martin Skutella, José Verschae and Andreas Wiese)
it – Inf. Technol., 53(6):274–279, 2011.
@article{EisenbrandNiemeierSkutella+2011,
author = {Eisenbrand, Friedrich and Niemeier, Martin and Skutella, Martin and Verschae, Jos{\'{e}} and Wiese, Andreas},
title = {Real-time Avionics Optimization},
journal = {it -- Inf. Technol.},
volume = {53},
number = {6},
pages = {274--279},
year = {2011},
doi = {10.1524/itit.2011.0653},
}
- Generalized Maximum Flows over Time (Martin Groß and Martin Skutella)
WAOA 2011 – Proc. 9th Workshop on Approximation and Online Algorithms, pp. 247–260.
@inproceedings{GrossSkutella2011,
author = {Gro{\ss}, Martin and Skutella, Martin},
title = {Generalized Maximum Flows over Time},
booktitle = {WAOA 2011 – Proc. 9th Workshop on Approximation and Online Algorithms},
pages = {247--260},
year = {2011},
doi = {10.1007/978-3-642-29116-6\_21},
}
- Minimum Spanning Trees – Sometimes Greed Pays Off (Katharina Skutella and Martin Skutella)
Chapter in Algorithms Unplugged, 2011.
@incollection{SkutellaSkutella2011,
author = {Skutella, Katharina and Skutella, Martin},
title = {Minimum Spanning Trees -- Sometimes Greed Pays Off},
booktitle = {Algorithms Unplugged},
pages = {325--331},
year = {2011},
doi = {10.1007/978-3-642-15328-0\_33},
}
- On the dominant of the $s$-$t$-cut polytope: Vertices, facets, and adjacency (Martin Skutella and Alexia Weber)
Math. Program., 124(1-2):441–454, 2010.
@article{SkutellaWeber2010,
author = {Skutella, Martin and Weber, Alexia},
title = {On the dominant of the $s$-$t$-cut polytope: Vertices, facets,
and adjacency},
journal = {Math. Program.},
volume = {124},
number = {1-2},
pages = {441--454},
year = {2010},
doi = {10.1007/s10107-010-0373-7},
}
- Length-bounded cuts and flows (Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondrej Pangrác, Heiko Schilling and Martin Skutella)
ACM Trans. Algorithms, 7(1):4:1–4:27, 2010.
Extended abstract appeared in Proc. of ICALP 2006
@article{BaierErlebachHall+2010,
author = {Baier, Georg and Erlebach, Thomas and Hall, Alexander and K{\"{o}}hler, Ekkehard and Kolman, Petr and Pangr{\'{a}}c, Ondrej and Schilling, Heiko and Skutella, Martin},
title = {Length-bounded cuts and flows},
journal = {ACM Trans. Algorithms},
volume = {7},
number = {1},
pages = {4:1--4:27},
year = {2010},
doi = {10.1145/1868237.1868241},
}
- Evolutionary Algorithms and Matroid Optimization Problems (Joachim Reichel and Martin Skutella)
Algorithmica, 57(1):187–206, 2010.
Extended abstract appeared in Proc. of GECCO 2007
@article{ReichelSkutella2010,
author = {Reichel, Joachim and Skutella, Martin},
title = {Evolutionary Algorithms and Matroid Optimization Problems},
journal = {Algorithmica},
volume = {57},
number = {1},
pages = {187--206},
year = {2010},
doi = {10.1007/s00453-008-9253-4},
}
- Earliest Arrival Flows in Networks with Multiple Sinks (Melanie Schmidt and Martin Skutella)
Electron. Notes Discret. Math., 36:607–614, 2010.
@article{SchmidtSkutella2010,
author = {Schmidt, Melanie and Skutella, Martin},
title = {Earliest Arrival Flows in Networks with Multiple Sinks},
journal = {Electron. Notes Discret. Math.},
volume = {36},
pages = {607--614},
year = {2010},
doi = {10.1016/j.endm.2010.05.077},
}
- Scheduling Periodic Tasks in a Hard Real-Time Environment (Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, José Verschae and Andreas Wiese)
ICALP 2010 – Proc. 37th International Colloquium on Automata, Languages and Programming, pp. 299–311.
@inproceedings{EisenbrandHaehnleNiemeier+2010,
author = {Eisenbrand, Friedrich and H{\"{a}}hnle, Nicolai and Niemeier, Martin and Skutella, Martin and Verschae, Jos{\'{e}} and Wiese, Andreas},
title = {Scheduling Periodic Tasks in a Hard Real-Time Environment},
booktitle = {ICALP 2010 – Proc. 37th International Colloquium on Automata, Languages and Programming},
pages = {299--311},
year = {2010},
doi = {10.1007/978-3-642-14165-2\_26},
}
- Universal Sequencing on a Single Machine (Leah Epstein, Asaf Levin, Alberto Marchetti-Spaccamela, Nicole Megow, Julián Mestre, Martin Skutella and Leen Stougie)
IPCO 2010 – Proc. 14th Conference on Integer Programming and Combinatorial Optimization, pp. 230–243.
Full paper appeared in SIAM J. Comput. 2012
@inproceedings{EpsteinLevinMarchetti-Spaccamela+2010,
author = {Epstein, Leah and Levin, Asaf and Marchetti{-}Spaccamela, Alberto and Megow, Nicole and Mestre, Juli{\'{a}}n and Skutella, Martin and Stougie, Leen},
title = {Universal Sequencing on a Single Machine},
booktitle = {IPCO 2010 – Proc. 14th Conference on Integer Programming and Combinatorial Optimization},
pages = {230--243},
year = {2010},
doi = {10.1007/978-3-642-13036-6\_18},
}
- Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods (Friedrich Eisenbrand, Karthikeyan Kesavan, Raju S. Mattikalli, Martin Niemeier, Arnold W. Nordsieck, Martin Skutella, José Verschae and Andreas Wiese)
ESA 2010 – Proc. 18th European Symposium on Algorithms, pp. 11–22.
@inproceedings{EisenbrandKesavanMattikalli+2010,
author = {Eisenbrand, Friedrich and Kesavan, Karthikeyan and Mattikalli, Raju S. and Niemeier, Martin and Nordsieck, Arnold W. and Skutella, Martin and Verschae, Jos{\'{e}} and Wiese, Andreas},
title = {Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods},
booktitle = {ESA 2010 – Proc. 18th European Symposium on Algorithms},
pages = {11--22},
year = {2010},
doi = {10.1007/978-3-642-15775-2\_2},
}
- A Robust PTAS for Machine Covering and Packing (Martin Skutella and José Verschae)
ESA 2010 – Proc. 18th European Symposium on Algorithms, pp. 36–47.
@inproceedings{SkutellaVerschae2010,
author = {Skutella, Martin and Verschae, José},
title = {A Robust {PTAS} for Machine Covering and Packing},
booktitle = {ESA 2010 – Proc. 18th European Symposium on Algorithms},
pages = {36--47},
year = {2010},
doi = {10.1007/978-3-642-15775-2\_4},
}
- Packet Routing on the Grid (Britta Peis, Martin Skutella and Andreas Wiese)
LATIN 2010 – Proc. 9th Latin American Symposium on Theoretical Informatics, pp. 120–130.
@inproceedings{PeisSkutellaWiese2010,
author = {Peis, Britta and Skutella, Martin and Wiese, Andreas},
title = {Packet Routing on the Grid},
booktitle = {LATIN 2010 – Proc. 9th Latin American Symposium on Theoretical Informatics},
pages = {120--130},
year = {2010},
doi = {10.1007/978-3-642-12200-2\_12},
}
- An FPTAS for Flows over Time with Aggregate Arc Capacities (Daniel Dressler and Martin Skutella)
WAOA 2010 – Proc. 8th Workshop on Approximation and Online Algorithms, pp. 106–117.
@inproceedings{DresslerSkutella2010,
author = {Dressler, Daniel and Skutella, Martin},
title = {An {FPTAS} for Flows over Time with Aggregate Arc Capacities},
booktitle = {WAOA 2010 – Proc. 8th Workshop on Approximation and Online Algorithms},
pages = {106--117},
year = {2010},
doi = {10.1007/978-3-642-18318-8\_10},
}
- Optimal Evacuation Solutions for Large-Scale Scenarios (Daniel Dressler, Gunnar Flötteröd, Gregor Lämmel, Kai Nagel and Martin Skutella)
OR 2010 – Proc. International Conference of the German Operations Research Society.
@inproceedings{DresslerFloetteroedLaemmel+2010,
author = {Dressler, Daniel and Fl{\"{o}}tter{\"{o}}d, Gunnar and L{\"{a}}mmel, Gregor and Nagel, Kai and Skutella, Martin},
title = {Optimal Evacuation Solutions for Large-Scale Scenarios},
booktitle = {OR 2010 – Proc. International Conference of the German Operations Research Society},
year = {2010},
doi = {10.1007/978-3-642-20009-0\_38},
}
- Route Planning for Robot Systems (Martin Skutella and Wolfgang Welz)
OR 2010 – Proc. International Conference of the German Operations Research Society, pp. 307–312.
@inproceedings{SkutellaWelz2010,
author = {Skutella, Martin and Welz, Wolfgang},
title = {Route Planning for Robot Systems},
booktitle = {OR 2010 – Proc. International Conference of the German Operations Research Society},
pages = {307--312},
year = {2010},
doi = {10.1007/978-3-642-20009-0\_49},
}
- Online Scheduling with Bounded Migration (Peter Sanders, Naveen Sivadasan and Martin Skutella)
Math. Oper. Res., 34(2):481–498, 2009.
Extended abstract appeared in Proc. of ICALP 2004
@article{SandersSivadasanSkutella2009,
author = {Sanders, Peter and Sivadasan, Naveen and Skutella, Martin},
title = {Online Scheduling with Bounded Migration},
journal = {Math. Oper. Res.},
volume = {34},
number = {2},
pages = {481--498},
year = {2009},
doi = {10.1287/moor.1090.0381},
}
- Earliest Arrival Flows with Multiple Sources (Nadine Baumann and Martin Skutella)
Math. Oper. Res., 34(2):499–512, 2009.
Extended abstract appeared in Proc. of FOCS 2006
@article{BaumannSkutella2009,
author = {Baumann, Nadine and Skutella, Martin},
title = {Earliest Arrival Flows with Multiple Sources},
journal = {Math. Oper. Res.},
volume = {34},
number = {2},
pages = {499--512},
year = {2009},
doi = {10.1287/moor.1090.0382},
}
- Latency-constrained aggregation in sensor networks (Luca Becchetti, Alberto Marchetti-Spaccamela, Andrea Vitaletti, Peter Korteweg, Martin Skutella and Leen Stougie)
ACM Trans. Algorithms, 6(1):13:1–13:20, 2009.
Extended abstract appeared in Proc. of ESA 2006
@article{BecchettiMarchetti-SpaccamelaVitaletti+2009,
author = {Becchetti, Luca and Marchetti{-}Spaccamela, Alberto and Vitaletti, Andrea and Korteweg, Peter and Skutella, Martin and Stougie, Leen},
title = {Latency-constrained aggregation in sensor networks},
journal = {ACM Trans. Algorithms},
volume = {6},
number = {1},
pages = {13:1--13:20},
year = {2009},
doi = {10.1145/1644015.1644028},
}
- Multiline Addressing by Network Flow (Friedrich Eisenbrand, Andreas Karrenbauer, Martin Skutella and Chihao Xu)
Algorithmica, 53(4):583–596, 2009.
@article{EisenbrandKarrenbauerSkutella+2009,
author = {Eisenbrand, Friedrich and Karrenbauer, Andreas and Skutella, Martin and Xu, Chihao},
title = {Multiline Addressing by Network Flow},
journal = {Algorithmica},
volume = {53},
number = {4},
pages = {583--596},
year = {2009},
doi = {10.1007/s00453-008-9252-5},
}
- Flows with unit path capacities and related packing and covering problems (Maren Martens and Martin Skutella)
J. Comb. Optim., 18(3):272–293, 2009.
Extended abstract appeared in Proc. of COCOA 2008
@article{MartensSkutella2009,
author = {Martens, Maren and Skutella, Martin},
title = {Flows with unit path capacities and related packing and covering problems},
journal = {J. Comb. Optim.},
volume = {18},
number = {3},
pages = {272--293},
year = {2009},
doi = {10.1007/s10878-009-9225-x},
}
- Single-source $k$-splittable min-cost flows (Fernanda Salazar and Martin Skutella)
Oper. Res. Lett., 37(2):71–74, 2009.
@article{SalazarSkutella2009,
author = {Salazar, Fernanda and Skutella, Martin},
title = {Single-source $k$-splittable min-cost flows},
journal = {Oper. Res. Lett.},
volume = {37},
number = {2},
pages = {71--74},
year = {2009},
doi = {10.1016/j.orl.2008.12.004},
}
- The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders (José R. Correa, Martin Skutella and José Verschae)
APPROX 2009 – Proc. 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 84–97.
Full paper appeared in Math. Oper. Res. 2012
@inproceedings{CorreaSkutellaVerschae2009,
author = {Correa, José R. and Skutella, Martin and Verschae, José},
title = {The Power of Preemption on Unrelated Machines and Applications to
Scheduling Orders},
booktitle = {APPROX 2009 – Proc. 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems},
pages = {84--97},
year = {2009},
doi = {10.1007/978-3-642-03685-9\_7},
}
- Real-Time Message Routing and Scheduling (Ronald Koch, Britta Peis, Martin Skutella and Andreas Wiese)
APPROX 2009 – Proc. 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 217–230.
@inproceedings{KochPeisSkutella+2009,
author = {Koch, Ronald and Peis, Britta and Skutella, Martin and Wiese, Andreas},
title = {Real-Time Message Routing and Scheduling},
booktitle = {APPROX 2009 – Proc. 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems},
pages = {217--230},
year = {2009},
doi = {10.1007/978-3-642-03685-9\_17},
}
- Nash Equilibria and the Price of Anarchy for Flows over Time (Ronald Koch and Martin Skutella)
SAGT 2009 – Proc. 2nd International Symposium on Algorithmic Game Theory, pp. 323–334.
Full paper appeared in Theory Comput. Syst. 2011
@inproceedings{KochSkutella2009,
author = {Koch, Ronald and Skutella, Martin},
title = {Nash Equilibria and the Price of Anarchy for Flows over Time},
booktitle = {SAGT 2009 – Proc. 2nd International Symposium on Algorithmic Game Theory},
pages = {323--334},
year = {2009},
doi = {10.1007/978-3-642-04645-2\_29},
}
- Packet Routing: Complexity and Algorithms (Britta Peis, Martin Skutella and Andreas Wiese)
WAOA 2009 – Proc. 7th Workshop on Approximation and Online Algorithms, pp. 217–228.
@inproceedings{PeisSkutellaWiese2009,
author = {Peis, Britta and Skutella, Martin and Wiese, Andreas},
title = {Packet Routing: Complexity and Algorithms},
booktitle = {WAOA 2009 – Proc. 7th Workshop on Approximation and Online Algorithms},
pages = {217--228},
year = {2009},
doi = {10.1007/978-3-642-12450-1\_20},
}
- On the size of weights in randomized search heuristics (Joachim Reichel and Martin Skutella)
FOGA 2009 – Proc. 10th ACM SIGEVO International Workshop on Foundations of Genetic Algorithms, pp. 21–28.
@inproceedings{ReichelSkutella2009,
author = {Reichel, Joachim and Skutella, Martin},
title = {On the size of weights in randomized search heuristics},
booktitle = {FOGA 2009 – Proc. 10th ACM SIGEVO International Workshop on Foundations of Genetic Algorithms},
pages = {21--28},
year = {2009},
doi = {10.1145/1527125.1527130},
}
- An Introduction to Network Flows Over Time (Martin Skutella)
Chapter in Research Trends in Combinatorial Optimization (W. Cook, L. Lovász, J. Vygen, eds.), Springer, 2009.
@incollection{Skutella2009,
author = {Skutella, Martin},
booktitle = {Research Trends in Combinatorial Optimization},
editor = {Cook, W. and Lov{\'a}sz, L. and Vygen, J.},
pages = {451--482},
publisher = {Springer},
title = {An Introduction to Network Flows Over Time},
year = {2009},
doi = {10.1007/978-3-540-76796-1_21},
}
- Traffic Networks and Flows over Time (Ekkehard Köhler, Rolf H. Möhring and Martin Skutella)
Chapter in Algorithmics of Large and Complex Networks – Design, Analysis, and Simulation, 2009.
@incollection{KoehlerMoehringSkutella2009,
author = {K{\"{o}}hler, Ekkehard and M{\"{o}}hring, Rolf H. and Skutella, Martin},
title = {Traffic Networks and Flows over Time},
booktitle = {Algorithmics of Large and Complex Networks -- Design, Analysis, and
Simulation},
pages = {166--196},
year = {2009},
doi = {10.1007/978-3-642-02094-0\_9},
}
- A short proof of the VPN Tree Routing Conjecture on ring networks (Fabrizio Grandoni, Volker Kaibel, Gianpaolo Oriolo and Martin Skutella)
Oper. Res. Lett., 36(3):361–365, 2008.
@article{GrandoniKaibelOriolo+2008,
author = {Grandoni, Fabrizio and Kaibel, Volker and Oriolo, Gianpaolo and Skutella, Martin},
title = {A short proof of the {VPN} Tree Routing Conjecture on ring networks},
journal = {Oper. Res. Lett.},
volume = {36},
number = {3},
pages = {361--365},
year = {2008},
doi = {10.1016/j.orl.2007.10.008},
}
- Maximum $k$-Splittable $s,t$-Flows (Ronald Koch, Martin Skutella and Ines Spenke)
Theory Comput. Syst., 43(1):56–66, 2008.
Extended abstract appeared in Proc. of WAOA 2005
@article{KochSkutellaSpenke2008,
author = {Koch, Ronald and Skutella, Martin and Spenke, Ines},
title = {Maximum $k$-Splittable $s,t$-Flows},
journal = {Theory Comput. Syst.},
volume = {43},
number = {1},
pages = {56--66},
year = {2008},
doi = {10.1007/s00224-007-9068-8},
}
- Flows with unit path capacities and related packing and covering problems (Maren Martens and Martin Skutella)
COCOA 2008 – Proc. 2nd International Conference on Combinatorial Optimization and Applications, pp. 180–189.
Full paper appeared in J. Comb. Optim. 2009
@inproceedings{MartensSkutella2008,
author = {Martens, Maren and Skutella, Martin},
title = {Flows with unit path capacities and related packing and covering problems},
booktitle = {COCOA 2008 – Proc. 2nd International Conference on Combinatorial Optimization and Applications},
pages = {180--189},
year = {2008},
doi = {10.1007/978-3-540-85097-7\_17},
}
- Computing minimum cuts by randomized search heuristics (Frank Neumann, Joachim Reichel and Martin Skutella)
GECCO 2008 – Proc. Genetic and Evolutionary Computation Conference, pp. 779–786.
Full paper appeared in Algorithmica 2011
@inproceedings{NeumannReichelSkutella2008,
author = {Neumann, Frank and Reichel, Joachim and Skutella, Martin},
title = {Computing minimum cuts by randomized search heuristics},
booktitle = {GECCO 2008 – Proc. Genetic and Evolutionary Computation Conference},
pages = {779--786},
year = {2008},
doi = {10.1145/1389095.1389250},
}
- Minimale aufspannende Bäume – Wenn das Naheliegende das Beste ist... (Katharina Skutella and Martin Skutella)
Chapter in Taschenbuch der Algorithmen, 2008.
@incollection{SkutellaSkutella2008,
author = {Skutella, Katharina and Skutella, Martin},
title = {Minimale aufspannende B{\"{a}}ume -- Wenn das Naheliegende das
Beste ist...},
booktitle = {Taschenbuch der Algorithmen},
pages = {353--360},
year = {2008},
doi = {10.1007/978-3-540-76394-9\_35},
}
- An Introduction to Network Flows over Time (Martin Skutella)
Chapter in Research Trends in Combinatorial Optimization, Bonn Workshop on Combinatorial Optimization, November 3-7, 2008, Bonn, Germany, 2008.
@incollection{Skutella2008,
author = {Skutella, Martin},
title = {An Introduction to Network Flows over Time},
booktitle = {Research Trends in Combinatorial Optimization, Bonn Workshop on Combinatorial
Optimization, November 3-7, 2008, Bonn, Germany},
pages = {451--482},
year = {2008},
doi = {10.1007/978-3-540-76796-1\_21},
}
- Quickest Flows Over Time (Lisa Fleischer and Martin Skutella)
SIAM J. Comput., 36(6):1600–1630, 2007.
Extended abstracts of different parts appeared in Proc. of IPCO 2002 and SODA 2003
@article{FleischerSkutella2007,
author = {Fleischer, Lisa and Skutella, Martin},
title = {Quickest Flows Over Time},
journal = {SIAM J. Comput.},
volume = {36},
number = {6},
pages = {1600--1630},
year = {2007},
doi = {10.1137/S0097539703427215},
}
- New Approaches for Virtual Private Network Design (Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo and Martin Skutella)
SIAM J. Comput., 37(3):706–721, 2007.
Extended abstract appeared in Proc. of ICALP 2005
@article{EisenbrandGrandoniOriolo+2007,
author = {Eisenbrand, Friedrich and Grandoni, Fabrizio and Oriolo, Gianpaolo and Skutella, Martin},
title = {New Approaches for Virtual Private Network Design},
journal = {SIAM J. Comput.},
volume = {37},
number = {3},
pages = {706--721},
year = {2007},
doi = {10.1137/060654827},
}
- An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times (Alexander Hall, Katharina Langkau and Martin Skutella)
Algorithmica, 47(3):299–321, 2007.
Extended abstract appeared in Proc. of APPROX 2003
@article{HallLangkauSkutella2007,
author = {Hall, Alexander and Langkau, Katharina and Skutella, Martin},
title = {An {FPTAS} for Quickest Multicommodity Flows with Inflow-Dependent
Transit Times},
journal = {Algorithmica},
volume = {47},
number = {3},
pages = {299--321},
year = {2007},
doi = {10.1007/s00453-006-0196-3},
}
- Multicommodity flows over time: Efficient algorithms and complexity (Alexander Hall, Steffen Hippler and Martin Skutella)
Theor. Comput. Sci., 379(3):387–404, 2007.
Extended abstract appeared in Proc. of ICALP 2003
@article{HallHipplerSkutella2007,
author = {Hall, Alexander and Hippler, Steffen and Skutella, Martin},
title = {Multicommodity flows over time: Efficient algorithms and complexity},
journal = {Theor. Comput. Sci.},
volume = {379},
number = {3},
pages = {387--404},
year = {2007},
doi = {10.1016/j.tcs.2007.02.046},
}
- Convex Combinations of Single Source Unsplittable Flows (Maren Martens, Fernanda Salazar and Martin Skutella)
ESA 2007 – Proc. 15th European Symposium on Algorithms, pp. 395–406.
@inproceedings{MartensSalazarSkutella2007,
author = {Martens, Maren and Salazar, Fernanda and Skutella, Martin},
title = {Convex Combinations of Single Source Unsplittable Flows},
booktitle = {ESA 2007 – Proc. 15th European Symposium on Algorithms},
pages = {395--406},
year = {2007},
doi = {10.1007/978-3-540-75520-3\_36},
}
- The Freeze-Tag Problem: How to Wake Up a Swarm of Robots (Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell and Martin Skutella)
Algorithmica, 46(2):193–221, 2006.
Extended abstract appeared in Proc. of SODA 2002
@article{ArkinBenderFekete+2006,
author = {Arkin, Esther M. and Bender, Michael A. and Fekete, S{\'{a}}ndor P. and Mitchell, Joseph S. B. and Skutella, Martin},
title = {The Freeze-Tag Problem: How to Wake Up a Swarm of Robots},
journal = {Algorithmica},
volume = {46},
number = {2},
pages = {193--221},
year = {2006},
doi = {10.1007/s00453-006-1206-1},
}
- Flows on few paths: Algorithms and lower bounds (Maren Martens and Martin Skutella)
Networks, 48(2):68–76, 2006.
Extended abstract appeared in Proc. of ESA 2004
@article{MartensSkutella2006,
author = {Martens, Maren and Skutella, Martin},
title = {Flows on few paths: Algorithms and lower bounds},
journal = {Networks},
volume = {48},
number = {2},
pages = {68--76},
year = {2006},
doi = {10.1002/net.20121},
}
- Solving Evacuation Problems Efficiently–Earliest Arrival Flows with Multiple Sources (Nadine Baumann and Martin Skutella)
FOCS 2006 – Proc. 47th Symposium on Foundations of Computer Science, pp. 399–410.
Full paper appeared in Math. Oper. Res. 2009
@inproceedings{BaumannSkutella2006,
author = {Baumann, Nadine and Skutella, Martin},
title = {Solving Evacuation Problems Efficiently--Earliest Arrival Flows with
Multiple Sources},
booktitle = {FOCS 2006 – Proc. 47th Symposium on Foundations of Computer Science},
pages = {399--410},
year = {2006},
doi = {10.1109/FOCS.2006.70},
}
- Length-Bounded Cuts and Flows (Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondrej Pangrác, Heiko Schilling and Martin Skutella)
ICALP 2006 – Proc. 33rd International Colloquium on Automata, Languages and Programming, pp. 679–690.
Full paper appeared in ACM Trans. Algorithms 2010
@inproceedings{BaierErlebachHall+2006,
author = {Baier, Georg and Erlebach, Thomas and Hall, Alexander and K{\"{o}}hler, Ekkehard and Kolman, Petr and Pangr{\'{a}}c, Ondrej and Schilling, Heiko and Skutella, Martin},
title = {Length-Bounded Cuts and Flows},
booktitle = {ICALP 2006 – Proc. 33rd International Colloquium on Automata, Languages and Programming},
pages = {679--690},
year = {2006},
doi = {10.1007/11786986\_59},
}
- Latency Constrained Aggregation in Sensor Networks (Luca Becchetti, Alberto Marchetti-Spaccamela, Andrea Vitaletti, Peter Korteweg, Martin Skutella and Leen Stougie)
ESA 2006 – Proc. 14th European Symposium on Algorithms, pp. 88–99.
Full paper appeared in ACM Trans. Algorithms 2009
@inproceedings{BecchettiMarchetti-SpaccamelaVitaletti+2006,
author = {Becchetti, Luca and Marchetti{-}Spaccamela, Alberto and Vitaletti, Andrea and Korteweg, Peter and Skutella, Martin and Stougie, Leen},
title = {Latency Constrained Aggregation in Sensor Networks},
booktitle = {ESA 2006 – Proc. 14th European Symposium on Algorithms},
pages = {88--99},
year = {2006},
doi = {10.1007/11841036\_11},
}
- Multiline Addressing by Network Flow (Friedrich Eisenbrand, Andreas Karrenbauer, Martin Skutella and Chihao Xu)
ESA 2006 – Proc. 14th European Symposium on Algorithms, pp. 744–755.
Full paper appeared in Algorithmica 2009
@inproceedings{EisenbrandKarrenbauerSkutella+2006,
author = {Eisenbrand, Friedrich and Karrenbauer, Andreas and Skutella, Martin and Xu, Chihao},
title = {Multiline Addressing by Network Flow},
booktitle = {ESA 2006 – Proc. 14th European Symposium on Algorithms},
pages = {744--755},
year = {2006},
doi = {10.1007/11841036\_66},
}
- List Scheduling in Order of \(\alpha\)-Points on a Single Machine (Martin Skutella)
Chapter in Efficient Approximation and Online Algorithms – Recent Progress on Classical Combinatorial Optimization Problems and New Applications, 2006.
@incollection{Skutella2006,
author = {Skutella, Martin},
title = {List Scheduling in Order of {\(\alpha\)}-Points on a Single Machine},
booktitle = {Efficient Approximation and Online Algorithms -- Recent Progress on
Classical Combinatorial Optimization Problems and New Applications},
pages = {250--291},
year = {2006},
doi = {10.1007/11671541\_9},
}
- Stochastic Machine Scheduling with Precedence Constraints (Martin Skutella and Marc Uetz)
SIAM J. Comput., 34(4):788–802, 2005.
Extended abstract appeared in Proc. of SODA 2001
@article{SkutellaUetz2005,
author = {Skutella, Martin and Uetz, Marc},
title = {Stochastic Machine Scheduling with Precedence Constraints},
journal = {SIAM J. Comput.},
volume = {34},
number = {4},
pages = {788--802},
year = {2005},
doi = {10.1137/S0097539702415007},
}
- Flows over Time with Load-Dependent Transit Times (Ekkehard Köhler and Martin Skutella)
SIAM J. Optim., 15(4):1185–1202, 2005.
Extended abstract appeared in Proc. of SODA 2002
@article{KoehlerSkutella2005,
author = {K{\"{o}}hler, Ekkehard and Skutella, Martin},
title = {Flows over Time with Load-Dependent Transit Times},
journal = {SIAM J. Optim.},
volume = {15},
number = {4},
pages = {1185--1202},
year = {2005},
doi = {10.1137/S1052623403432645},
}
- The $k$-Splittable Flow Problem (Georg Baier, Ekkehard Köhler and Martin Skutella)
Algorithmica, 42(3-4):231–248, 2005.
Extended abstract appeared in Proc. of ESA 2002
@article{BaierKoehlerSkutella2005,
author = {Baier, Georg and K{\"{o}}hler, Ekkehard and Skutella, Martin},
title = {The $k$-Splittable Flow Problem},
journal = {Algorithmica},
volume = {42},
number = {3-4},
pages = {231--248},
year = {2005},
doi = {10.1007/s00453-005-1167-9},
}
- Approximating $k$-hop minimum-spanning trees (Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos and Martin Skutella)
Oper. Res. Lett., 33(2):115–120, 2005.
@article{AlthausFunkeHar-Peled+2005,
author = {Althaus, Ernst and Funke, Stefan and {Har-Peled}, Sariel and Könemann, Jochen and Ramos, Edgar A. and Skutella, Martin},
title = {Approximating $k$-hop minimum-spanning trees},
journal = {Oper. Res. Lett.},
volume = {33},
number = {2},
pages = {115--120},
year = {2005},
doi = {10.1016/j.orl.2004.05.005},
}
- New Approaches for Virtual Private Network Design (Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo and Martin Skutella)
ICALP 2005 – Proc. 32nd International Colloquium on Automata, Languages and Programming, pp. 1151–1162.
Full paper appeared in SIAM J. Comput. 2007
@inproceedings{EisenbrandGrandoniOriolo+2005,
author = {Eisenbrand, Friedrich and Grandoni, Fabrizio and Oriolo, Gianpaolo and Skutella, Martin},
title = {New Approaches for Virtual Private Network Design},
booktitle = {ICALP 2005 – Proc. 32nd International Colloquium on Automata, Languages and Programming},
pages = {1151--1162},
year = {2005},
doi = {10.1007/11523468\_93},
}
- Approximation and Complexity of $k$-Splittable Flows (Ronald Koch, Martin Skutella and Ines Spenke)
WAOA 2005 – Proc. 3rd Workshop on Approximation and Online Algorithms, pp. 244–257.
Full paper appeared in Theory Comput. Syst. 2008
@inproceedings{KochSkutellaSpenke2005,
author = {Koch, Ronald and Skutella, Martin and Spenke, Ines},
title = {Approximation and Complexity of $k$-Splittable Flows},
booktitle = {WAOA 2005 – Proc. 3rd Workshop on Approximation and Online Algorithms},
pages = {244--257},
year = {2005},
doi = {10.1007/11671411\_19},
}
- Length-Bounded and Dynamic $k$-Splittable Flows (Maren Martens and Martin Skutella)
OR 2005 – Proc. International Conference of the German Operations Research Society, pp. 297–302.
@inproceedings{MartensSkutella2005,
author = {Martens, Maren and Skutella, Martin},
title = {Length-Bounded and Dynamic $k$-Splittable Flows},
booktitle = {OR 2005 – Proc. International Conference of the German Operations Research Society},
pages = {297--302},
year = {2005},
doi = {10.1007/3-540-32539-5\_47},
}
- Scheduling with AND/OR Precedence Constraints (Rolf H. Möhring, Martin Skutella and Frederik Stork)
SIAM J. Comput., 33(2):393–415, 2004.
Extended abstract appeared in Proc. of SODA 2000
@article{MoehringSkutellaStork2004,
author = {M{\"{o}}hring, Rolf H. and Skutella, Martin and Stork, Frederik},
title = {Scheduling with {AND/OR} Precedence Constraints},
journal = {SIAM J. Comput.},
volume = {33},
number = {2},
pages = {393--415},
year = {2004},
doi = {10.1137/S009753970037727X},
}
- Cooperative facility location games (Michel X. Goemans and Martin Skutella)
J. Algorithms, 50(2):194–214, 2004.
Extended abstract appeared in Proc. of SODA 2000
@article{GoemansSkutella2004,
author = {Goemans, Michel X. and Skutella, Martin},
title = {Cooperative facility location games},
journal = {J. Algorithms},
volume = {50},
number = {2},
pages = {194--214},
year = {2004},
doi = {10.1016/S0196-6774(03)00098-1},
}
- Online Scheduling with Bounded Migration (Peter Sanders, Naveen Sivadasan and Martin Skutella)
ICALP 2004 – Proc. 31st International Colloquium on Automata, Languages and Programming, pp. 1111–1122.
Full paper appeared in Math. Oper. Res. 2009
@inproceedings{SandersSivadasanSkutella2004,
author = {Sanders, Peter and Sivadasan, Naveen and Skutella, Martin},
title = {Online Scheduling with Bounded Migration},
booktitle = {ICALP 2004 – Proc. 31st International Colloquium on Automata, Languages and Programming},
pages = {1111--1122},
year = {2004},
doi = {10.1007/978-3-540-27836-8\_92},
}
- Flows on Few Paths: Algorithms and Lower Bounds (Maren Martens and Martin Skutella)
ESA 2004 – Proc. 12th European Symposium on Algorithms, pp. 520–531.
Full paper appeared in Networks 2006
@inproceedings{MartensSkutella2004,
author = {Martens, Maren and Skutella, Martin},
title = {Flows on Few Paths: Algorithms and Lower Bounds},
booktitle = {ESA 2004 – Proc. 12th European Symposium on Algorithms},
pages = {520--531},
year = {2004},
doi = {10.1007/978-3-540-30140-0\_47},
}
- Preemptive scheduling with rejection (Han Hoogeveen, Martin Skutella and Gerhard J. Woeginger)
Math. Program., 94(2-3):361–374, 2003.
Extended abstract appeared in Proc. of ESA 2000
@article{HoogeveenSkutellaWoeginger2003,
author = {Hoogeveen, Han and Skutella, Martin and Woeginger, Gerhard J.},
title = {Preemptive scheduling with rejection},
journal = {Math. Program.},
volume = {94},
number = {2-3},
pages = {361--374},
year = {2003},
doi = {10.1007/s10107-002-0324-z},
}
- The complexity of economic equilibria for house allocation markets (Sándor P. Fekete, Martin Skutella and Gerhard J. Woeginger)
Inf. Process. Lett., 88(5):219–223, 2003.
@article{FeketeSkutellaWoeginger2003,
author = {Fekete, S{\'{a}}ndor P. and Skutella, Martin and Woeginger, Gerhard J.},
title = {The complexity of economic equilibria for house allocation markets},
journal = {Inf. Process. Lett.},
volume = {88},
number = {5},
pages = {219--223},
year = {2003},
doi = {10.1016/j.ipl.2003.08.008},
}
- Minimum cost flows over time without intermediate storage (Lisa Fleischer and Martin Skutella)
SODA 2003 – Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, pp. 66–75.
Full paper appeared in SIAM J. Comput. 2007
@inproceedings{FleischerSkutella2003,
author = {Fleischer, Lisa and Skutella, Martin},
title = {Minimum cost flows over time without intermediate storage},
booktitle = {SODA 2003 – Proc. 14th ACM-SIAM Symposium on Discrete Algorithms},
pages = {66--75},
year = {2003},
url = {http://dl.acm.org/citation.cfm?id=644108.644118},
}
- Multicommodity Flows over Time: Efficient Algorithms and Complexity (Alexander Hall, Steffen Hippler and Martin Skutella)
ICALP 2003 – Proc. 30th International Colloquium on Automata, Languages and Programming, pp. 397–409.
Full paper appeared in Theor. Comput. Sci. 2007
@inproceedings{HallHipplerSkutella2003,
author = {Hall, Alexander and Hippler, Steffen and Skutella, Martin},
title = {Multicommodity Flows over Time: Efficient Algorithms and Complexity},
booktitle = {ICALP 2003 – Proc. 30th International Colloquium on Automata, Languages and Programming},
pages = {397--409},
year = {2003},
doi = {10.1007/3-540-45061-0\_33},
}
- An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times (Alexander Hall, Katharina Langkau and Martin Skutella)
APPROX 2003 – Proc. 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 71–82.
Full paper appeared in Algorithmica 2007
@inproceedings{HallLangkauSkutella2003,
author = {Hall, Alexander and Langkau, Katharina and Skutella, Martin},
title = {An {FPTAS} for Quickest Multicommodity Flows with Inflow-Dependent
Transit Times},
booktitle = {APPROX 2003 – Proc. 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems},
pages = {71--82},
year = {2003},
doi = {10.1007/978-3-540-45198-3\_7},
}
- Approximating the single source unsplittable min-cost flow problem (Martin Skutella)
Math. Program., 91(3):493–514, 2002.
Extended abstract appeared in Proc. of FOCS 2000
@article{Skutella2002,
author = {Skutella, Martin},
title = {Approximating the single source unsplittable min-cost flow problem},
journal = {Math. Program.},
volume = {91},
number = {3},
pages = {493--514},
year = {2002},
doi = {10.1007/s101070100260},
}
- The Power of $\alpha$-Points in Preemptive Single Machine Scheduling (Andreas S. Schulz and Martin Skutella)
J. Sched., 5:121–133, 2002.
@article{SchulzSkutella2002a,
author = {Schulz, Andreas S. and Skutella, Martin},
journal = {J. Sched.},
pages = {121--133},
title = {The Power of $\alpha$-Points in Preemptive Single Machine Scheduling},
volume = {5},
year = {2002},
doi = {10.1002/jos.93},
}
- Single Machine Scheduling with Release Dates (Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz, Martin Skutella and Yaoguang Wang)
SIAM J. Discret. Math., 15(2):165–192, 2002.
@article{GoemansQueyranneSchulz+2002,
author = {Goemans, Michel X. and Queyranne, Maurice and Schulz, Andreas S. and Skutella, Martin and Wang, Yaoguang},
title = {Single Machine Scheduling with Release Dates},
journal = {SIAM J. Discret. Math.},
volume = {15},
number = {2},
pages = {165--192},
year = {2002},
doi = {10.1137/S089548019936223X},
}
- Scheduling Unrelated Machines by Randomized Rounding (Andreas S. Schulz and Martin Skutella)
SIAM J. Discret. Math., 15(4):450–469, 2002.
Extended abstract appeared in Proc. of ESA 1997
@article{SchulzSkutella2002,
author = {Schulz, Andreas S. and Skutella, Martin},
title = {Scheduling Unrelated Machines by Randomized Rounding},
journal = {SIAM J. Discret. Math.},
volume = {15},
number = {4},
pages = {450--469},
year = {2002},
doi = {10.1137/S0895480199357078},
}
- Flows over time with load-dependent transit times (Ekkehard Köhler and Martin Skutella)
SODA 2002 – Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 174–183.
Full paper appeared in SIAM J. Optim. 2005
@inproceedings{KoehlerSkutella2002,
author = {K{\"{o}}hler, Ekkehard and Skutella, Martin},
title = {Flows over time with load-dependent transit times},
booktitle = {SODA 2002 – Proc. 13th ACM-SIAM Symposium on Discrete Algorithms},
pages = {174--183},
year = {2002},
url = {http://dl.acm.org/citation.cfm?id=545381.545403},
}
- The freeze-tag problem: how to wake up a swarm of robots (Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell and Martin Skutella)
SODA 2002 – Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 568–577.
Full paper appeared in Algorithmica 2006
@inproceedings{ArkinBenderFekete2002,
author = {Arkin, Esther M. and Bender, Michael A. and Fekete, S{\'{a}}ndor P. and Mitchell, Joseph S. B. and Skutella, Martin},
title = {The freeze-tag problem: how to wake up a swarm of robots},
booktitle = {SODA 2002 – Proc. 13th ACM-SIAM Symposium on Discrete Algorithms},
pages = {568--577},
year = {2002},
url = {http://dl.acm.org/citation.cfm?id=545381.545457},
}
- The Quickest Multicommodity Flow Problem (Lisa Fleischer and Martin Skutella)
IPCO 2002 – Proc. 9th Conference on Integer Programming and Combinatorial Optimization, pp. 36–53.
Full paper appeared in SIAM J. Comput. 2007
@inproceedings{FleischerSkutella2002,
author = {Fleischer, Lisa and Skutella, Martin},
title = {The Quickest Multicommodity Flow Problem},
booktitle = {IPCO 2002 – Proc. 9th Conference on Integer Programming and Combinatorial Optimization},
pages = {36--53},
year = {2002},
doi = {10.1007/3-540-47867-1\_4},
}
- On the $k$-Splittable Flow Problem (Georg Baier, Ekkehard Köhler and Martin Skutella)
ESA 2002 – Proc. 10th European Symposium on Algorithms, pp. 101–113.
Full paper appeared in Algorithmica 2005
@inproceedings{BaierKoehlerSkutella2002,
author = {Baier, Georg and K{\"{o}}hler, Ekkehard and Skutella, Martin},
title = {On the $k$-Splittable Flow Problem},
booktitle = {ESA 2002 – Proc. 10th European Symposium on Algorithms},
pages = {101--113},
year = {2002},
doi = {10.1007/3-540-45749-6\_13},
}
- Time-Expanded Graphs for Flow-Dependent Transit Times (Ekkehard Köhler, Katharina Langkau and Martin Skutella)
ESA 2002 – Proc. 10th European Symposium on Algorithms, pp. 599–611.
@inproceedings{KoehlerLangkauSkutella2002,
author = {K{\"{o}}hler, Ekkehard and Langkau, Katharina and Skutella, Martin},
title = {Time-Expanded Graphs for Flow-Dependent Transit Times},
booktitle = {ESA 2002 – Proc. 10th European Symposium on Algorithms},
pages = {599--611},
year = {2002},
doi = {10.1007/3-540-45749-6\_53},
}
- A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines (Martin Skutella and Gerhard J. Woeginger)
Math. Oper. Res., 25(1):63–75, 2000.
Extended abstract appeared in Proc. of STOC 1999
@article{SkutellaWoeginger2000,
author = {Skutella, Martin and Woeginger, Gerhard J.},
title = {A {PTAS} for Minimizing the Total Weighted Completion Time on Identical
Parallel Machines},
journal = {Math. Oper. Res.},
volume = {25},
number = {1},
pages = {63--75},
year = {2000},
doi = {10.1287/moor.25.1.63.15212},
}
- Approximating the single source unsplittable min-cost flow problem (Martin Skutella)
FOCS 2000 – Proc. 41st Symposium on Foundations of Computer Science, pp. 136–145.
Full paper appeared in Math. Program. 2002
@inproceedings{Skutella2000,
author = {Skutella, Martin},
title = {Approximating the single source unsplittable min-cost flow problem},
booktitle = {FOCS 2000 – Proc. 41st Symposium on Foundations of Computer Science},
pages = {136--145},
year = {2000},
doi = {10.1109/SFCS.2000.892073},
}
- Cooperative facility location games (Michel X. Goemans and Martin Skutella)
SODA 2000 – Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 76–85.
Full paper appeared in J. Algorithms 2004
@inproceedings{GoemansSkutella2000,
author = {Goemans, Michel X. and Skutella, Martin},
title = {Cooperative facility location games},
booktitle = {SODA 2000 – Proc. 11th ACM-SIAM Symposium on Discrete Algorithms},
pages = {76--85},
year = {2000},
url = {http://dl.acm.org/citation.cfm?id=338219.338238},
}
- Forcing relations for AND/OR precedence constraints (Rolf H. Möhring, Martin Skutella and Frederik Stork)
SODA 2000 – Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 235–236.
Full paper appeared in SIAM J. Comput. 2004
@inproceedings{MoehringSkutellaStork2000,
author = {M{\"{o}}hring, Rolf H. and Skutella, Martin and Stork, Frederik},
title = {Forcing relations for {AND/OR} precedence constraints},
booktitle = {SODA 2000 – Proc. 11th ACM-SIAM Symposium on Discrete Algorithms},
pages = {235--236},
year = {2000},
url = {http://dl.acm.org/citation.cfm?id=338219.338257},
}
- Preemptive Scheduling with Rejection (Han Hoogeveen, Martin Skutella and Gerhard J. Woeginger)
ESA 2000 – Proc. 8th European Symposium on Algorithms, pp. 268–277.
Full paper appeared in Math. Program. 2003
@inproceedings{HoogeveenSkutellaWoeginger2000,
author = {Hoogeveen, Han and Skutella, Martin and Woeginger, Gerhard J.},
title = {Preemptive Scheduling with Rejection},
booktitle = {ESA 2000 – Proc. 8th European Symposium on Algorithms},
pages = {268--277},
year = {2000},
doi = {10.1007/3-540-45253-2\_25},
}
- Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates (Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein and Maxim Sviridenko)
FOCS 1999 – Proc. 40th Symposium on Foundations of Computer Science, pp. 32–44.
@inproceedings{AfratiBampisChekuri+1999,
author = {Afrati, Foto N. and
Bampis, Evripidis and
Chekuri, Chandra and
Karger, David R. and
Kenyon, Claire and
Khanna, Sanjeev and
Milis, Ioannis and
Queyranne, Maurice and
Skutella, Martin and
Stein, Clifford and
Sviridenko, Maxim},
title = {Approximation Schemes for Minimizing Average Weighted Completion Time
with Release Dates},
booktitle = {FOCS 1999 – Proc. 40th Symposium on Foundations of Computer Science},
pages = {32--44},
year = {1999},
doi = {10.1109/SFFCS.1999.814574},
}
- A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines (Martin Skutella and Gerhard J. Woeginger)
STOC 1999 – Proc. 31st Symposium on Theory of Computing, pp. 400–407.
Full paper appeared in Math. Oper. Res. 2000
@inproceedings{SkutellaWoeginger1999,
author = {Skutella, Martin and Woeginger, Gerhard J.},
title = {A {PTAS} for Minimizing the Weighted Sum of Job Completion Times on
Parallel Machines},
booktitle = {STOC 1999 – Proc. 31st Symposium on Theory of Computing},
pages = {400--407},
year = {1999},
doi = {10.1145/301250.301356},
}
- Convex Quadratic Programming Relaxations for Network Scheduling Problems (Martin Skutella)
ESA 1999 – Proc. 7th European Symposium on Algorithms, pp. 127–138.
Full paper appeared in J. ACM 2001
@inproceedings{Skutella1999a,
author = {Skutella, Martin},
title = {Convex Quadratic Programming Relaxations for Network Scheduling Problems},
booktitle = {ESA 1999 – Proc. 7th European Symposium on Algorithms},
pages = {127--138},
year = {1999},
doi = {10.1007/3-540-48481-7\_12},
}
- Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem (Martin Skutella)
SODA 1997 – Proc. 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 501–508.
Full paper appeared in Math. Oper. Res. 2000
@inproceedings{Skutella1997,
author = {Skutella, Martin},
title = {Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem},
booktitle = {SODA 1997 – Proc. 8th ACM-SIAM Symposium on Discrete Algorithms},
pages = {501--508},
year = {1997},
url = {https://dl.acm.org/doi/10.5555/314161.314375},
}
- Scheduling-LPs Bear Probabilities: Randomized Approximations for Min-Sum Criteria (Andreas S. Schulz and Martin Skutella)
ESA 1997 – Proc. 5th European Symposium on Algorithms, pp. 416–429.
Full paper appeared in SIAM J. Discret. Math. 2002
@inproceedings{SchulzSkutella1997,
author = {Schulz, Andreas S. and Skutella, Martin},
title = {Scheduling-LPs Bear Probabilities: Randomized Approximations for Min-Sum
Criteria},
booktitle = {ESA 1997 – Proc. 5th European Symposium on Algorithms},
pages = {416--429},
year = {1997},
doi = {10.1007/3-540-63397-9\_32},
}
- Random-Based Scheduling: New Approximations and LP Lower Bounds (Andreas S. Schulz and Martin Skutella)
RANDOM 1997 – Proc. 1st International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 119–133.
Full paper appeared in J. Sched. 2002
@inproceedings{SchulzSkutella1997a,
author = {Schulz, Andreas S. and Skutella, Martin},
title = {Random-Based Scheduling: New Approximations and {LP} Lower Bounds},
booktitle = {RANDOM 1997 – Proc. 1st International Workshop on Randomization and Approximation Techniques in Computer Science},
pages = {119--133},
year = {1997},
doi = {10.1007/3-540-63248-4\_11},
}
- Parallel Repetition of MIP(2, 1) Systems (Clemens Gröpl and Martin Skutella)
Chapter in Lectures on Proof Verification and Approximation Algorithms, 1997.
@incollection{GroeplSkutella1997,
author = {Gr{\"{o}}pl, Clemens and Skutella, Martin},
title = {Parallel Repetition of MIP(2, 1) Systems},
booktitle = {Lectures on Proof Verification and Approximation Algorithms},
pages = {161--178},
year = {1997},
doi = {10.1007/BFb0053016},
}
