Westphal, Stephan

[["dc.bibliographiccitation.firstpage","343"],["dc.bibliographiccitation.issue","1"],["dc.bibliographiccitation.journal","Annals of Operations Research"],["dc.bibliographiccitation.lastpage","354"],["dc.bibliographiccitation.volume","239"],["dc.contributor.author","Goerigk, Marc"],["dc.contributor.author","Westphal, Stephan"],["dc.date.accessioned","2018-11-07T10:16:23Z"],["dc.date.available","2018-11-07T10:16:23Z"],["dc.date.issued","2016"],["dc.description.abstract","The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances."],["dc.identifier.doi","10.1007/s10479-014-1586-6"],["dc.identifier.isi","000373223800018"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/41029"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.publisher","Springer"],["dc.relation.issn","1572-9338"],["dc.relation.issn","0254-5330"],["dc.title","A combined local search and integer programming approach to the traveling tournament problem"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dc.type.status","published"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","87"],["dc.bibliographiccitation.issue","1"],["dc.bibliographiccitation.journal","Journal of Combinatorial Optimization"],["dc.bibliographiccitation.lastpage","96"],["dc.bibliographiccitation.volume","30"],["dc.contributor.author","Bender, Marco"],["dc.contributor.author","Westphal, Stephan"],["dc.date.accessioned","2018-11-07T09:55:30Z"],["dc.date.available","2018-11-07T09:55:30Z"],["dc.date.issued","2015"],["dc.description.abstract","We consider the -Canadian Traveller Problem, which asks for a shortest path between two nodes and in an undirected graph, where up to edges may be blocked. An online algorithm learns about a blocked edge when reaching one of its endpoints. Recently, it has been shown that no randomized online algorithm can be better than -competitive, even if all --paths are node-disjoint. We show that the bound is tight by constructing a randomized online algorithm for this case that achieves the ratio against an oblivious adversary and is therefore best possible."],["dc.description.sponsorship","DFG RTG [1703]"],["dc.identifier.doi","10.1007/s10878-013-9634-8"],["dc.identifier.isi","000355630900007"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/36754"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.publisher","Springer"],["dc.relation.issn","1573-2886"],["dc.relation.issn","1382-6905"],["dc.title","An optimal randomized online algorithm for the -Canadian Traveller Problem on node-disjoint paths"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dc.type.status","published"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","207"],["dc.bibliographiccitation.issue","2"],["dc.bibliographiccitation.journal","Mathematical Methods of Operations Research"],["dc.bibliographiccitation.lastpage","242"],["dc.bibliographiccitation.volume","83"],["dc.contributor.author","Thielen, Clemens"],["dc.contributor.author","Tiedemann, Morten"],["dc.contributor.author","Westphal, Stephan"],["dc.date.accessioned","2018-11-07T10:16:03Z"],["dc.date.available","2018-11-07T10:16:03Z"],["dc.date.issued","2016"],["dc.description.abstract","We consider an online knapsack problem with incremental capacity. In each time period, a set of items, each with a specific weight and value, is revealed and, without knowledge of future items, it has to be decided which of these items to accept. Additionally, the knapsack capacity is not fully available from the start but increases by a constant amount in each time period. The goal is to maximize the overall value of the accepted items. This setting extends the basic online knapsack problem by introducing a dynamic instead of a static knapsack capacity and is applicable to classic problems such as resource allocation or one-way trading. In contrast to the basic online knapsack problem, for which no competitive algorithms exist, the setting of incremental capacity facilitates the development of competitive algorithms for a bounded time horizon. We provide a competitive analysis of deterministic and randomized online algorithms for the online knapsack problem with incremental capacity and present lower bounds on the competitive ratio achievable by online algorithms for the problem. Most of these lower bounds match the competitive ratios achieved by our online algorithms exactly or differ only by a constant factor."],["dc.description.sponsorship","German Research Foundation (DFG) [GRK 1703/1]"],["dc.identifier.doi","10.1007/s00186-015-0526-9"],["dc.identifier.isi","000374577700003"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/40957"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.publisher","Springer"],["dc.publisher.place","Heidelberg"],["dc.relation.issn","1432-5217"],["dc.relation.issn","1432-2994"],["dc.title","The online knapsack problem with incremental capacity"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dc.type.status","published"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","35"],["dc.bibliographiccitation.issue","1"],["dc.bibliographiccitation.journal","4OR"],["dc.bibliographiccitation.lastpage","57"],["dc.bibliographiccitation.volume","13"],["dc.contributor.author","Ide, Jonas"],["dc.contributor.author","Tiedemann, Morten"],["dc.contributor.author","Westphal, Stephan"],["dc.contributor.author","Haiduk, Felix"],["dc.date.accessioned","2018-11-07T10:00:21Z"],["dc.date.available","2018-11-07T10:00:21Z"],["dc.date.issued","2015"],["dc.description.abstract","In the veneer cutting industry tree trunks are peeled into thin veneer strips which are cut, glued together, and pressed into bentwood pieces for seats, backrests, etc. In this work, a model for optimizing the inherent cutting problem with respect to resource efficiency is presented. Especially the heterogeneous quality of the wood renders existing models for classic cutting stock problems useless and calls for a new modeling approach. By means of the model presented in this paper, the problem is solved to optimality for real-world instances in reasonable time and applicable solutions are generated. Furthermore, in order to deal with uncertainties in the wood quality, the approach of robust optimization is applied to the problem. Robust optimization is an important tool to deal with uncertainties in the formulation of mathematical optimization models. Different concepts of robustness have been provided in the literature, one of which is the concept of minmax robust efficiency for uncertain multi-objective optimization problems. The concept of minmax robust efficiency is applied to a simplified version of the problem, robust efficient solutions are calculated, and the paper concludes with the discussion of the benefit of these solutions."],["dc.identifier.doi","10.1007/s10288-014-0265-4"],["dc.identifier.isi","000351136300003"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/37788"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.publisher","Springer"],["dc.publisher.place","Heidelberg"],["dc.relation.issn","1614-2411"],["dc.relation.issn","1619-4500"],["dc.title","An application of deterministic and robust optimization in the wood cutting industry"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dc.type.status","published"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","1836"],["dc.bibliographiccitation.issue","12"],["dc.bibliographiccitation.journal","Computers & Operations Research"],["dc.bibliographiccitation.lastpage","1844"],["dc.bibliographiccitation.volume","38"],["dc.contributor.author","Krumke, Sven O."],["dc.contributor.author","Thielen, Clemens"],["dc.contributor.author","Westphal, Stephan"],["dc.date.accessioned","2018-11-07T08:49:38Z"],["dc.date.available","2018-11-07T08:49:38Z"],["dc.date.issued","2011"],["dc.description.abstract","We consider the problem of scheduling n intervals (jobs with fixed starting times) on m machines with different speeds with the objective to maximize the number of accepted intervals. We prove that the offline version of the problem is strongly NP-hard to solve. For the online version, we show a lower bound of 5/3 on the competitive ratio of any deterministic online algorithm for the problem. Moreover, we present two simple greedy rules for online algorithms and show that any online algorithm using these rules is 2-competitive. One of these 2-competitive algorithms is shown to run in O(n logm) time. Additionally, we prove that our greedy rules impose no loss in the sense that every online algorithm for the problem can be modified to use the rules without reducing the number of accepted intervals on any instance. (C) 2011 Elsevier Ltd. All rights reserved."],["dc.identifier.doi","10.1016/j.cor.2011.03.001"],["dc.identifier.isi","000290932100018"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/21511"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.publisher","Pergamon-elsevier Science Ltd"],["dc.relation.issn","0305-0548"],["dc.title","Interval scheduling on related machines"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dc.type.status","published"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","1"],["dc.bibliographiccitation.journal","Journal of Cleaner Production"],["dc.bibliographiccitation.lastpage","8"],["dc.bibliographiccitation.volume","110"],["dc.contributor.author","Geldermann, Jutta"],["dc.contributor.author","Kolbe, Lutz M."],["dc.contributor.author","Krause, Andreas"],["dc.contributor.author","Mai, Carsten"],["dc.contributor.author","Militz, Holger"],["dc.contributor.author","Osburg, Victoria-Sophie"],["dc.contributor.author","Schobel, Anita"],["dc.contributor.author","Schumann, Matthias"],["dc.contributor.author","Toporowski, Waldemar"],["dc.contributor.author","Westphal, Stephan"],["dc.date.accessioned","2018-11-07T10:21:24Z"],["dc.date.available","2018-11-07T10:21:24Z"],["dc.date.issued","2016"],["dc.description.abstract","In light of various environmental problems and challenges concerning resource allocation, the utilisation of renewable resources is increasingly important for the efficient use of raw materials. Therefore, cascading utilisation (i.e., the multiple material utilisations of renewable resources prior to their conversion into energy) and approaches that aim to further increase resource efficiency (e.g., the utilisation of by-products) can be considered guiding principles. This paper therefore introduces the Special Volume \"Improved Resource Efficiency and Cascading Utilisation of Renewable Materials\". Because both research aspects, resource efficiency and cascading utilisation, belong to several disciplines, the Special Volume adopts an interdisciplinary perspective and presents 16 articles, which can be divided into four subjects: Innovative Materials based on Renewable Resources and their Impact on Sustainability and Resource Efficiency, Quantitative Models for the Integrated Optimisation of Production and Distribution in Networks for Renewable Resources, Information Technology-based Collaboration in Value Generating Networks for Renewable Resources, and Consumer Behaviour towards Eco-friendly Products. The interdisciplinary perspective allows a comprehensive overview of current research on resource efficiency, which is supplemented with 15 book reviews showing the extent to which textbooks of selected disciplines already refer to resource efficiency. This introductory article highlights the relevance of the four subjects, presents summaries of all papers, and discusses future research directions. The overall contribution of the Special Volume is that it bridges the resource efficiency research of selected disciplines and that it presents several approaches for more environmentally sound production and consumption. (C) 2015 Elsevier Ltd. All rights reserved."],["dc.identifier.doi","10.1016/j.jclepro.2015.09.092"],["dc.identifier.isi","000368203100001"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/42078"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.publisher","Elsevier Sci Ltd"],["dc.relation.issn","1879-1786"],["dc.relation.issn","0959-6526"],["dc.title","Improved resource efficiency and cascading utilisation of renewable materials"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dc.type.status","published"],["dc.type.subtype","letter_note"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","125"],["dc.bibliographiccitation.issue","2"],["dc.bibliographiccitation.journal","Networks"],["dc.bibliographiccitation.lastpage","131"],["dc.bibliographiccitation.volume","62"],["dc.contributor.author","Thielen, Clemens"],["dc.contributor.author","Westphal, Stephan"],["dc.date.accessioned","2018-11-07T09:21:00Z"],["dc.date.available","2018-11-07T09:21:00Z"],["dc.date.issued","2013"],["dc.description.abstract","We consider the maximum flow problem with minimum quantities (MFPMQ), which is a variant of the maximum flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound (a minimum quantity), which may depend on the arc. This problem has recently been shown to be weakly NP -complete even on series-parallel graphs. In this article, we provide further complexity and approximability results for MFPMQ and several special cases. We first show that it is strongly NP -hard to approximate MFPMQ on general graphs (and even bipartite graphs) within any positive factor. On series-parallel graphs, however, we present a pseudo-polynomial time dynamic programming algorithm for the problem. We then study the case that the minimum quantity is the same for each arc in the network and show that, under this restriction, the problem is still weakly NP -complete on general graphs, but can be solved in strongly polynomial time on series-parallel graphs. On general graphs, we present a (2 - 1/lambda)-approximation algorithm for this case, where lambda denotes the common minimum quantity of all arcs. (c) 2013 Wiley Periodicals, Inc."],["dc.identifier.doi","10.1002/net.21502"],["dc.identifier.isi","000322920500004"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/29010"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.publisher","Wiley-blackwell"],["dc.relation.issn","0028-3045"],["dc.title","Complexity and approximability of the maximum flow problem with minimum quantities"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dc.type.status","published"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","1"],["dc.bibliographiccitation.issue","1"],["dc.bibliographiccitation.journal","Mathematical Methods of Operations Research"],["dc.bibliographiccitation.lastpage","20"],["dc.bibliographiccitation.volume","76"],["dc.contributor.author","Thielen, Clemens"],["dc.contributor.author","Westphal, Stephan"],["dc.date.accessioned","2018-11-07T09:08:05Z"],["dc.date.available","2018-11-07T09:08:05Z"],["dc.date.issued","2012"],["dc.description.abstract","We consider the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. It consists of designing a schedule for a sports league of n teams such that the total traveling costs of the teams are minimized. The most important variant of the traveling tournament problem imposes restrictions on the number of consecutive home games or away games a team may have. We consider the case where at most two consecutive home games or away games are allowed. We show that the well-known independent lower bound for this case cannot be reached and present two approximation algorithms for the problem. The first algorithm has an approximation ratio of in the case that n/2 is odd, and of in the case that n/2 is even. Furthermore, we show that this algorithm is applicable to real world problems as it yields close to optimal tournaments for many standard benchmark instances. The second algorithm we propose is only suitable for the case that n/2 is even and n a parts per thousand yen 12, and achieves an approximation ratio of 1 + 16/n in this case, which makes it the first -approximation for the problem."],["dc.identifier.doi","10.1007/s00186-012-0387-4"],["dc.identifier.isi","000305960500001"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/25944"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.publisher","Springer"],["dc.publisher.place","Heidelberg"],["dc.relation.issn","1432-2994"],["dc.title","Approximation algorithms for TTP(2)"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dc.type.status","published"],["dspace.entity.type","Publication"]]