Zobrazeno 1 - 10
of 37
pro vyhledávání: '"Tobias Mömke"'
Autor:
Tobias Mömke, Hang Zhou
Publikováno v:
Symposium on Simplicity in Algorithms (SOSA) ISBN: 9781611977585
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c13c48ada4f519f273cfc4802f434873
https://doi.org/10.1137/1.9781611977585.ch11
https://doi.org/10.1137/1.9781611977585.ch11
Publikováno v:
Algorithmica, 84 (5)
We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we identify a broad class of online problems for which the existence of a randomized online algorithm with constant expected
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8c4669c17d58bf701cd1ab87b78e7992
https://hdl.handle.net/20.500.11850/530894
https://hdl.handle.net/20.500.11850/530894
Publikováno v:
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Size and weight limitations of low-earth orbit (LEO) small satellites make their operation rest on a fine balance between solar power infeed and power demands of communication technologies on board, buffered by on-board battery storage. As a result,
Publikováno v:
Integer Programming and Combinatorial Optimization ISBN: 9783031069000
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0afb4af22644a51ecdafa7b36a849014
https://doi.org/10.1007/978-3-031-06901-7_9
https://doi.org/10.1007/978-3-031-06901-7_9
Autor:
Richard Královič, Sacha Krug, Tobias Mömke, Stefan Dobrev, Rastislav Královič, Dennis Komm, Jeff Edmonds
Publikováno v:
Theoretical Computer Science, 689
We study the advice complexity of an online version of the set cover problem. The goal is to quantify the information that online algorithms for this problem need to be supplied with to compute high-quality solutions and to overcome the drawback of n
Publikováno v:
Information and Computation. 254:59-83
We investigate to what extent the solution quality of online algorithms can be improved when supplying them with information about the input. To this end, we refine the recently introduced notion of advice complexity where the algorithm has access to
Autor:
Tobias Mömke, Ola Svensson
Publikováno v:
Journal of the ACM. 63:1-28
We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading
Autor:
Tobias Mömke
Publikováno v:
Information Processing Letters. 115:866-871
Given a complete edge-weighted graph G, we present a polynomial time algorithm to compute a degree-four-bounded spanning Eulerian subgraph of 2G that has at most 1.5 times the weight of an optimal TSP solution of G. Based on this algorithm and a nove