Fleszar, Krzysztof

Stabbing Rectangles by Line Segments – How Decomposition Reduces the Shallow-Cell Complexity Chan, Timothy M.; Dijk, Thomas C. Van; Fleszar, Krzysztof; Spoerhase, Joachim; Wolff, Alexander (2018). Submitted

[ BibTeX ]

@article{stabbing-18,
  author = {Chan, Timothy M. and Dijk, Thomas C. Van and Fleszar, Krzysztof and Spoerhase, Joachim and Wolff, Alexander},
  keywords = {shallow-shell},
  title = {Stabbing Rectangles by Line Segments – How Decomposition Reduces the Shallow-Cell Complexity},
  volume = {Submitted},
  year = 2018
}

Approximating the Generalized Minimum {Manhattan} Network Problem Das, Aparna; Fleszar, Krzysztof; Kobourov, Stephen; Spoerhase, Joachim; Veeramoni, Sankar; Wolff, Alexander in Algorithmica (2018). 80(4) 1170–1190.

[ BibTeX ]
[ URL ]

@article{das-etal17:approximating-gmmn,
  author = {Das, Aparna and Fleszar, Krzysztof and Kobourov, Stephen and Spoerhase, Joachim and Veeramoni, Sankar and Wolff, Alexander},
  journal = {Algorithmica},
  keywords = {network},
  month = {apr},
  number = 4,
  pages = {1170–1190},
  title = {Approximating the Generalized Minimum {Manhattan} Network Problem},
  volume = 80,
  year = 2018
}

A {PTAS} for {E}uclidean {TSP} with Hyperplane Neighborhoods Antoniadis, Antonios; Fleszar, Krzysztof; Hoeksma, Ruben; Schewior, Kevin (2018). Submitted

[ BibTeX ]
[ URL ]

@article{tspnhyperplanes-18,
  author = {Antoniadis, Antonios and Fleszar, Krzysztof and Hoeksma, Ruben and Schewior, Kevin},
  keywords = {tsp},
  title = {A {PTAS} for {E}uclidean {TSP} with Hyperplane Neighborhoods},
  volume = {Submitted},
  year = 2018
}

New algorithms for maximum disjoint paths based on tree-likeness Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim in Mathematical Programming (2017).

[ BibTeX ]
[ URL ]

@article{fleszar2017algorithms,
  author = {Fleszar, Krzysztof and Mnich, Matthias and Spoerhase, Joachim},
  journal = {Mathematical Programming},
  keywords = {tree},
  month = {nov},
  title = {New algorithms for maximum disjoint paths based on tree-likeness},
  year = 2017
}

Approximating the Generalized Minimum {M}anhattan Network Problem Das, Aparna; Fleszar, Krzysztof; Kobourov, Stephen; Spoerhase, Joachim; Veeramoni, Sankar; Wolff, Alexander in Algorithmica (2017). 1–21.

[ BibTeX ]

@article{das-etal17:approximating-gmmn,
  author = {Das, Aparna and Fleszar, Krzysztof and Kobourov, Stephen and Spoerhase, Joachim and Veeramoni, Sankar and Wolff, Alexander},
  journal = {Algorithmica},
  keywords = {network},
  month = {March},
  pages = {1-21},
  title = {Approximating the Generalized Minimum {M}anhattan Network Problem},
  year = 2017
}

The Complexity of Drawing Graphs on Few Lines and Few Planes Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander in Proc. Algorithms Data Struct. Symp. (WADS’17), Lecture Notes in Computer Science, F. Ellen, A. Kolokolova, J.-R. Sack (eds.) (2017).

[ BibTeX ]

@inproceedings{cflrvw-cdgfl-WADS17,
  author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander},
  booktitle = {Proc. Algorithms Data Struct. Symp. (WADS'17)},
  editor = {Ellen, Faith and Kolokolova, Antonina and Sack, J{\"o}rg-R{\"u}diger},
  keywords = {planes},
  note = {to appear},
  publisher = {Springer International Publishing},
  series = {Lecture Notes in Computer Science},
  title = {The Complexity of Drawing Graphs on Few Lines and Few Planes},
  year = 2017
}

New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim in 24th Europ. Symp. Algorithms (ESA’16), Leibniz International Proceedings in Informatics (LIPIcs), P. Sankowski, C. Zaroliagis (eds.) (2016). (Vol. 57) 42:1–42:17.

[ BibTeX ]
[ URL ]

@inproceedings{DBLP:journals/corr/FleszarMS16,
  author = {Fleszar, Krzysztof and Mnich, Matthias and Spoerhase, Joachim},
  booktitle = {24th Europ. Symp. Algorithms (ESA'16)},
  editor = {Sankowski, Piotr and Zaroliagis, Christos},
  keywords = {vertex},
  pages = {42:1–42:17},
  publisher = {Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  title = {New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness},
  volume = 57,
  year = 2016
}

Minimum Rectilinear Polygons for Given Angle Sequences Evans, William S.; Fleszar, Krzysztof; Kindermann, Philipp; Saeedi, Noushin; Shin, Chan-Su; Wolff, Alexander in Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCGG’15), Lecture Notes in Computer Science, J. Akiyama, H. Ito, T. Sakai (eds.) (2016). (Vol. 9943) 105–119.

[ BibTeX ]
[ URL ]

@inproceedings{efkssw-mrpga-JCDCGG15,
  author = {Evans, William S. and Fleszar, Krzysztof and Kindermann, Philipp and Saeedi, Noushin and Shin, Chan-Su and Wolff, Alexander},
  booktitle = {Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCGG'15)},
  editor = {Akiyama, Jin and Ito, Hiro and Sakai, Toshinori},
  keywords = {sequence},
  pages = {105–119},
  publisher = {Springer International Publishing},
  series = {Lecture Notes in Computer Science},
  title = {Minimum Rectilinear Polygons for Given Angle Sequences},
  volume = 9943,
  year = 2016
}

Drawing Graphs on Few Lines and Few Planes Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander in Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Lecture Notes in Computer Science, Y. Hu, M. N{"o}llenburg (eds.) (2016). (Vol. 9801) 166–180.

[ BibTeX ]
[ URL ]

@inproceedings{cflrvw-dgflf-GD16,
  author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander},
  booktitle = {Proc. 24th Int. Symp. Graph Drawing \& Network Vis. (GD'16)},
  editor = {Hu, Yifan and N{\"o}llenburg, Martin},
  keywords = {structure},
  pages = {166–180},
  publisher = {Springer International Publishing},
  series = {Lecture Notes in Computer Science},
  title = {Drawing Graphs on Few Lines and Few Planes},
  volume = 9801,
  year = 2016
}

Colored Non-Crossing {E}uclidean {S}teiner Forest Bereg, Sergey; Fleszar, Krzysztof; Kindermann, Philipp; Pupyrev, Sergey; Spoerhase, Joachim; Wolff, Alexander in Proc. 26th Int. Symp. Algorithms Comput. (ISAAC’15), Lecture Notes in Computer Science, K. Elbassioni, K. Makino (eds.) (2015). (Vol. 9472) 429–441.

[ Abstract ]
[ BibTeX ]
[ URL ]

Given a set of \($k$\)-colored points in the plane, we consider the problem of finding \($k$\) trees such that each tree connects all points of one color class, no two trees cross, and the total edge length of the trees is minimized. For \($k=1$\), this is the well-known Euclidean Steiner tree problem. For general \($k$\), a \($k\rho$\)-approximation algorithm is known, where \($\rho \le 1.21$\) is the Steiner ratio. We present a PTAS for \($k=2$\), a \($(5/3+\varepsilon)$\)-approximation for \($k=3$\), and two approximation algorithms for general \($k$\), with ratios \($O(\sqrt n \log k)$\) and \($k+\varepsilon$\).

@inproceedings{bfkpsw-cnesf-isaac15,
  abstract = {Given a set of $k$-colored points in the plane, we consider the problem of finding $k$ trees such that each tree connects all points of one color class, no two trees cross, and the total edge length of the trees is minimized. For $k=1$, this is the well-known Euclidean Steiner tree problem. For general $k$, a $k\rho$-approximation algorithm is known, where $\rho \le 1.21$ is the Steiner ratio. We present a PTAS for $k=2$, a $(5/3+\varepsilon)$-approximation for $k=3$, and two approximation algorithms for general $k$, with ratios $O(\sqrt n \log k)$ and $k+\varepsilon$.},
  author = {Bereg, Sergey and Fleszar, Krzysztof and Kindermann, Philipp and Pupyrev, Sergey and Spoerhase, Joachim and Wolff, Alexander},
  booktitle = {Proc. 26th Int. Symp. Algorithms Comput. (ISAAC'15)},
  editor = {Elbassioni, Khaled and Makino, Kazuhisa},
  keywords = {noncrossing},
  month = {dec},
  pages = {429-441},
  publisher = {Springer Berlin Heidelberg},
  series = {Lecture Notes in Computer Science},
  title = {Colored Non-Crossing {E}uclidean {S}teiner Forest},
  volume = 9472,
  year = 2015
}

Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems Byrka, Jarosław; Fleszar, Krzysztof; Rybicki, Bartosz; Spoerhase, Joachim in Proc. ACM-SIAM Symp. Discrete Algorithms (SODA’15) (2015).

[ BibTeX ]
[ URL ]

@inproceedings{noauthororeditor2015bifactor,
  author = {Byrka, Jarosław and Fleszar, Krzysztof and Rybicki, Bartosz and Spoerhase, Joachim},
  booktitle = {Proc. ACM-SIAM Symp. Discrete Algorithms (SODA'15)},
  keywords = {myown},
  title = {Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems},
  year = 2015
}

Approximating the Generalized Minimum {Manhattan} Network Problem. Das, Aparna; Fleszar, Krzysztof; Kobourov, Stephen G.; Spoerhase, Joachim; Veeramoni, Sankar; Wolff, Alexander in Proc. 24th Int. Symp. Algorithms Comput. (ISAAC’13), Lecture Notes in Computer Science, L. Cai, S.-W. Cheng, T. W. Lam (eds.) (2013). (Vol. 8283) 722–732.

[ BibTeX ]
[ URL ]

@inproceedings{conf/isaac/DasFKSVW13,
  author = {Das, Aparna and Fleszar, Krzysztof and Kobourov, Stephen G. and Spoerhase, Joachim and Veeramoni, Sankar and Wolff, Alexander},
  booktitle = {Proc. 24th Int. Symp. Algorithms Comput. (ISAAC'13)},
  crossref = {conf/isaac/2013},
  editor = {Cai, Leizhen and Cheng, Siu-Wing and Lam, Tak Wah},
  keywords = {network},
  pages = {722-732},
  publisher = {Springer Berlin Heidelberg},
  series = {Lecture Notes in Computer Science},
  title = {Approximating the Generalized Minimum {Manhattan} Network Problem.},
  volume = 8283,
  year = 2013
}

Road Segment Selection with Strokes and Stability van Dijk, T. C.; Fleszar, K.; Haunert, J.-H.; Spoerhase, J. in Proc. 1st ACM SIGSPATIAL Int. Workshop MapInteraction (MapInteract’13) (2013). 72–77.

[ Abstract ]
[ BibTeX ]
[ URL ]

In order to visualize a road network without producing visual clutter, a subset of all road segments needs to be selected. Many algorithms for road segment selection are based on a relevance score for edges in a network (for example betweenness centrality) and proceed by taking a greedy selection based on these weights. This can give dissatisfactory results. In order to improve readability, we introduce a stroke-based constraint and provide an efficient dynamic program that makes an optimal selection given this constraint. Next, we consider the computation of animated road selections from changing edge weights (for example a focus area that follows a moving user). Handling each time step of the animation individually can lead to distracting flickering effects. Here we introduce an optimization objective to achieve a more stable selection and provide a polynomial-time algorithm for solving it. While separately solvable in polynomial time, we show that the combination of the stroke constraints and stability optimization is NP-hard.

@inproceedings{vanDijk:2013:RSS:2534931.2534936,
  abstract = {In order to visualize a road network without producing visual clutter, a subset of all road segments needs to be selected. Many algorithms for road segment selection are based on a relevance score for edges in a network (for example betweenness centrality) and proceed by taking a greedy selection based on these weights. This can give dissatisfactory results. In order to improve readability, we introduce a stroke-based constraint and provide an efficient dynamic program that makes an optimal selection given this constraint. Next, we consider the computation of animated road selections from changing edge weights (for example a focus area that follows a moving user). Handling each time step of the animation individually can lead to distracting flickering effects. Here we introduce an optimization objective to achieve a more stable selection and provide a polynomial-time algorithm for solving it. While separately solvable in polynomial time, we show that the combination of the stroke constraints and stability optimization is NP-hard.},
  address = {New York, NY, USA},
  author = {van Dijk, T. C. and Fleszar, K. and Haunert, J.-H. and Spoerhase, J.},
  booktitle = {Proc. 1st ACM SIGSPATIAL Int. Workshop MapInteraction (MapInteract'13)},
  keywords = {strokes},
  pages = {72–77},
  publisher = {ACM},
  title = {Road Segment Selection with Strokes and Stability},
  year = 2013
}

Polylogarithmic Approximation for Generalized Minimum {Manhattan} Networks Das, Aparna; Fleszar, Krzysztof; Kobourov, Stephen G.; Spoerhase, Joachim; Veeramoni, Sankar; Wolff, Alexander in Proc. 29th Europ. Workshop Comput. Geom. (EuroCG’13), S. Fekete (ed.) (2013).

[ BibTeX ]

@inproceedings{dfksvw-pagmm-EuroCG13,
  address = {Braunschweig},
  author = {Das, Aparna and Fleszar, Krzysztof and Kobourov, Stephen G. and Spoerhase, Joachim and Veeramoni, Sankar and Wolff, Alexander},
  booktitle = {Proc. 29th Europ. Workshop Comput. Geom. (EuroCG'13)},
  editor = {Fekete, S{\'a}ndor},
  keywords = {networks},
  month = {mar},
  title = {Polylogarithmic Approximation for Generalized Minimum {Manhattan} Networks},
  year = 2013
}

Structural Complexity of Multiobjective {NP} Search Problems Fleszar, Krzysztof; Glaßer, Christian; Lipp, Fabian; Reitwießner, Christian; Witek, Maximilian in Proc. 10th Latin American Symp. Theoretical Informatics (LATIN’12), Lecture Notes in Computer Science, D. Fernández-Baca (ed.) (2012). (Vol. 7256) 338–349.

[ Abstract ]
[ BibTeX ]
[ URL ]

An NP search problem is a multivalued function that maps instances to polynomially length-bounded solutions such that the validity of solutions is testable in polynomial time. NPMV_g denotes the class of these functions. There are at least two computational tasks associated with an NP search problem: (i) Find out whether a solution exists. (ii) Compute an arbitrary solution. Further computational tasks arise in settings with multiple objectives, for example: (iii) Compute a solution that is minimal w.r.t. the first objective, while the second objective does not exceed some budget. Each such computational task defines a class of multivalued functions. We systematically investigate these classes and their relation to traditional complexity classes and classes of multivalued functions, like NP or max·P. For multiobjective problems, some classes of computational tasks turn out to be equivalent to the function class NPMV_g , some to the class of decision problems NP, and some to a seemingly new class that includes both NPMV_g and NP. Under the assumption that certain exponential time classes are different, we show that there are computational tasks of multiobjective problems (more precisely functions in NPMV_g) that are Turing-inequivalent to any set.

@inproceedings{noKey,
  abstract = {An NP search problem is a multivalued function that maps instances to polynomially length-bounded solutions such that the validity of solutions is testable in polynomial time. NPMV_g denotes the class of these functions. There are at least two computational tasks associated with an NP search problem: (i) Find out whether a solution exists. (ii) Compute an arbitrary solution. Further computational tasks arise in settings with multiple objectives, for example: (iii) Compute a solution that is minimal w.r.t. the first objective, while the second objective does not exceed some budget. Each such computational task defines a class of multivalued functions. We systematically investigate these classes and their relation to traditional complexity classes and classes of multivalued functions, like NP or max·P. For multiobjective problems, some classes of computational tasks turn out to be equivalent to the function class NPMV_g , some to the class of decision problems NP, and some to a seemingly new class that includes both NPMV_g and NP. Under the assumption that certain exponential time classes are different, we show that there are computational tasks of multiobjective problems (more precisely functions in NPMV_g) that are Turing-inequivalent to any set.},
  author = {Fleszar, Krzysztof and Glaßer, Christian and Lipp, Fabian and Reitwießner, Christian and Witek, Maximilian},
  booktitle = {Proc. 10th Latin American Symp. Theoretical Informatics (LATIN'12)},
  editor = {Fernández-Baca, David},
  keywords = {optimization},
  pages = {338-349},
  publisher = {Springer Berlin Heidelberg},
  series = {Lecture Notes in Computer Science},
  title = {Structural Complexity of Multiobjective {NP} Search Problems},
  volume = 7256,
  year = 2012
}

Polylogarithmic Approximation for Generalized Minimum {Manhattan} Networks Das, Aparna; Fleszar, Krzysztof; Kobourov, Stephen G.; Spoerhase, Joachim; Veeramoni, Sankar; Wolff, Alexander (2012, April).

[ BibTeX ]
[ URL ]

@misc{dfksvw-pagmm-arXiv12,
  author = {Das, Aparna and Fleszar, Krzysztof and Kobourov, Stephen G. and Spoerhase, Joachim and Veeramoni, Sankar and Wolff, Alexander},
  howpublished = {Arxiv report},
  keywords = {networks},
  month = {apr},
  note = {Available at http://arxiv.org/abs/1203.6481},
  title = {Polylogarithmic Approximation for Generalized Minimum {Manhattan} Networks},
  year = 2012
}

Generalized Minimum {M}anhattan Networks Fleszar, Krzysztof (2012, May).

[ BibTeX ]

@misc{fleszar2012generalized,
  author = {Fleszar, Krzysztof},
  howpublished = {Master's thesis, Lehrstuhl f\"ur Informatik I, Universit\"at W\"urzburg},
  keywords = {networks},
  month = 5,
  school = {Lehrstuhl f\"ur Informatik I, Universit\"at W\"urzburg},
  title = {Generalized Minimum {M}anhattan Networks},
  type = {master's thesis},
  year = 2012
}

The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions Fleszar, Krzysztof; Gla{ss}er, Christian; Lipp, Fabian; Reitwie{ss}ner, Christian; Witek, Maximilian in Electronic Colloquium Computat. Complexity (ECCC) (2011). 18 53.

[ BibTeX ]
[ URL ]

@article{journals/eccc/FleszarGLRW11,
  author = {Fleszar, Krzysztof and Gla{\ss}er, Christian and Lipp, Fabian and Reitwie{\ss}ner, Christian and Witek, Maximilian},
  journal = {Electronic Colloquium Computat. Complexity (ECCC)},
  keywords = {optimization},
  pages = 53,
  title = {The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions},
  volume = 18,
  year = 2011
}

Complementation of Multihead Automata Fleszar, Krzysztof (2010, July).

[ Abstract ]
[ BibTeX ]

Since the proofs of Szelepscényi Szel87 and Immerman Imme88 it is known that nondeterministic space-bounded complexity classes are closed under complementation. Consequently this result is true for nondeterministic Turing machines bounded by logarithmic space, or equivalently for nondeterministic finite automata with two-way input heads. By utilizing the inductive counting technique Cook et al. showed that complementation holds also for LOGCFL, a complexity class that can be represented by nondeterministic finite pushdown automata bounded by polynomial time. This raises the question how the complementation of these automata is related to the increase of input heads of the complementing machine. The following results are evinced: 1. For every language L accepted by a nondeterministic finite automaton with k two-way input heads there exists a nondeterministic finite automaton with 8k+1 two-way input heads accepting the complement of L. 2. For every language L accepted by a nondeterministic pushdown automaton M with k two-way input heads working in time n^r there exists a nondeterministic pushdown automaton M′ with 18k+5r two-way input heads accepting the complement of L in time O(n^8k+2r).

@misc{fleszar2010complementation,
  abstract = {Since the proofs of Szelepscényi Szel87 and Immerman Imme88 it is known that nondeterministic space-bounded complexity classes are closed under complementation. Consequently this result is true for nondeterministic Turing machines bounded by logarithmic space, or equivalently for nondeterministic finite automata with two-way input heads. By utilizing the inductive counting technique Cook et al. showed that complementation holds also for LOGCFL, a complexity class that can be represented by nondeterministic finite pushdown automata bounded by polynomial time. This raises the question how the complementation of these automata is related to the increase of input heads of the complementing machine. The following results are evinced: 1. For every language L accepted by a nondeterministic finite automaton with k two-way input heads there exists a nondeterministic finite automaton with 8k+1 two-way input heads accepting the complement of L. 2. For every language L accepted by a nondeterministic pushdown automaton M with k two-way input heads working in time n^r there exists a nondeterministic pushdown automaton M\′ with 18k+5r two-way input heads accepting the complement of L in time O(n^8k+2r).},
  author = {Fleszar, Krzysztof},
  howpublished = {Bachelor thesis, Lehrstuhl f\"ur Informatik IV, Universit\"at W\"urzburg},
  keywords = {nondeterministic},
  month = {jul},
  school = {Lehrstuhl f\"ur Informatik IV, Universit\"at W\"urzburg},
  title = {Complementation of Multihead Automata},
  type = {bachelor thesis},
  year = 2010
}

Publications

MSc Krzysztof Fleszar

Address

Research

Short CV

Teaching

Data privacy protection

Data privacy protection

Picture credits