Westphal, Stephan

[["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","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","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"]]