TY - GEN A1 - Borndörfer, Ralf A1 - Elijazyfer, Ziena A1 - Schwartz, Stephan T1 - Approximating Balanced Graph Partitions N2 - We consider the problem of partitioning a weighted graph into k connected components of similar weight. In particular, we consider the two classical objectives to maximize the lightest part or to minimize the heaviest part. For a partitioning of the vertex set and for both objectives, we give the first known approximation results on general graphs. Specifically, we give a $\Delta$-approximation where $\Delta$ is the maximum degree of an arbitrary spanning tree of the given graph. Concerning the edge partition case, we even obtain a 2-approximation for the min-max and the max-min problem, by using the claw-freeness of line graphs. T3 - ZIB-Report - 19-25 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73675 SN - 1438-0064 ER - TY - THES A1 - Elijazyfer, Ziena T1 - Längenbeschränkte Teilgraphenbildung zur Maut-Kontrollstreckenoptimierung Y1 - 2018 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Arslan, Oytun A1 - Elijazyfer, Ziena A1 - Güler, Hakan A1 - Renken, Malte A1 - Sahin, Guvenc A1 - Schlechte, Thomas T1 - Line Planning on Path Networks with Application to the Istanbul Metrobüs T2 - Operations Research Proceedings 2016 N2 - Bus rapid transit systems in developing and newly industrialized countries often consist of a trunk with a path topology. On this trunk, several overlapping lines are operated which provide direct connections. The demand varies heavily over the day, with morning and afternoon peaks typically in reverse directions. We propose an integer programming model for this problem, derive a structural property of line plans in the static (or single period) ``unimodal demand'' case, and consider approaches to the solution of the multi-period version that rely on clustering the demand into peak and off-peak service periods. An application to the Metrobüs system of Istanbul is discussed. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-55702-1_32 SP - 235 EP - 241 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Arslan, Oytun A1 - Elijazyfer, Ziena A1 - Güler, Hakan A1 - Renken, Malte A1 - Sahin, Güvenc A1 - Schlechte, Thomas T1 - Line Planning on Path Networks with Application to the Istanbul Metrobüs N2 - Bus rapid transit systems in developing and newly industrialized countries often consist of a trunk with a path topology. On this trunk, several overlapping lines are operated which provide direct connections. The demand varies heavily over the day, with morning and afternoon peaks typically in reverse directions. We propose an integer programming model for this problem, derive a structural property of line plans in the static (or single period) ``unimodal demand'' case, and consider approaches to the solution of the multi-period version that rely on clustering the demand into peak and off-peak service periods. An application to the Metrobüs system of Istanbul is discussed. T3 - ZIB-Report - 16-38 KW - line planning KW - unimodal demand Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60119 SN - 1438-0064 ER -