MPI-INF Logo
Homepage

Contact

Krzysztof Fleszar

Krzysztof Fleszar

My new affiliation is University of Warsaw

My former affiliation:
Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
 email: kfleszar@mpi-inf.mpg.de
ORCID iD icon orcid.org ID: 0000-0002-1129-3289

Research Interests

  • Approximation Algorithms (e.g. for k-Medians, Traveling Salesman and Disjoint Paths problems)
  • Online Algorithms (e.g. Maximum Matchings and Machine Scheduling)
  • Geometric Optimization Problems (e.g. Stabbing rectangles with lines)

Publications

Please see my dblp page for an up-to-date list of my publications.

Matching entries: 0
settings...
Aparna Das, Krzysztof Fleszar, Stephen Kobourov, Joachim Spoerhase, Sankar Veeramoni, and Alexander Wolff (2018), "Approximating the Generalized Minimum Manhattan Network Problem", Algorithmica., Apr, 2018. Vol. 80(4), pp. 1170-1190.
BibTeX:
@article{gmmn-algorithmica-18,
  author = {Das, Aparna and Fleszar, Krzysztof and Kobourov, Stephen and Spoerhase, Joachim and Veeramoni, Sankar and Wolff, Alexander},
  title = {Approximating the Generalized Minimum Manhattan Network Problem},
  journal = {Algorithmica},
  year = {2018},
  volume = {80},
  number = {4},
  pages = {1170--1190},
  url = {https://doi.org/10.1007/s00453-017-0298-0}
}
Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma, and Kevin Schewior (2018), "A PTAS for Euclidean TSP with Hyperplane Neighborhoods", In Proc. ACM-SIAM Symp. Discrete Algorithms (SODA'19). (To appear)
BibTeX:
@inproceedings{tspnhyperplanes-18,
  author = {Antonios Antoniadis and Krzysztof Fleszar and Ruben Hoeksma and Kevin Schewior},
  title = {A PTAS for Euclidean TSP with Hyperplane Neighborhoods},
  booktitle = {Proc. ACM-SIAM Symp. Discrete Algorithms (SODA'19)},
  year = {2018},
  number = {To appear},
  note = {(https://arxiv.org/abs/1804.03953)},
  url = {https://arxiv.org/abs/1804.03953}
}
Timothy M. Chan, Thomas C. Van Dijk, Krzysztof Fleszar, Joachim Spoerhase, and Alexander Wolff (2018), "Stabbing Rectangles by Line Segments – How Decomposition Reduces the Shallow-Cell Complexity", In Proc. 29th Int. Symp. Algorithms Comput. (ISAAC'18). (To appear)
BibTeX:
@inproceedings{stabbing-18,
  author = {Timothy M. Chan and Thomas C. Van Dijk and Krzysztof Fleszar and Joachim Spoerhase and Alexander Wolff},
  title = {Stabbing Rectangles by Line Segments – How Decomposition Reduces the Shallow-Cell Complexity},
  booktitle = {Proc. 29th Int. Symp. Algorithms Comput. (ISAAC'18)},
  year = {2018},
  number = {To appear},
  note = {(https://arxiv.org/abs/1806.02851)},
  url = {https://arxiv.org/abs/1806.02851}
}
Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase (2018), "New algorithms for maximum disjoint paths based on tree-likeness", Mathematical Programming. Vol. 171(1-2), pp. 433-461.
BibTeX:
@article{edge-disjoint-paths-mapr-17,
  author = {Fleszar, Krzysztof and Mnich, Matthias and Spoerhase, Joachim},
  title = {New algorithms for maximum disjoint paths based on tree-likeness},
  journal = {Mathematical Programming},
  year = {2018},
  volume = {171},
  number = {1-2},
  pages = {433--461}
}
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, and Alexander Wolff (2017), "The Complexity of Drawing Graphs on Few Lines and Few Planes", In Proc. Algorithms Data Struct. Symp. (WADS'17). , pp. 265-276. Springer.
BibTeX:
@inproceedings{complexity-rho-wads-17,
  author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander},
  editor = {Ellen, Faith and Kolokolova, Antonina and Sack, Jörg-Rüdiger},
  title = {The Complexity of Drawing Graphs on Few Lines and Few Planes},
  booktitle = {Proc. Algorithms Data Struct. Symp. (WADS'17)},
  publisher = {Springer},
  year = {2017},
  pages = {265--276},
  url = {https://doi.org/10.1007/978-3-319-62127-2_23}
}
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, and Alexander Wolff (2016), "Drawing Graphs on Few Lines and Few Planes", In Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD'16). Vol. 9801, pp. 166-180. Springer.
BibTeX:
@inproceedings{few-lines-and-planes-16,
  author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander},
  editor = {Hu, Yifan and Nöllenburg, Martin},
  title = {Drawing Graphs on Few Lines and Few Planes},
  booktitle = {Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD'16)},
  publisher = {Springer},
  year = {2016},
  volume = {9801},
  pages = {166--180},
  url = {http://dx.doi.org/10.1007/978-3-319-50106-2_14},
  doi = {10.1007/978-3-319-50106-2_14}
}
William S. Evans, Krzysztof Fleszar, Philipp Kindermann, Noushin Saeedi, Chan-Su Shin, and Alexander Wolff (2016), "Minimum Rectilinear Polygons for Given Angle Sequences", In Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCGG'15). Vol. 9943, pp. 105-119. Springer.
BibTeX:
@inproceedings{lr-sequences-16,
  author = {Evans, William S. and Fleszar, Krzysztof and Kindermann, Philipp and Saeedi, Noushin and Shin, Chan-Su and Wolff, Alexander},
  editor = {Akiyama, Jin and Ito, Hiro and Sakai, Toshinori},
  title = {Minimum Rectilinear Polygons for Given Angle Sequences},
  booktitle = {Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCGG'15)},
  publisher = {Springer},
  year = {2016},
  volume = {9943},
  pages = {105--119},
  url = {http://dx.doi.org/10.1007/978-3-319-48532-4_10},
  doi = {10.1007/978-3-319-48532-4_10}
}
Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase (2016), "New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness", In 24th Europ. Symp. Algorithms (ESA'16). Vol. 57, pp. 42:1-42:17. Schloss Dagstuhl -- Leibniz-Zentrum für Informatik.
BibTeX:
@inproceedings{edge-disjoint-paths-16,
  author = {Fleszar, Krzysztof and Mnich, Matthias and Spoerhase, Joachim},
  editor = {Sankowski, Piotr and Zaroliagis, Christos},
  title = {New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness},
  booktitle = {24th Europ. Symp. Algorithms (ESA'16)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  year = {2016},
  volume = {57},
  pages = {42:1--42:17},
  url = {http://drops.dagstuhl.de/opus/volltexte/2016/6354}
}
Sergey Bereg, Krzysztof Fleszar, Philipp Kindermann, Sergey Pupyrev, Joachim Spoerhase, and Alexander Wolff (2015), "Colored Non-Crossing Euclidean Steiner Forest", In Proc. 26th Int. Symp. Algorithms Comput. (ISAAC'15)., December, 2015. Vol. 9472, pp. 429-441. Springer.
BibTeX:
@inproceedings{colored-steiner-isaac-15,
  author = {Bereg, Sergey and Fleszar, Krzysztof and Kindermann, Philipp and Pupyrev, Sergey and Spoerhase, Joachim and Wolff, Alexander},
  editor = {Elbassioni, Khaled and Makino, Kazuhisa},
  title = {Colored Non-Crossing Euclidean Steiner Forest},
  booktitle = {Proc. 26th Int. Symp. Algorithms Comput. (ISAAC'15)},
  publisher = {Springer},
  year = {2015},
  volume = {9472},
  pages = {429-441},
  url = {http://dx.doi.org/10.1007/978-3-662-48971-0_37}
}
Jarosław Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase (2015), "Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems", In Proc. ACM-SIAM Symp. Discrete Algorithms (SODA'15).
BibTeX:
@inproceedings{kmedian-soda-15,
  author = {Byrka, Jarosław and Fleszar, Krzysztof and Rybicki, Bartosz and Spoerhase, Joachim},
  title = {Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems},
  booktitle = {Proc. ACM-SIAM Symp. Discrete Algorithms (SODA'15)},
  year = {2015},
  url = {https://arxiv.org/abs/1312.6550}
}
Aparna Das, Krzysztof Fleszar, Stephen G. Kobourov, Joachim Spoerhase, Sankar Veeramoni, and Alexander Wolff (2013), "Polylogarithmic Approximation for Generalized Minimum Manhattan Networks", In Proc. 29th Europ. Workshop Comput. Geom. (EuroCG'13). Braunschweig, March, 2013.
BibTeX:
@inproceedings{gmmn-eurocg-13,
  author = {Das, Aparna and Fleszar, Krzysztof and Kobourov, Stephen G. and Spoerhase, Joachim and Veeramoni, Sankar and Wolff, Alexander},
  editor = {Fekete, Sándor},
  title = {Polylogarithmic Approximation for Generalized Minimum Manhattan Networks},
  booktitle = {Proc. 29th Europ. Workshop Comput. Geom. (EuroCG'13)},
  year = {2013},
  url = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/dfksvw-pagmm-EuroCG13.pdf}
}
Aparna Das, Krzysztof Fleszar, Stephen G. Kobourov, Joachim Spoerhase, Sankar Veeramoni, and Alexander Wolff (2013), "Approximating the Generalized Minimum Manhattan Network Problem.", In Proc. 24th Int. Symp. Algorithms Comput. (ISAAC'13). Vol. 8283, pp. 722-732. Springer.
BibTeX:
@inproceedings{gmmn-isaac-13,
  author = {Das, Aparna and Fleszar, Krzysztof and Kobourov, Stephen G. and Spoerhase, Joachim and Veeramoni, Sankar and Wolff, Alexander},
  editor = {Cai, Leizhen and Cheng, Siu-Wing and Lam, Tak Wah},
  title = {Approximating the Generalized Minimum Manhattan Network Problem.},
  booktitle = {Proc. 24th Int. Symp. Algorithms Comput. (ISAAC'13)},
  publisher = {Springer},
  year = {2013},
  volume = {8283},
  pages = {722-732},
  url = {https://doi.org/10.1007/978-3-642-45030-3_67}
}
Thomas. C. van Dijk, Krzysztof Fleszar, Jan-Henrik Haunert, and Joachim Spoerhase (2013), "Road Segment Selection with Strokes and Stability", In Proc. 1st ACM SIGSPATIAL Int. Workshop MapInteraction (MapInteract'13). New York, NY, USA , pp. 72-77. ACM.
BibTeX:
@inproceedings{strokes-map-13,
  author = {van Dijk, Thomas. C. and Fleszar, Krzysztof and Haunert, Jan-Henrik and Spoerhase, Joachim},
  title = {Road Segment Selection with Strokes and Stability},
  booktitle = {Proc. 1st ACM SIGSPATIAL Int. Workshop MapInteraction (MapInteract'13)},
  publisher = {ACM},
  year = {2013},
  pages = {72--77},
  url = {http://doi.acm.org/10.1145/2534931.2534936},
  doi = {10.1145/2534931.2534936}
}
Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, and Maximilian Witek (2012), "Structural Complexity of Multiobjective NP Search Problems", In Proc. 10th Latin American Symp. Theoretical Informatics (LATIN'12). Vol. 7256, pp. 338-349. Springer.
BibTeX:
@inproceedings{multiobjective-latin-12,
  author = {Fleszar, Krzysztof and Glaßer, Christian and Lipp, Fabian and Reitwießner, Christian and Witek, Maximilian},
  editor = {Fernández-Baca, David},
  title = {Structural Complexity of Multiobjective NP Search Problems},
  booktitle = {Proc. 10th Latin American Symp. Theoretical Informatics (LATIN'12)},
  publisher = {Springer},
  year = {2012},
  volume = {7256},
  pages = {338-349},
  url = {http://dx.doi.org/10.1007/978-3-642-29344-3_29},
  doi = {10.1007/978-3-642-29344-3_29}
}

Recent Positions

List of recent positions

Education

  • October 2012 - October 2017:
    PhD in Computer Science at University of Würzburg, Germany.
  • September 2010 - September 2012:
    Master's Degree in Computer Science (Generalized Minimum Manhattan Networks) at University of Würzburg, Germany.
  • October 2010 - August 2010:
    Bachelor's Degree in Computer Science (Complementation of Multihead Automata) at University of Würzburg, Germany.