[{"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1611.06500"}],"external_id":{"arxiv":["1611.06500"]},"arxiv":1,"author":[{"first_name":"Gramoz","full_name":"Goranci, Gramoz","last_name":"Goranci"},{"last_name":"Henzinger","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"last_name":"Thorup","full_name":"Thorup, Mikkel","first_name":"Mikkel"}],"intvolume":"        14","publication_status":"published","oa_version":"Preprint","article_type":"original","article_number":"17","year":"2018","quality_controlled":"1","issue":"2","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","month":"04","volume":14,"language":[{"iso":"eng"}],"doi":"10.1145/3174803","citation":{"ama":"Goranci G, Henzinger M, Thorup M. Incremental exact min-cut in polylogarithmic amortized update time. <i>ACM Transactions on Algorithms</i>. 2018;14(2). doi:<a href=\"https://doi.org/10.1145/3174803\">10.1145/3174803</a>","ista":"Goranci G, Henzinger M, Thorup M. 2018. Incremental exact min-cut in polylogarithmic amortized update time. ACM Transactions on Algorithms. 14(2), 17.","apa":"Goranci, G., Henzinger, M., &#38; Thorup, M. (2018). Incremental exact min-cut in polylogarithmic amortized update time. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3174803\">https://doi.org/10.1145/3174803</a>","chicago":"Goranci, Gramoz, Monika Henzinger, and Mikkel Thorup. “Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2018. <a href=\"https://doi.org/10.1145/3174803\">https://doi.org/10.1145/3174803</a>.","ieee":"G. Goranci, M. Henzinger, and M. Thorup, “Incremental exact min-cut in polylogarithmic amortized update time,” <i>ACM Transactions on Algorithms</i>, vol. 14, no. 2. Association for Computing Machinery, 2018.","mla":"Goranci, Gramoz, et al. “Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time.” <i>ACM Transactions on Algorithms</i>, vol. 14, no. 2, 17, Association for Computing Machinery, 2018, doi:<a href=\"https://doi.org/10.1145/3174803\">10.1145/3174803</a>.","short":"G. Goranci, M. Henzinger, M. Thorup, ACM Transactions on Algorithms 14 (2018)."},"date_updated":"2024-11-06T12:05:51Z","abstract":[{"lang":"eng","text":"We present a deterministic incremental algorithm for exactly maintaining the size of a minimum cut with O(log3 n log log2 n) amortized time per edge insertion and O(1) query time. This result partially answers an open question posed by Thorup (2007). It also stays in sharp contrast to a polynomial conditional lower bound for the fully dynamic weighted minimum cut problem. Our algorithm is obtained by combining a sparsification technique of Kawarabayashi and Thorup (2015) or its recent improvement by Henzinger, Rao, and Wang (2017), and an exact incremental algorithm of Henzinger (1997).\r\n\r\nWe also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an O(nlog n/ε2) space Monte Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a (1+ε)-approximation to the minimum cut. The algorithm has O((α (n) log3 n)/ε 2) amortized update time and constant query time, where α (n) stands for the inverse of Ackermann function."}],"publication_identifier":{"issn":["1549-6325"],"eissn":["1549-6333"]},"date_created":"2022-07-27T11:29:39Z","oa":1,"_id":"11664","publisher":"Association for Computing Machinery","day":"01","article_processing_charge":"No","status":"public","acknowledgement":"We thank the two anonymous reviewers for their suggestions and comments, which improved the\r\nquality of the article.","type":"journal_article","scopus_import":"1","publication":"ACM Transactions on Algorithms","date_published":"2018-04-01T00:00:00Z","title":"Incremental exact min-cut in polylogarithmic amortized update time"},{"extern":"1","keyword":["Theory of computation","Algorithmic game theory and mechanism design","Applied computing","Economics","Simplified mechanisms","Combinatorial auctions with item bidding","Price of anarchy"],"month":"05","issue":"2","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","year":"2018","article_number":"5","article_type":"original","oa_version":"Preprint","publication_status":"published","intvolume":"         6","arxiv":1,"author":[{"full_name":"Dütting, Paul","first_name":"Paul","last_name":"Dütting"},{"full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"full_name":"Starnberger, Martin","first_name":"Martin","last_name":"Starnberger"}],"main_file_link":[{"url":"https://arxiv.org/abs/1310.3153","open_access":"1"}],"external_id":{"arxiv":["1310.3153"]},"title":"Valuation compressions in VCG-based combinatorial auctions","date_published":"2018-05-01T00:00:00Z","publication":"ACM Transactions on Economics and Computation","scopus_import":"1","type":"journal_article","article_processing_charge":"No","status":"public","_id":"11667","day":"01","publisher":"Association for Computing Machinery","oa":1,"date_created":"2022-07-27T11:46:46Z","publication_identifier":{"issn":["2167-8375"],"eissn":["2167-8383"]},"date_updated":"2024-11-06T12:06:28Z","abstract":[{"text":"The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions, the truthful direct-revelation mechanism that maximizes social welfare is the Vickrey-Clarke-Groves mechanism. For many valuation spaces, computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that increased expressiveness can give rise to additional equilibria of poorer efficiency.","lang":"eng"}],"doi":"10.1145/3232860","citation":{"apa":"Dütting, P., Henzinger, M., &#38; Starnberger, M. (2018). Valuation compressions in VCG-based combinatorial auctions. <i>ACM Transactions on Economics and Computation</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3232860\">https://doi.org/10.1145/3232860</a>","chicago":"Dütting, Paul, Monika Henzinger, and Martin Starnberger. “Valuation Compressions in VCG-Based Combinatorial Auctions.” <i>ACM Transactions on Economics and Computation</i>. Association for Computing Machinery, 2018. <a href=\"https://doi.org/10.1145/3232860\">https://doi.org/10.1145/3232860</a>.","ama":"Dütting P, Henzinger M, Starnberger M. Valuation compressions in VCG-based combinatorial auctions. <i>ACM Transactions on Economics and Computation</i>. 2018;6(2). doi:<a href=\"https://doi.org/10.1145/3232860\">10.1145/3232860</a>","ista":"Dütting P, Henzinger M, Starnberger M. 2018. Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. 6(2), 5.","ieee":"P. Dütting, M. Henzinger, and M. Starnberger, “Valuation compressions in VCG-based combinatorial auctions,” <i>ACM Transactions on Economics and Computation</i>, vol. 6, no. 2. Association for Computing Machinery, 2018.","mla":"Dütting, Paul, et al. “Valuation Compressions in VCG-Based Combinatorial Auctions.” <i>ACM Transactions on Economics and Computation</i>, vol. 6, no. 2, 5, Association for Computing Machinery, 2018, doi:<a href=\"https://doi.org/10.1145/3232860\">10.1145/3232860</a>.","short":"P. Dütting, M. Henzinger, M. Starnberger, ACM Transactions on Economics and Computation 6 (2018)."},"volume":6,"language":[{"iso":"eng"}]},{"title":"Dynamic algorithms via the primal-dual method","scopus_import":"1","type":"journal_article","date_published":"2018-08-01T00:00:00Z","publication":"Information and Computation","publisher":"Elsevier","day":"01","_id":"11757","date_created":"2022-08-08T11:20:03Z","oa":1,"status":"public","article_processing_charge":"No","doi":"10.1016/j.ic.2018.02.005","citation":{"ieee":"S. Bhattacharya, M. Henzinger, and G. Italiano, “Dynamic algorithms via the primal-dual method,” <i>Information and Computation</i>, vol. 261, no. 08. Elsevier, pp. 219–239, 2018.","ama":"Bhattacharya S, Henzinger M, Italiano G. Dynamic algorithms via the primal-dual method. <i>Information and Computation</i>. 2018;261(08):219-239. doi:<a href=\"https://doi.org/10.1016/j.ic.2018.02.005\">10.1016/j.ic.2018.02.005</a>","ista":"Bhattacharya S, Henzinger M, Italiano G. 2018. Dynamic algorithms via the primal-dual method. Information and Computation. 261(08), 219–239.","chicago":"Bhattacharya, Sayan, Monika Henzinger, and Giuseppe Italiano. “Dynamic Algorithms via the Primal-Dual Method.” <i>Information and Computation</i>. Elsevier, 2018. <a href=\"https://doi.org/10.1016/j.ic.2018.02.005\">https://doi.org/10.1016/j.ic.2018.02.005</a>.","apa":"Bhattacharya, S., Henzinger, M., &#38; Italiano, G. (2018). Dynamic algorithms via the primal-dual method. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2018.02.005\">https://doi.org/10.1016/j.ic.2018.02.005</a>","short":"S. Bhattacharya, M. Henzinger, G. Italiano, Information and Computation 261 (2018) 219–239.","mla":"Bhattacharya, Sayan, et al. “Dynamic Algorithms via the Primal-Dual Method.” <i>Information and Computation</i>, vol. 261, no. 08, Elsevier, 2018, pp. 219–39, doi:<a href=\"https://doi.org/10.1016/j.ic.2018.02.005\">10.1016/j.ic.2018.02.005</a>."},"language":[{"iso":"eng"}],"volume":261,"publication_identifier":{"issn":["0890-5401"]},"abstract":[{"text":"We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an O ( f 2)-approximately optimal solution in O ( f · log(m + n)) amortized update time, where f is the maximum “frequency” of an element, n is the number of sets, and m is the maximum number of elements in the universe at any point in time. (2) For the dynamic b-matching problem, we maintain an O (1)-approximately optimal solution in O (log3 n) amortized update time, where n is the number of nodes in the graph.","lang":"eng"}],"date_updated":"2024-11-06T08:13:33Z","quality_controlled":"1","year":"2018","month":"08","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"08","article_type":"original","publication_status":"published","page":"219-239","oa_version":"Published Version","author":[{"full_name":"Bhattacharya, Sayan","first_name":"Sayan","last_name":"Bhattacharya"},{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Italiano, Giuseppe","first_name":"Giuseppe","last_name":"Italiano"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1016/j.ic.2018.02.005"}],"intvolume":"       261"},{"year":"2018","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"6","month":"12","extern":"1","article_type":"original","page":"1-40","publication_status":"published","oa_version":"Preprint","external_id":{"arxiv":["1512.08148"]},"main_file_link":[{"url":"https://arxiv.org/abs/1512.08148","open_access":"1"}],"author":[{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"full_name":"Krinninger, Sebastian","first_name":"Sebastian","last_name":"Krinninger"},{"full_name":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"}],"arxiv":1,"intvolume":"        65","title":"Decremental single-source shortest paths on undirected graphs in near-linear total update time","type":"journal_article","scopus_import":"1","related_material":{"record":[{"relation":"earlier_version","id":"11855","status":"public"}]},"publication":"Journal of the ACM","date_published":"2018-12-01T00:00:00Z","date_created":"2022-08-08T12:33:17Z","oa":1,"publisher":"Association for Computing Machinery","day":"01","_id":"11768","status":"public","article_processing_charge":"No","language":[{"iso":"eng"}],"volume":65,"citation":{"ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source shortest paths on undirected graphs in near-linear total update time,” <i>Journal of the ACM</i>, vol. 65, no. 6. Association for Computing Machinery, pp. 1–40, 2018.","ista":"Henzinger M, Krinninger S, Nanongkai D. 2018. Decremental single-source shortest paths on undirected graphs in near-linear total update time. Journal of the ACM. 65(6), 1–40.","ama":"Henzinger M, Krinninger S, Nanongkai D. Decremental single-source shortest paths on undirected graphs in near-linear total update time. <i>Journal of the ACM</i>. 2018;65(6):1-40. doi:<a href=\"https://doi.org/10.1145/3218657\">10.1145/3218657</a>","chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” <i>Journal of the ACM</i>. Association for Computing Machinery, 2018. <a href=\"https://doi.org/10.1145/3218657\">https://doi.org/10.1145/3218657</a>.","apa":"Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2018). Decremental single-source shortest paths on undirected graphs in near-linear total update time. <i>Journal of the ACM</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3218657\">https://doi.org/10.1145/3218657</a>","short":"M. Henzinger, S. Krinninger, D. Nanongkai, Journal of the ACM 65 (2018) 1–40.","mla":"Henzinger, Monika, et al. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” <i>Journal of the ACM</i>, vol. 65, no. 6, Association for Computing Machinery, 2018, pp. 1–40, doi:<a href=\"https://doi.org/10.1145/3218657\">10.1145/3218657</a>."},"doi":"10.1145/3218657","abstract":[{"text":"In the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1+ϵ)-approximation factor, the running time was recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1+ϵ)-approximation algorithm with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover, we obtain m1+o(1) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn) time is the mn0.9 + o(1)-time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary.\r\n\r\nIn contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, ϵ)-hop set introduced by Cohen [12] in the PRAM literature. An (h, ϵ)-hop set of a graph G=(V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1+ϵ)-approximated by their h-hop distance (given by a path containing at most h edges) on G′=(V, E ∪ F). Our algorithm can maintain an (no(1), ϵ)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools might be of independent interest.","lang":"eng"}],"date_updated":"2024-11-06T12:18:17Z","publication_identifier":{"issn":["0004-5411"],"eissn":["1557-735X"]}},{"type":"conference","scopus_import":"1","publication":"26th Annual European Symposium on Algorithms","date_published":"2018-08-14T00:00:00Z","title":"A tree structure for dynamic facility location","language":[{"iso":"eng"}],"volume":112,"citation":{"ieee":"G. Goranci, M. Henzinger, and D. Leniowski, “A tree structure for dynamic facility location,” in <i>26th Annual European Symposium on Algorithms</i>, Helsinki, Finland, 2018, vol. 112.","apa":"Goranci, G., Henzinger, M., &#38; Leniowski, D. (2018). A tree structure for dynamic facility location. In <i>26th Annual European Symposium on Algorithms</i> (Vol. 112). Helsinki, Finland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.39\">https://doi.org/10.4230/LIPICS.ESA.2018.39</a>","chicago":"Goranci, Gramoz , Monika Henzinger, and Dariusz Leniowski. “A Tree Structure for Dynamic Facility Location.” In <i>26th Annual European Symposium on Algorithms</i>, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.39\">https://doi.org/10.4230/LIPICS.ESA.2018.39</a>.","ama":"Goranci G, Henzinger M, Leniowski D. A tree structure for dynamic facility location. In: <i>26th Annual European Symposium on Algorithms</i>. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.39\">10.4230/LIPICS.ESA.2018.39</a>","ista":"Goranci G, Henzinger M, Leniowski D. 2018. A tree structure for dynamic facility location. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 39.","short":"G. Goranci, M. Henzinger, D. Leniowski, in:, 26th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","mla":"Goranci, Gramoz, et al. “A Tree Structure for Dynamic Facility Location.” <i>26th Annual European Symposium on Algorithms</i>, vol. 112, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.39\">10.4230/LIPICS.ESA.2018.39</a>."},"doi":"10.4230/LIPICS.ESA.2018.39","abstract":[{"text":"We study the metric facility location problem with client insertions and deletions. This setting differs from the classic dynamic facility location problem, where the set of clients remains the same, but the metric space can change over time. We show a deterministic algorithm that maintains a constant factor approximation to the optimal solution in worst-case time O~(2^{O(kappa^2)}) per client insertion or deletion in metric spaces while answering queries about the cost in O(1) time, where kappa denotes the doubling dimension of the metric. For metric spaces with bounded doubling dimension, the update time is polylogarithmic in the parameters of the problem.","lang":"eng"}],"date_updated":"2024-11-06T11:57:41Z","publication_identifier":{"isbn":["9783959770811"],"issn":["1868-8969"]},"oa":1,"date_created":"2022-08-12T08:20:57Z","day":"14","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"11827","status":"public","article_processing_charge":"No","alternative_title":["LIPIcs"],"conference":{"start_date":"2018-08-20","location":"Helsinki, Finland","name":"ESA: Annual European Symposium on Algorithms","end_date":"2018-08-22"},"article_number":"39","year":"2018","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"08","extern":"1","external_id":{"arxiv":["1909.06653"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2018.39"}],"author":[{"last_name":"Goranci","full_name":"Goranci, Gramoz ","first_name":"Gramoz "},{"last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Dariusz","full_name":"Leniowski, Dariusz","last_name":"Leniowski"}],"arxiv":1,"intvolume":"       112","publication_status":"published","oa_version":"Published Version"},{"date_created":"2022-08-12T08:26:42Z","oa":1,"corr_author":"1","_id":"11828","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","day":"14","article_processing_charge":"No","status":"public","language":[{"iso":"eng"}],"volume":112,"citation":{"ieee":"G. Goranci, M. Henzinger, and P. Peng, “Dynamic effective resistances and approximate schur complement on separable graphs,” in <i>26th Annual European Symposium on Algorithms</i>, Helsinki, Finland, 2018, vol. 112.","ama":"Goranci G, Henzinger M, Peng P. Dynamic effective resistances and approximate schur complement on separable graphs. In: <i>26th Annual European Symposium on Algorithms</i>. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.40\">10.4230/LIPICS.ESA.2018.40</a>","ista":"Goranci G, Henzinger M, Peng P. 2018. Dynamic effective resistances and approximate schur complement on separable graphs. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 40.","apa":"Goranci, G., Henzinger, M., &#38; Peng, P. (2018). Dynamic effective resistances and approximate schur complement on separable graphs. In <i>26th Annual European Symposium on Algorithms</i> (Vol. 112). Helsinki, Finland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.40\">https://doi.org/10.4230/LIPICS.ESA.2018.40</a>","chicago":"Goranci, Gramoz, Monika Henzinger, and Pan Peng. “Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.” In <i>26th Annual European Symposium on Algorithms</i>, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.40\">https://doi.org/10.4230/LIPICS.ESA.2018.40</a>.","short":"G. Goranci, M. Henzinger, P. Peng, in:, 26th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","mla":"Goranci, Gramoz, et al. “Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.” <i>26th Annual European Symposium on Algorithms</i>, vol. 112, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2018.40\">10.4230/LIPICS.ESA.2018.40</a>."},"doi":"10.4230/LIPICS.ESA.2018.40","date_updated":"2024-11-06T12:16:31Z","abstract":[{"text":"We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an n^{c}-separator theorem for some c<1. We give a fully dynamic algorithm that maintains (1+epsilon)-approximations of the all-pairs effective resistances of an n-vertex graph G undergoing edge insertions and deletions with O~(sqrt{n}/epsilon^2) worst-case update time and O~(sqrt{n}/epsilon^2) worst-case query time, if G is guaranteed to be sqrt{n}-separable (i.e., it is taken from a class satisfying a sqrt{n}-separator theorem) and its separator can be computed in O~(n) time. Our algorithm is built upon a dynamic algorithm for maintaining approximate Schur complement that approximately preserves pairwise effective resistances among a set of terminals for separable graphs, which might be of independent interest.\r\nWe complement our result by proving that for any two fixed vertices s and t, no incremental or decremental algorithm can maintain the s-t effective resistance for sqrt{n}-separable graphs with worst-case update time O(n^{1/2-delta}) and query time O(n^{1-delta}) for any delta>0, unless the Online Matrix Vector Multiplication (OMv) conjecture is false.\r\nWe further show that for general graphs, no incremental or decremental algorithm can maintain the s-t effective resistance problem with worst-case update time O(n^{1-delta}) and query-time O(n^{2-delta}) for any delta >0, unless the OMv conjecture is false.","lang":"eng"}],"publication_identifier":{"isbn":["9783959770811"],"issn":["1868-8969"]},"title":"Dynamic effective resistances and approximate schur complement on separable graphs","type":"conference","scopus_import":"1","publication":"26th Annual European Symposium on Algorithms","date_published":"2018-08-14T00:00:00Z","publication_status":"published","oa_version":"Published Version","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2018.40","open_access":"1"}],"external_id":{"arxiv":["1802.09111"]},"arxiv":1,"author":[{"last_name":"Goranci","full_name":"Goranci, Gramoz","first_name":"Gramoz"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"full_name":"Peng, Pan","first_name":"Pan","last_name":"Peng"}],"intvolume":"       112","year":"2018","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","month":"08","alternative_title":["LIPIcs"],"conference":{"end_date":"2018-08-22","name":"ESA: Annual European Symposium on Algorithms","start_date":"2018-08-20","location":"Helsinki, Finland"},"article_number":"40"},{"title":"Dynamic algorithms for graph coloring","scopus_import":"1","type":"conference","date_published":"2018-01-01T00:00:00Z","publication":"29th Annual ACM-SIAM Symposium on Discrete Algorithms","publisher":"Society for Industrial and Applied Mathematics","day":"01","_id":"11872","date_created":"2022-08-16T12:07:14Z","oa":1,"status":"public","article_processing_charge":"No","citation":{"short":"S. Bhattacharya, D. Chakrabarty, M. Henzinger, D. Nanongkai, in:, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2018, pp. 1–20.","mla":"Bhattacharya, Sayan, et al. “Dynamic Algorithms for Graph Coloring.” <i>29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2018, pp. 1–20, doi:<a href=\"https://doi.org/10.1137/1.9781611975031.1\">10.1137/1.9781611975031.1</a>.","ieee":"S. Bhattacharya, D. Chakrabarty, M. Henzinger, and D. Nanongkai, “Dynamic algorithms for graph coloring,” in <i>29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, New Orleans, LA, United States, 2018, pp. 1–20.","chicago":"Bhattacharya, Sayan, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. “Dynamic Algorithms for Graph Coloring.” In <i>29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 1–20. Society for Industrial and Applied Mathematics, 2018. <a href=\"https://doi.org/10.1137/1.9781611975031.1\">https://doi.org/10.1137/1.9781611975031.1</a>.","apa":"Bhattacharya, S., Chakrabarty, D., Henzinger, M., &#38; Nanongkai, D. (2018). Dynamic algorithms for graph coloring. In <i>29th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 1–20). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611975031.1\">https://doi.org/10.1137/1.9781611975031.1</a>","ista":"Bhattacharya S, Chakrabarty D, Henzinger M, Nanongkai D. 2018. Dynamic algorithms for graph coloring. 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1–20.","ama":"Bhattacharya S, Chakrabarty D, Henzinger M, Nanongkai D. Dynamic algorithms for graph coloring. In: <i>29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2018:1-20. doi:<a href=\"https://doi.org/10.1137/1.9781611975031.1\">10.1137/1.9781611975031.1</a>"},"doi":"10.1137/1.9781611975031.1","language":[{"iso":"eng"}],"publication_identifier":{"eisbn":["978-161197503-1"]},"abstract":[{"lang":"eng","text":"We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algorithms for (Δ + 1)- vertex coloring and (2Δ – 1)-edge coloring in a graph with maximum degree Δ. It is natural to ask if we can efficiently maintain such colorings in the dynamic setting as well. We get the following three results. (1) We present a randomized algorithm which maintains a (Δ + 1)-vertex coloring with O(log Δ) expected amortized update time. (2) We present a deterministic algorithm which maintains a (1 + o(1)Δ-vertex coloring with O(polylog Δ) amortized update time. (3) We present a simple, deterministic algorithm which maintains a (2Δ – 1)-edge coloring with O(log Δ) worst-case update time. This improves the recent O(Δ)-edge coloring algorithm with  worst-case update time [4]."}],"date_updated":"2024-11-06T12:20:35Z","quality_controlled":"1","year":"2018","month":"01","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"name":"SODA: Symposium on Discrete Algorithms","location":"New Orleans, LA, United States","start_date":"2018-01-07","end_date":"2018-01-10"},"publication_status":"published","page":"1 - 20","oa_version":"Preprint","author":[{"last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan","first_name":"Sayan"},{"last_name":"Chakrabarty","first_name":"Deeparnab","full_name":"Chakrabarty, Deeparnab"},{"full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"first_name":"Danupon","full_name":"Nanongkai, Danupon","last_name":"Nanongkai"}],"arxiv":1,"external_id":{"arxiv":["1711.04355"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1711.04355"}]},{"year":"2018","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"01","extern":"1","conference":{"name":"ALENEX: Symposium on Algorithm Engineering and Experiments","location":"New Orleans, LA, United States","start_date":"2018-01-07","end_date":"2018-01-08"},"page":"48-61","publication_status":"published","oa_version":"Preprint","external_id":{"arxiv":["1708.06127"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.06127"}],"author":[{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Alexander","full_name":"Noe, Alexander","last_name":"Noe"},{"last_name":"Schulz","full_name":"Schulz, Christian","first_name":"Christian"},{"last_name":"Strash","full_name":"Strash, Darren","first_name":"Darren"}],"arxiv":1,"title":"Practical minimum cut algorithms","type":"conference","scopus_import":"1","publication":"20th Workshop on Algorithm Engineering and Experiments","date_published":"2018-01-01T00:00:00Z","oa":1,"date_created":"2022-08-17T07:04:57Z","publisher":"Society for Industrial and Applied Mathematics","day":"01","_id":"11882","status":"public","article_processing_charge":"No","language":[{"iso":"eng"}],"doi":"10.1137/1.9781611975055.5","citation":{"ista":"Henzinger M, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. 20th Workshop on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 48–61.","ama":"Henzinger M, Noe A, Schulz C, Strash D. Practical minimum cut algorithms. In: <i>20th Workshop on Algorithm Engineering and Experiments</i>. Society for Industrial and Applied Mathematics; 2018:48-61. doi:<a href=\"https://doi.org/10.1137/1.9781611975055.5\">10.1137/1.9781611975055.5</a>","apa":"Henzinger, M., Noe, A., Schulz, C., &#38; Strash, D. (2018). Practical minimum cut algorithms. In <i>20th Workshop on Algorithm Engineering and Experiments</i> (pp. 48–61). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611975055.5\">https://doi.org/10.1137/1.9781611975055.5</a>","chicago":"Henzinger, Monika, Alexander Noe, Christian Schulz, and Darren Strash. “Practical Minimum Cut Algorithms.” In <i>20th Workshop on Algorithm Engineering and Experiments</i>, 48–61. Society for Industrial and Applied Mathematics, 2018. <a href=\"https://doi.org/10.1137/1.9781611975055.5\">https://doi.org/10.1137/1.9781611975055.5</a>.","ieee":"M. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,” in <i>20th Workshop on Algorithm Engineering and Experiments</i>, New Orleans, LA, United States, 2018, pp. 48–61.","mla":"Henzinger, Monika, et al. “Practical Minimum Cut Algorithms.” <i>20th Workshop on Algorithm Engineering and Experiments</i>, Society for Industrial and Applied Mathematics, 2018, pp. 48–61, doi:<a href=\"https://doi.org/10.1137/1.9781611975055.5\">10.1137/1.9781611975055.5</a>.","short":"M. Henzinger, A. Noe, C. Schulz, D. Strash, in:, 20th Workshop on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2018, pp. 48–61."},"abstract":[{"text":"The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi's contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm shows good scalability.","lang":"eng"}],"date_updated":"2024-11-06T12:22:09Z","publication_identifier":{"eisbn":["978-1-61197-505-5"]}},{"article_type":"original","quality_controlled":"1","year":"2018","extern":"1","month":"05","issue":"3","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"author":[{"last_name":"Bhattacharya","first_name":"Sayan","full_name":"Bhattacharya, Sayan"},{"last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"first_name":"Giuseppe F.","full_name":"Italiano, Giuseppe F.","last_name":"Italiano"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1412.1318"}],"external_id":{"arxiv":["1412.1318"]},"intvolume":"        47","publication_status":"published","page":"859-887","oa_version":"Preprint","scopus_import":"1","related_material":{"record":[{"id":"11875","relation":"earlier_version","status":"public"}]},"type":"journal_article","date_published":"2018-05-01T00:00:00Z","publication":"SIAM Journal on Computing","title":"Deterministic fully dynamic data structures for vertex cover and matching","doi":"10.1137/140998925","citation":{"ista":"Bhattacharya S, Henzinger M, Italiano GF. 2018. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 47(3), 859–887.","ama":"Bhattacharya S, Henzinger M, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. <i>SIAM Journal on Computing</i>. 2018;47(3):859-887. doi:<a href=\"https://doi.org/10.1137/140998925\">10.1137/140998925</a>","apa":"Bhattacharya, S., Henzinger, M., &#38; Italiano, G. F. (2018). Deterministic fully dynamic data structures for vertex cover and matching. <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/140998925\">https://doi.org/10.1137/140998925</a>","chicago":"Bhattacharya, Sayan, Monika Henzinger, and Giuseppe F. Italiano. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics, 2018. <a href=\"https://doi.org/10.1137/140998925\">https://doi.org/10.1137/140998925</a>.","ieee":"S. Bhattacharya, M. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” <i>SIAM Journal on Computing</i>, vol. 47, no. 3. Society for Industrial &#38; Applied Mathematics, pp. 859–887, 2018.","mla":"Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” <i>SIAM Journal on Computing</i>, vol. 47, no. 3, Society for Industrial &#38; Applied Mathematics, 2018, pp. 859–87, doi:<a href=\"https://doi.org/10.1137/140998925\">10.1137/140998925</a>.","short":"S. Bhattacharya, M. Henzinger, G.F. Italiano, SIAM Journal on Computing 47 (2018) 859–887."},"language":[{"iso":"eng"}],"volume":47,"publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"date_updated":"2024-11-06T12:22:54Z","abstract":[{"lang":"eng","text":"We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph 𝐺=(𝑉,𝐸), with |𝑉|=𝑛 and |𝐸|=𝑚, in 𝑜(𝑚‾‾√) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+𝜖) approximation in 𝑂(log𝑛/𝜖2) amortized time per update. For maximum matching, we show how to maintain a (3+𝜖) approximation in 𝑂(min(𝑛√/𝜖,𝑚1/3/𝜖2) amortized time per update and a (4+𝜖) approximation in 𝑂(𝑚1/3/𝜖2) worst-case time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457--464]."}],"_id":"11890","day":"01","publisher":"Society for Industrial & Applied Mathematics","date_created":"2022-08-17T08:21:23Z","oa":1,"article_processing_charge":"No","status":"public"},{"article_number":"3","conference":{"name":"SEA: Symposium on Experimental Algorithms","location":"L'Aquila, Italy","start_date":"2018-07-27","end_date":"2018-07-29"},"alternative_title":["LIPIcs"],"month":"07","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","year":"2018","intvolume":"       103","author":[{"last_name":"Biedermann","first_name":"Sonja","full_name":"Biedermann, Sonja"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"last_name":"Schulz","full_name":"Schulz, Christian","first_name":"Christian"},{"last_name":"Schuster","first_name":"Bernhard","full_name":"Schuster, Bernhard"}],"arxiv":1,"external_id":{"arxiv":["1802.07034"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPICS.SEA.2018.3"}],"oa_version":"Published Version","publication_status":"published","date_published":"2018-07-01T00:00:00Z","publication":"17th International Symposium on Experimental Algorithms","scopus_import":"1","type":"conference","title":"Memetic graph clustering","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959770705"]},"abstract":[{"lang":"eng","text":"It is common knowledge that there is no single best strategy for graph clustering, which justifies a plethora of existing approaches. In this paper, we present a general memetic algorithm, VieClus, to tackle the graph clustering problem. This algorithm can be adapted to optimize different objective functions. A key component of our contribution are natural recombine operators that employ ensemble clusterings as well as multi-level techniques. Lastly, we combine these techniques with a scalable communication protocol, producing a system that is able to compute high-quality solutions in a short amount of time. We instantiate our scheme with local search for modularity and show that our algorithm successfully improves or reproduces all entries of the 10th DIMACS implementation challenge under consideration using a small amount of time."}],"date_updated":"2024-11-06T11:57:15Z","citation":{"mla":"Biedermann, Sonja, et al. “Memetic Graph Clustering.” <i>17th International Symposium on Experimental Algorithms</i>, vol. 103, 3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPICS.SEA.2018.3\">10.4230/LIPICS.SEA.2018.3</a>.","short":"S. Biedermann, M. Henzinger, C. Schulz, B. Schuster, in:, 17th International Symposium on Experimental Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","ama":"Biedermann S, Henzinger M, Schulz C, Schuster B. Memetic graph clustering. In: <i>17th International Symposium on Experimental Algorithms</i>. Vol 103. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPICS.SEA.2018.3\">10.4230/LIPICS.SEA.2018.3</a>","ista":"Biedermann S, Henzinger M, Schulz C, Schuster B. 2018. Memetic graph clustering. 17th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 103, 3.","chicago":"Biedermann, Sonja, Monika Henzinger, Christian Schulz, and Bernhard Schuster. “Memetic Graph Clustering.” In <i>17th International Symposium on Experimental Algorithms</i>, Vol. 103. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPICS.SEA.2018.3\">https://doi.org/10.4230/LIPICS.SEA.2018.3</a>.","apa":"Biedermann, S., Henzinger, M., Schulz, C., &#38; Schuster, B. (2018). Memetic graph clustering. In <i>17th International Symposium on Experimental Algorithms</i> (Vol. 103). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SEA.2018.3\">https://doi.org/10.4230/LIPICS.SEA.2018.3</a>","ieee":"S. Biedermann, M. Henzinger, C. Schulz, and B. Schuster, “Memetic graph clustering,” in <i>17th International Symposium on Experimental Algorithms</i>, L’Aquila, Italy, 2018, vol. 103."},"doi":"10.4230/LIPICS.SEA.2018.3","language":[{"iso":"eng"}],"volume":103,"status":"public","article_processing_charge":"No","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","day":"01","_id":"11911","date_created":"2022-08-18T06:49:40Z","oa":1},{"title":"Continuous heterogeneous photocatalysis in serial micro-batch reactors","publication":"Angewandte Chemie International Edition","date_published":"2018-07-26T00:00:00Z","type":"journal_article","scopus_import":"1","article_processing_charge":"No","status":"public","date_created":"2022-08-24T10:57:25Z","_id":"11958","day":"26","publisher":"Wiley","date_updated":"2023-02-21T10:09:18Z","abstract":[{"lang":"eng","text":"Solid reagents, leaching catalysts, and heterogeneous photocatalysts are commonly employed in batch processes but are ill-suited for continuous-flow chemistry. Heterogeneous catalysts for thermal reactions are typically used in packed-bed reactors, which cannot be penetrated by light and thus are not suitable for photocatalytic reactions involving solids. We demonstrate that serial micro-batch reactors (SMBRs) allow for the continuous utilization of solid materials together with liquids and gases in flow. This technology was utilized to develop selective and efficient fluorination reactions using a modified graphitic carbon nitride heterogeneous catalyst instead of costly homogeneous metal polypyridyl complexes. The merger of this inexpensive, recyclable catalyst and the SMBR approach enables sustainable and scalable photocatalysis."}],"publication_identifier":{"eissn":[" 1521-3773"],"issn":["1433-7851"]},"volume":57,"language":[{"iso":"eng"}],"doi":"10.1002/anie.201712568","citation":{"ieee":"B. Pieber, M. Shalom, M. Antonietti, P. H. Seeberger, and K. Gilmore, “Continuous heterogeneous photocatalysis in serial micro-batch reactors,” <i>Angewandte Chemie International Edition</i>, vol. 57, no. 31. Wiley, pp. 9976–9979, 2018.","ama":"Pieber B, Shalom M, Antonietti M, Seeberger PH, Gilmore K. Continuous heterogeneous photocatalysis in serial micro-batch reactors. <i>Angewandte Chemie International Edition</i>. 2018;57(31):9976-9979. doi:<a href=\"https://doi.org/10.1002/anie.201712568\">10.1002/anie.201712568</a>","ista":"Pieber B, Shalom M, Antonietti M, Seeberger PH, Gilmore K. 2018. Continuous heterogeneous photocatalysis in serial micro-batch reactors. Angewandte Chemie International Edition. 57(31), 9976–9979.","chicago":"Pieber, Bartholomäus, Menny Shalom, Markus Antonietti, Peter H. Seeberger, and Kerry Gilmore. “Continuous Heterogeneous Photocatalysis in Serial Micro-Batch Reactors.” <i>Angewandte Chemie International Edition</i>. Wiley, 2018. <a href=\"https://doi.org/10.1002/anie.201712568\">https://doi.org/10.1002/anie.201712568</a>.","apa":"Pieber, B., Shalom, M., Antonietti, M., Seeberger, P. H., &#38; Gilmore, K. (2018). Continuous heterogeneous photocatalysis in serial micro-batch reactors. <i>Angewandte Chemie International Edition</i>. Wiley. <a href=\"https://doi.org/10.1002/anie.201712568\">https://doi.org/10.1002/anie.201712568</a>","short":"B. Pieber, M. Shalom, M. Antonietti, P.H. Seeberger, K. Gilmore, Angewandte Chemie International Edition 57 (2018) 9976–9979.","mla":"Pieber, Bartholomäus, et al. “Continuous Heterogeneous Photocatalysis in Serial Micro-Batch Reactors.” <i>Angewandte Chemie International Edition</i>, vol. 57, no. 31, Wiley, 2018, pp. 9976–79, doi:<a href=\"https://doi.org/10.1002/anie.201712568\">10.1002/anie.201712568</a>."},"issue":"31","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","month":"07","year":"2018","quality_controlled":"1","pmid":1,"article_type":"letter_note","oa_version":"None","page":"9976-9979","publication_status":"published","intvolume":"        57","external_id":{"pmid":["29377383"]},"author":[{"id":"93e5e5b2-0da6-11ed-8a41-af589a024726","first_name":"Bartholomäus","full_name":"Pieber, Bartholomäus","orcid":"0000-0001-8689-388X","last_name":"Pieber"},{"first_name":"Menny","full_name":"Shalom, Menny","last_name":"Shalom"},{"last_name":"Antonietti","first_name":"Markus","full_name":"Antonietti, Markus"},{"last_name":"Seeberger","first_name":"Peter H.","full_name":"Seeberger, Peter H."},{"last_name":"Gilmore","first_name":"Kerry","full_name":"Gilmore, Kerry"}]},{"file":[{"content_type":"application/pdf","date_updated":"2020-07-14T12:45:37Z","file_name":"IST-2018-1065-v1+1_ACS_nanoletters_8b03217.pdf","checksum":"3e6034a94c6b5335e939145d88bdb371","date_created":"2018-12-12T10:16:08Z","relation":"main_file","file_size":1361441,"access_level":"open_access","file_id":"5194","creator":"system"}],"oa_version":"Published Version","page":"7141 - 7145","publication_status":"published","intvolume":"        18","project":[{"_id":"25517E86-B435-11E9-9278-68D0E5697425","name":"Towards Spin qubits and Majorana fermions in Germanium self assembled hut-wires","grant_number":"335497","call_identifier":"FP7"}],"external_id":{"pmid":["30359041"],"isi":["000451102100064"]},"author":[{"orcid":"0000-0003-2424-8636","last_name":"Vukušić","full_name":"Vukušić, Lada","first_name":"Lada","id":"31E9F056-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kukucka","full_name":"Kukucka, Josip","id":"3F5D8856-F248-11E8-B48F-1D18A9856A87","first_name":"Josip"},{"last_name":"Watzinger","full_name":"Watzinger, Hannes","first_name":"Hannes","id":"35DF8E50-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Joshua M","id":"4CDE0A96-F248-11E8-B48F-1D18A9856A87","full_name":"Milem, Joshua M","last_name":"Milem"},{"full_name":"Schäffler, Friedrich","first_name":"Friedrich","last_name":"Schäffler"},{"full_name":"Katsaros, Georgios","first_name":"Georgios","id":"38DB5788-F248-11E8-B48F-1D18A9856A87","last_name":"Katsaros","orcid":"0000-0001-8342-202X"}],"issue":"11","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"10","year":"2018","quality_controlled":"1","publist_id":"8032","isi":1,"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"pmid":1,"acknowledged_ssus":[{"_id":"M-Shop"},{"_id":"NanoFab"}],"department":[{"_id":"GeKa"}],"article_processing_charge":"No","status":"public","date_created":"2018-12-11T11:44:13Z","oa":1,"_id":"23","publisher":"American Chemical Society","day":"25","date_updated":"2026-04-08T14:09:47Z","abstract":[{"text":"The strong atomistic spin–orbit coupling of holes makes single-shot spin readout measurements difficult because it reduces the spin lifetimes. By integrating the charge sensor into a high bandwidth radio frequency reflectometry setup, we were able to demonstrate single-shot readout of a germanium quantum dot hole spin and measure the spin lifetime. Hole spin relaxation times of about 90 μs at 500 mT are reported, with a total readout visibility of about 70%. By analyzing separately the spin-to-charge conversion and charge readout fidelities, we have obtained insight into the processes limiting the visibilities of hole spins. The analyses suggest that high hole visibilities are feasible at realistic experimental conditions, underlying the potential of hole spins for the realization of viable qubit devices.","lang":"eng"}],"publication_identifier":{"issn":["1530-6984"]},"volume":18,"language":[{"iso":"eng"}],"doi":"10.1021/acs.nanolett.8b03217","citation":{"apa":"Vukušić, L., Kukucka, J., Watzinger, H., Milem, J. M., Schäffler, F., &#38; Katsaros, G. (2018). Single-shot readout of hole spins in Ge. <i>Nano Letters</i>. American Chemical Society. <a href=\"https://doi.org/10.1021/acs.nanolett.8b03217\">https://doi.org/10.1021/acs.nanolett.8b03217</a>","chicago":"Vukušić, Lada, Josip Kukucka, Hannes Watzinger, Joshua M Milem, Friedrich Schäffler, and Georgios Katsaros. “Single-Shot Readout of Hole Spins in Ge.” <i>Nano Letters</i>. American Chemical Society, 2018. <a href=\"https://doi.org/10.1021/acs.nanolett.8b03217\">https://doi.org/10.1021/acs.nanolett.8b03217</a>.","ama":"Vukušić L, Kukucka J, Watzinger H, Milem JM, Schäffler F, Katsaros G. Single-shot readout of hole spins in Ge. <i>Nano Letters</i>. 2018;18(11):7141-7145. doi:<a href=\"https://doi.org/10.1021/acs.nanolett.8b03217\">10.1021/acs.nanolett.8b03217</a>","ista":"Vukušić L, Kukucka J, Watzinger H, Milem JM, Schäffler F, Katsaros G. 2018. Single-shot readout of hole spins in Ge. Nano Letters. 18(11), 7141–7145.","ieee":"L. Vukušić, J. Kukucka, H. Watzinger, J. M. Milem, F. Schäffler, and G. Katsaros, “Single-shot readout of hole spins in Ge,” <i>Nano Letters</i>, vol. 18, no. 11. American Chemical Society, pp. 7141–7145, 2018.","mla":"Vukušić, Lada, et al. “Single-Shot Readout of Hole Spins in Ge.” <i>Nano Letters</i>, vol. 18, no. 11, American Chemical Society, 2018, pp. 7141–45, doi:<a href=\"https://doi.org/10.1021/acs.nanolett.8b03217\">10.1021/acs.nanolett.8b03217</a>.","short":"L. Vukušić, J. Kukucka, H. Watzinger, J.M. Milem, F. Schäffler, G. Katsaros, Nano Letters 18 (2018) 7141–7145."},"file_date_updated":"2020-07-14T12:45:37Z","pubrep_id":"1065","has_accepted_license":"1","title":"Single-shot readout of hole spins in Ge","ddc":["530"],"ec_funded":1,"publication":"Nano Letters","date_published":"2018-10-25T00:00:00Z","type":"journal_article","related_material":{"record":[{"id":"7977","relation":"popular_science"},{"relation":"dissertation_contains","id":"7996","status":"public"},{"status":"public","relation":"dissertation_contains","id":"69"}]},"scopus_import":"1"},{"status":"public","acknowledgement":"This research was supported by the Vienna Science and Technology Fund (WWTF) grant ICT15-003; Austrian Science Fund (FWF): S11407-N23(RiSE/SHiNE);and an ERC Start Grant (279307:Graph Games).\r\n","article_processing_charge":"No","oa":1,"date_created":"2018-12-11T11:44:13Z","publisher":"IJCAI","day":"01","_id":"24","abstract":[{"lang":"eng","text":"Partially-observable Markov decision processes (POMDPs) with discounted-sum payoff are a standard framework to model a wide range of problems related to decision making under uncertainty. Traditionally, the goal has been to obtain policies that optimize the expectation of the discounted-sum payoff. A key drawback of the expectation measure is that even low probability events with extreme payoff can significantly affect the expectation, and thus the obtained policies are not necessarily risk-averse. An alternate approach is to optimize the probability that the payoff is above a certain threshold, which allows obtaining risk-averse policies, but ignores optimization of the expectation. We consider the expectation optimization with probabilistic guarantee (EOPG) problem, where the goal is to optimize the expectation ensuring that the payoff is above a given threshold with at least a specified probability. We present several results on the EOPG problem, including the first algorithm to solve it."}],"date_updated":"2025-04-14T13:51:04Z","volume":2018,"language":[{"iso":"eng"}],"doi":"10.24963/ijcai.2018/652","citation":{"ieee":"K. Chatterjee, A. Elgyütt, P. Novotný, and O. Rouillé, “Expectation optimization with probabilistic guarantees in POMDPs with discounted-sum objectives,” presented at the IJCAI: International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 2018, vol. 2018, pp. 4692–4699.","apa":"Chatterjee, K., Elgyütt, A., Novotný, P., &#38; Rouillé, O. (2018). Expectation optimization with probabilistic guarantees in POMDPs with discounted-sum objectives (Vol. 2018, pp. 4692–4699). Presented at the IJCAI: International Joint Conference on Artificial Intelligence, Stockholm, Sweden: IJCAI. <a href=\"https://doi.org/10.24963/ijcai.2018/652\">https://doi.org/10.24963/ijcai.2018/652</a>","chicago":"Chatterjee, Krishnendu, Adrian Elgyütt, Petr Novotný, and Owen Rouillé. “Expectation Optimization with Probabilistic Guarantees in POMDPs with Discounted-Sum Objectives,” 2018:4692–99. IJCAI, 2018. <a href=\"https://doi.org/10.24963/ijcai.2018/652\">https://doi.org/10.24963/ijcai.2018/652</a>.","ama":"Chatterjee K, Elgyütt A, Novotný P, Rouillé O. Expectation optimization with probabilistic guarantees in POMDPs with discounted-sum objectives. In: Vol 2018. IJCAI; 2018:4692-4699. doi:<a href=\"https://doi.org/10.24963/ijcai.2018/652\">10.24963/ijcai.2018/652</a>","ista":"Chatterjee K, Elgyütt A, Novotný P, Rouillé O. 2018. Expectation optimization with probabilistic guarantees in POMDPs with discounted-sum objectives. IJCAI: International Joint Conference on Artificial Intelligence vol. 2018, 4692–4699.","short":"K. Chatterjee, A. Elgyütt, P. Novotný, O. Rouillé, in:, IJCAI, 2018, pp. 4692–4699.","mla":"Chatterjee, Krishnendu, et al. <i>Expectation Optimization with Probabilistic Guarantees in POMDPs with Discounted-Sum Objectives</i>. Vol. 2018, IJCAI, 2018, pp. 4692–99, doi:<a href=\"https://doi.org/10.24963/ijcai.2018/652\">10.24963/ijcai.2018/652</a>."},"title":"Expectation optimization with probabilistic guarantees in POMDPs with discounted-sum objectives","ec_funded":1,"date_published":"2018-07-01T00:00:00Z","type":"conference","scopus_import":"1","oa_version":"Preprint","page":"4692 - 4699","publication_status":"published","intvolume":"      2018","project":[{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"},{"name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23"},{"grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications"}],"external_id":{"arxiv":["1804.10601"],"isi":["000764175404117"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1804.10601"}],"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"full_name":"Elgyütt, Adrian","first_name":"Adrian","id":"4A2E9DBA-F248-11E8-B48F-1D18A9856A87","last_name":"Elgyütt"},{"last_name":"Novotny","full_name":"Novotny, Petr","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Rouillé","full_name":"Rouillé, Owen","first_name":"Owen"}],"arxiv":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","month":"07","year":"2018","publist_id":"8031","quality_controlled":"1","conference":{"end_date":"2018-07-19","name":"IJCAI: International Joint Conference on Artificial Intelligence","start_date":"2018-07-13","location":"Stockholm, Sweden"},"isi":1,"department":[{"_id":"KrCh"},{"_id":"ToHe"}]},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"07","year":"2018","quality_controlled":"1","publist_id":"8030","conference":{"end_date":"2018-07-19","name":"IJCAI: International Joint Conference on Artificial Intelligence","location":"Stockholm, Sweden","start_date":"2018-07-13"},"isi":1,"department":[{"_id":"KrCh"}],"oa_version":"Published Version","page":"4764 - 4770","publication_status":"published","project":[{"name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003"},{"name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23"},{"call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"external_id":{"isi":["000764175404127"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.24963/ijcai.2018/662"}],"author":[{"last_name":"Horák","first_name":"Karel","full_name":"Horák, Karel"},{"last_name":"Bošanský","first_name":"Branislav","full_name":"Bošanský, Branislav"},{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"}],"title":"Goal-HSVI: Heuristic search value iteration for goal-POMDPs","ddc":["000"],"publication":"Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence","ec_funded":1,"date_published":"2018-07-01T00:00:00Z","type":"conference","scopus_import":"1","status":"public","acknowledgement":"∗This work has been supported by Vienna Science and Technology Fund (WWTF) Project ICT15-003, Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE), and ERC Starting grant (279307: Graph Games). This research was sponsored by the Army Research Laboratory and was accomplished under Cooperative Agreement Number W911NF-13-2-0045 (ARL Cyber Security CRA). ","article_processing_charge":"No","date_created":"2018-12-11T11:44:13Z","oa":1,"publisher":"IJCAI","day":"01","_id":"25","abstract":[{"lang":"eng","text":"Partially observable Markov decision processes (POMDPs) are the standard models for planning under uncertainty with both finite and infinite horizon. Besides the well-known discounted-sum objective, indefinite-horizon objective (aka Goal-POMDPs) is another classical objective for POMDPs. In this case, given a set of target states and a positive cost for each transition, the optimization objective is to minimize the expected total cost until a target state is reached. In the literature, RTDP-Bel or heuristic search value iteration (HSVI) have been used for solving Goal-POMDPs. Neither of these algorithms has theoretical convergence guarantees, and HSVI may even fail to terminate its trials. We give the following contributions: (1) We discuss the challenges introduced in Goal-POMDPs and illustrate how they prevent the original HSVI from converging. (2) We present a novel algorithm inspired by HSVI, termed Goal-HSVI, and show that our algorithm has convergence guarantees. (3) We show that Goal-HSVI outperforms RTDP-Bel on a set of well-known examples."}],"date_updated":"2026-06-18T18:34:17Z","volume":"2018-July","language":[{"iso":"eng"}],"citation":{"ieee":"K. Horák, B. Bošanský, and K. Chatterjee, “Goal-HSVI: Heuristic search value iteration for goal-POMDPs,” in <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>, Stockholm, Sweden, 2018, vol. 2018–July, pp. 4764–4770.","apa":"Horák, K., Bošanský, B., &#38; Chatterjee, K. (2018). Goal-HSVI: Heuristic search value iteration for goal-POMDPs. In <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i> (Vol. 2018–July, pp. 4764–4770). Stockholm, Sweden: IJCAI. <a href=\"https://doi.org/10.24963/ijcai.2018/662\">https://doi.org/10.24963/ijcai.2018/662</a>","chicago":"Horák, Karel, Branislav Bošanský, and Krishnendu Chatterjee. “Goal-HSVI: Heuristic Search Value Iteration for Goal-POMDPs.” In <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>, 2018–July:4764–70. IJCAI, 2018. <a href=\"https://doi.org/10.24963/ijcai.2018/662\">https://doi.org/10.24963/ijcai.2018/662</a>.","ista":"Horák K, Bošanský B, Chatterjee K. 2018. Goal-HSVI: Heuristic search value iteration for goal-POMDPs. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. IJCAI: International Joint Conference on Artificial Intelligence vol. 2018–July, 4764–4770.","ama":"Horák K, Bošanský B, Chatterjee K. Goal-HSVI: Heuristic search value iteration for goal-POMDPs. In: <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>. Vol 2018-July. IJCAI; 2018:4764-4770. doi:<a href=\"https://doi.org/10.24963/ijcai.2018/662\">10.24963/ijcai.2018/662</a>","short":"K. Horák, B. Bošanský, K. Chatterjee, in:, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI, 2018, pp. 4764–4770.","mla":"Horák, Karel, et al. “Goal-HSVI: Heuristic Search Value Iteration for Goal-POMDPs.” <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>, vol. 2018–July, IJCAI, 2018, pp. 4764–70, doi:<a href=\"https://doi.org/10.24963/ijcai.2018/662\">10.24963/ijcai.2018/662</a>."},"doi":"10.24963/ijcai.2018/662"},{"page":"3693-3701","publication_status":"published","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.08269"}],"external_id":{"isi":["000457843603087"],"arxiv":["1604.08269"]},"arxiv":1,"author":[{"last_name":"Mohapatra","full_name":"Mohapatra, Pritish","first_name":"Pritish"},{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal","full_name":"Rolinek, Michal","last_name":"Rolinek"},{"full_name":"Jawahar, C V","first_name":"C V","last_name":"Jawahar"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kumar","first_name":"M Pawan","full_name":"Kumar, M Pawan"}],"project":[{"grant_number":"616160","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"year":"2018","quality_controlled":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","month":"06","department":[{"_id":"VlKo"}],"isi":1,"conference":{"end_date":"2018-06-22","location":"Salt Lake City, UT, USA","start_date":"2018-06-18","name":"CVPR: Conference on Computer Vision and Pattern Recognition"},"oa":1,"date_created":"2018-12-11T11:45:33Z","_id":"273","publisher":"IEEE","day":"28","article_processing_charge":"No","status":"public","language":[{"iso":"eng"}],"doi":"10.1109/cvpr.2018.00389","citation":{"chicago":"Mohapatra, Pritish, Michal Rolinek, C V Jawahar, Vladimir Kolmogorov, and M Pawan Kumar. “Efficient Optimization for Rank-Based Loss Functions.” In <i>2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition</i>, 3693–3701. IEEE, 2018. <a href=\"https://doi.org/10.1109/cvpr.2018.00389\">https://doi.org/10.1109/cvpr.2018.00389</a>.","apa":"Mohapatra, P., Rolinek, M., Jawahar, C. V., Kolmogorov, V., &#38; Kumar, M. P. (2018). Efficient optimization for rank-based loss functions. In <i>2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition</i> (pp. 3693–3701). Salt Lake City, UT, USA: IEEE. <a href=\"https://doi.org/10.1109/cvpr.2018.00389\">https://doi.org/10.1109/cvpr.2018.00389</a>","ama":"Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. Efficient optimization for rank-based loss functions. In: <i>2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition</i>. IEEE; 2018:3693-3701. doi:<a href=\"https://doi.org/10.1109/cvpr.2018.00389\">10.1109/cvpr.2018.00389</a>","ista":"Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. 2018. Efficient optimization for rank-based loss functions. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition, 3693–3701.","ieee":"P. Mohapatra, M. Rolinek, C. V. Jawahar, V. Kolmogorov, and M. P. Kumar, “Efficient optimization for rank-based loss functions,” in <i>2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition</i>, Salt Lake City, UT, USA, 2018, pp. 3693–3701.","mla":"Mohapatra, Pritish, et al. “Efficient Optimization for Rank-Based Loss Functions.” <i>2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition</i>, IEEE, 2018, pp. 3693–701, doi:<a href=\"https://doi.org/10.1109/cvpr.2018.00389\">10.1109/cvpr.2018.00389</a>.","short":"P. Mohapatra, M. Rolinek, C.V. Jawahar, V. Kolmogorov, M.P. Kumar, in:, 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 3693–3701."},"date_updated":"2024-11-04T13:52:32Z","abstract":[{"lang":"eng","text":"The accuracy of information retrieval systems is often measured using complex loss functions such as the average precision (AP) or the normalized discounted cumulative gain (NDCG). Given a set of positive and negative samples, the parameters of a retrieval system can be estimated by minimizing these loss functions. However, the non-differentiability and non-decomposability of these loss functions does not allow for simple gradient based optimization algorithms. This issue is generally circumvented by either optimizing a structured hinge-loss upper bound to the loss function or by using asymptotic methods like the direct-loss minimization framework. Yet, the high computational complexity of loss-augmented inference, which is necessary for both the frameworks, prohibits its use in large training data sets. To alleviate this deficiency, we present a novel quicksort flavored algorithm for a large class of non-decomposable loss functions. We provide a complete characterization of the loss functions that are amenable to our algorithm, and show that it includes both AP and NDCG based loss functions. Furthermore, we prove that no comparison based algorithm can improve upon the computational complexity of our approach asymptotically. We demonstrate the effectiveness of our approach in the context of optimizing the structured hinge loss upper bound of AP and NDCG loss for learning models for a variety of vision tasks. We show that our approach provides significantly better results than simpler decomposable loss functions, while requiring a comparable training time."}],"publication_identifier":{"isbn":["9781538664209"]},"title":"Efficient optimization for rank-based loss functions","type":"conference","scopus_import":"1","ec_funded":1,"publication":"2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition","date_published":"2018-06-28T00:00:00Z"},{"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"isi":1,"pmid":1,"department":[{"_id":"MiSi"},{"_id":"Bio"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","issue":"6","month":"04","year":"2018","quality_controlled":"1","publist_id":"7627","intvolume":"       217","project":[{"grant_number":"Y 564-B12","call_identifier":"FWF","name":"Cytoskeletal force generation and force transduction of migrating leukocytes","_id":"25A8E5EA-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","grant_number":"281556","name":"Cytoskeletal force generation and force transduction of migrating leukocytes","_id":"25A603A2-B435-11E9-9278-68D0E5697425"}],"external_id":{"pmid":["29650776"],"isi":["000438077800026"]},"author":[{"last_name":"Brown","full_name":"Brown, Markus","first_name":"Markus","id":"3DAB9AFC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Louise","full_name":"Johnson, Louise","last_name":"Johnson"},{"full_name":"Leone, Dario","first_name":"Dario","last_name":"Leone"},{"last_name":"Májek","full_name":"Májek, Peter","first_name":"Peter"},{"orcid":"0000-0001-7829-3518","last_name":"Vaahtomeri","full_name":"Vaahtomeri, Kari","first_name":"Kari","id":"368EE576-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Senfter, Daniel","first_name":"Daniel","last_name":"Senfter"},{"full_name":"Bukosza, Nora","first_name":"Nora","last_name":"Bukosza"},{"full_name":"Schachner, Helga","first_name":"Helga","last_name":"Schachner"},{"first_name":"Gabriele","full_name":"Asfour, Gabriele","last_name":"Asfour"},{"last_name":"Langer","full_name":"Langer, Brigitte","first_name":"Brigitte"},{"orcid":"0000-0001-9843-3522","last_name":"Hauschild","full_name":"Hauschild, Robert","first_name":"Robert","id":"4E01D6B4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Parapatics","full_name":"Parapatics, Katja","first_name":"Katja"},{"full_name":"Hong, Young","first_name":"Young","last_name":"Hong"},{"first_name":"Keiryn","full_name":"Bennett, Keiryn","last_name":"Bennett"},{"full_name":"Kain, Renate","first_name":"Renate","last_name":"Kain"},{"last_name":"Detmar","first_name":"Michael","full_name":"Detmar, Michael"},{"orcid":"0000-0002-6620-9179","last_name":"Sixt","full_name":"Sixt, Michael K","first_name":"Michael K","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Jackson","full_name":"Jackson, David","first_name":"David"},{"full_name":"Kerjaschki, Dontscho","first_name":"Dontscho","last_name":"Kerjaschki"}],"file":[{"checksum":"9c7eba51a35c62da8c13f98120b64df4","file_name":"2018_JournalCellBiology_Brown.pdf","date_created":"2018-12-17T12:50:07Z","access_level":"open_access","file_id":"5704","creator":"dernst","file_size":2252043,"relation":"main_file","date_updated":"2020-07-14T12:45:45Z","content_type":"application/pdf"}],"oa_version":"Published Version","page":"2205 - 2221","publication_status":"published","publication":"Journal of Cell Biology","ec_funded":1,"date_published":"2018-04-12T00:00:00Z","type":"journal_article","scopus_import":"1","has_accepted_license":"1","title":"Lymphatic exosomes promote dendritic cell migration along guidance cues","ddc":["570"],"abstract":[{"text":"Lymphatic endothelial cells (LECs) release extracellular chemokines to guide the migration of dendritic cells. In this study, we report that LECs also release basolateral exosome-rich endothelial vesicles (EEVs) that are secreted in greater numbers in the presence of inflammatory cytokines and accumulate in the perivascular stroma of small lymphatic vessels in human chronic inflammatory diseases. Proteomic analyses of EEV fractions identified &gt; 1,700 cargo proteins and revealed a dominant motility-promoting protein signature. In vitro and ex vivo EEV fractions augmented cellular protrusion formation in a CX3CL1/fractalkine-dependent fashion and enhanced the directional migratory response of human dendritic cells along guidance cues. We conclude that perilymphatic LEC exosomes enhance exploratory behavior and thus promote directional migration of CX3CR1-expressing cells in complex tissue environments.","lang":"eng"}],"date_updated":"2025-04-14T13:10:20Z","language":[{"iso":"eng"}],"volume":217,"citation":{"mla":"Brown, Markus, et al. “Lymphatic Exosomes Promote Dendritic Cell Migration along Guidance Cues.” <i>Journal of Cell Biology</i>, vol. 217, no. 6, Rockefeller University Press, 2018, pp. 2205–21, doi:<a href=\"https://doi.org/10.1083/jcb.201612051\">10.1083/jcb.201612051</a>.","short":"M. Brown, L. Johnson, D. Leone, P. Májek, K. Vaahtomeri, D. Senfter, N. Bukosza, H. Schachner, G. Asfour, B. Langer, R. Hauschild, K. Parapatics, Y. Hong, K. Bennett, R. Kain, M. Detmar, M.K. Sixt, D. Jackson, D. Kerjaschki, Journal of Cell Biology 217 (2018) 2205–2221.","apa":"Brown, M., Johnson, L., Leone, D., Májek, P., Vaahtomeri, K., Senfter, D., … Kerjaschki, D. (2018). Lymphatic exosomes promote dendritic cell migration along guidance cues. <i>Journal of Cell Biology</i>. Rockefeller University Press. <a href=\"https://doi.org/10.1083/jcb.201612051\">https://doi.org/10.1083/jcb.201612051</a>","chicago":"Brown, Markus, Louise Johnson, Dario Leone, Peter Májek, Kari Vaahtomeri, Daniel Senfter, Nora Bukosza, et al. “Lymphatic Exosomes Promote Dendritic Cell Migration along Guidance Cues.” <i>Journal of Cell Biology</i>. Rockefeller University Press, 2018. <a href=\"https://doi.org/10.1083/jcb.201612051\">https://doi.org/10.1083/jcb.201612051</a>.","ista":"Brown M, Johnson L, Leone D, Májek P, Vaahtomeri K, Senfter D, Bukosza N, Schachner H, Asfour G, Langer B, Hauschild R, Parapatics K, Hong Y, Bennett K, Kain R, Detmar M, Sixt MK, Jackson D, Kerjaschki D. 2018. Lymphatic exosomes promote dendritic cell migration along guidance cues. Journal of Cell Biology. 217(6), 2205–2221.","ama":"Brown M, Johnson L, Leone D, et al. Lymphatic exosomes promote dendritic cell migration along guidance cues. <i>Journal of Cell Biology</i>. 2018;217(6):2205-2221. doi:<a href=\"https://doi.org/10.1083/jcb.201612051\">10.1083/jcb.201612051</a>","ieee":"M. Brown <i>et al.</i>, “Lymphatic exosomes promote dendritic cell migration along guidance cues,” <i>Journal of Cell Biology</i>, vol. 217, no. 6. Rockefeller University Press, pp. 2205–2221, 2018."},"doi":"10.1083/jcb.201612051","file_date_updated":"2020-07-14T12:45:45Z","acknowledgement":"M. Brown was supported by the Cell Communication in Health and Disease Graduate Study Program of the Austrian Science Fund and Medizinische Universität Wien, M. Sixt by the European Research Council (ERC GA 281556) and an Austrian Science Fund START award, K.L. Bennett by the Austrian Academy of Sciences, D.G. Jackson and L.A. Johnson by Unit Funding (MC_UU_12010/2) and project grants from the Medical Research Council (G1100134 and MR/L008610/1), and M. Detmar by the Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung and Advanced European Research Council grant LYVICAM. K. Vaahtomeri was supported by an Academy of Finland postdoctoral research grant (287853). This project has received funding from the European Union’s Horizon 2020 research and innovation program under grant agreement No. 668036 (RELENT).","status":"public","article_processing_charge":"No","corr_author":"1","oa":1,"date_created":"2018-12-11T11:45:33Z","publisher":"Rockefeller University Press","day":"12","_id":"275"},{"title":"Nano-scale microfluidics to study 3D chemotaxis at the single cell level","has_accepted_license":"1","ddc":["570"],"publication":"PLoS One","date_published":"2018-06-07T00:00:00Z","type":"journal_article","scopus_import":"1","status":"public","acknowledgement":"This work was supported by the Swiss National Science Foundation (MD-PhD fellowships, 323530_164221 to C.F.; and 323630_151483 to A.J.; grant PZ00P3_144863 to M.R, grant 31003A_156431 to T.S.; PZ00P3_148000 to C.T.B.; PZ00P3_154733 to M.M.), a Novartis “FreeNovation” grant to M.M. and T.S. and an EMBO long-term fellowship (ALTF 1396-2014) co-funded by the European Commission (LTFCOFUND2013, GA-2013-609409) to J.R.. M.R. was supported by the Gebert Rüf Foundation (GRS 058/14). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.","article_processing_charge":"No","oa":1,"date_created":"2018-12-11T11:45:34Z","day":"07","publisher":"Public Library of Science","_id":"276","abstract":[{"lang":"eng","text":"Directed migration of cells relies on their ability to sense directional guidance cues and to interact with pericellular structures in order to transduce contractile cytoskeletal- into mechanical forces. These biomechanical processes depend highly on microenvironmental factors such as exposure to 2D surfaces or 3D matrices. In vivo, the majority of cells are exposed to 3D environments. Data on 3D cell migration are mostly derived from intravital microscopy or collagen-based in vitro assays. Both approaches offer only limited controlla-bility of experimental conditions. Here, we developed an automated microfluidic system that allows positioning of cells in 3D microenvironments containing highly controlled diffusion-based chemokine gradients. Tracking migration in such gradients was feasible in real time at the single cell level. Moreover, the setup allowed on-chip immunocytochemistry and thus linking of functional with phenotypical properties in individual cells. Spatially defined retrieval of cells from the device allows down-stream off-chip analysis. Using dendritic cells as a model, our setup specifically allowed us for the first time to quantitate key migration characteristics of cells exposed to identical gradients of the chemokine CCL19 yet placed on 2D vs in 3D environments. Migration properties between 2D and 3D migration were distinct. Morphological features of cells migrating in an in vitro 3D environment were similar to those of cells migrating in animal tissues, but different from cells migrating on a surface. Our system thus offers a highly controllable in vitro-mimic of a 3D environment that cells traffic in vivo."}],"date_updated":"2023-09-13T09:00:15Z","volume":13,"language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:45:45Z","citation":{"ieee":"C. Frick <i>et al.</i>, “Nano-scale microfluidics to study 3D chemotaxis at the single cell level,” <i>PLoS One</i>, vol. 13, no. 6. Public Library of Science, 2018.","chicago":"Frick, Corina, Philip Dettinger, Jörg Renkawitz, Annaïse Jauch, Christoph Berger, Mike Recher, Timm Schroeder, and Matthias Mehling. “Nano-Scale Microfluidics to Study 3D Chemotaxis at the Single Cell Level.” <i>PLoS One</i>. Public Library of Science, 2018. <a href=\"https://doi.org/10.1371/journal.pone.0198330\">https://doi.org/10.1371/journal.pone.0198330</a>.","apa":"Frick, C., Dettinger, P., Renkawitz, J., Jauch, A., Berger, C., Recher, M., … Mehling, M. (2018). Nano-scale microfluidics to study 3D chemotaxis at the single cell level. <i>PLoS One</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pone.0198330\">https://doi.org/10.1371/journal.pone.0198330</a>","ista":"Frick C, Dettinger P, Renkawitz J, Jauch A, Berger C, Recher M, Schroeder T, Mehling M. 2018. Nano-scale microfluidics to study 3D chemotaxis at the single cell level. PLoS One. 13(6), e0198330.","ama":"Frick C, Dettinger P, Renkawitz J, et al. Nano-scale microfluidics to study 3D chemotaxis at the single cell level. <i>PLoS One</i>. 2018;13(6). doi:<a href=\"https://doi.org/10.1371/journal.pone.0198330\">10.1371/journal.pone.0198330</a>","short":"C. Frick, P. Dettinger, J. Renkawitz, A. Jauch, C. Berger, M. Recher, T. Schroeder, M. Mehling, PLoS One 13 (2018).","mla":"Frick, Corina, et al. “Nano-Scale Microfluidics to Study 3D Chemotaxis at the Single Cell Level.” <i>PLoS One</i>, vol. 13, no. 6, e0198330, Public Library of Science, 2018, doi:<a href=\"https://doi.org/10.1371/journal.pone.0198330\">10.1371/journal.pone.0198330</a>."},"doi":"10.1371/journal.pone.0198330","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","issue":"6","month":"06","year":"2018","publist_id":"7626","quality_controlled":"1","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"isi":1,"article_type":"original","article_number":"e0198330","department":[{"_id":"MiSi"}],"file":[{"date_updated":"2020-07-14T12:45:45Z","content_type":"application/pdf","date_created":"2018-12-17T14:10:32Z","checksum":"95fc5dc3938b3ad3b7697d10c83cc143","file_name":"2018_Plos_Frick.pdf","creator":"dernst","file_id":"5709","access_level":"open_access","relation":"main_file","file_size":7682167}],"oa_version":"Published Version","publication_status":"published","intvolume":"        13","external_id":{"isi":["000434384900031"]},"author":[{"first_name":"Corina","full_name":"Frick, Corina","last_name":"Frick"},{"last_name":"Dettinger","first_name":"Philip","full_name":"Dettinger, Philip"},{"orcid":"0000-0003-2856-3369","last_name":"Renkawitz","id":"3F0587C8-F248-11E8-B48F-1D18A9856A87","first_name":"Jörg","full_name":"Renkawitz, Jörg"},{"first_name":"Annaïse","full_name":"Jauch, Annaïse","last_name":"Jauch"},{"first_name":"Christoph","full_name":"Berger, Christoph","last_name":"Berger"},{"last_name":"Recher","full_name":"Recher, Mike","first_name":"Mike"},{"last_name":"Schroeder","first_name":"Timm","full_name":"Schroeder, Timm"},{"first_name":"Matthias","full_name":"Mehling, Matthias","last_name":"Mehling"}]},{"file":[{"content_type":"application/pdf","date_updated":"2020-07-14T12:45:45Z","file_size":1150679,"relation":"main_file","creator":"dernst","access_level":"open_access","file_id":"7834","date_created":"2020-05-14T12:23:08Z","file_name":"2018_PlantMolecBio_Dokladal.pdf","checksum":"451ae47616e6af2533099f596b2a47fb"}],"oa_version":"Submitted Version","page":"407 - 420","publication_status":"published","intvolume":"        97","external_id":{"isi":["000438981700009"]},"author":[{"last_name":"Dokládal","first_name":"Ladislav","full_name":"Dokládal, Ladislav"},{"orcid":"0000-0002-8510-9739","last_name":"Benková","first_name":"Eva","id":"38F4F166-F248-11E8-B48F-1D18A9856A87","full_name":"Benková, Eva"},{"full_name":"Honys, David","first_name":"David","last_name":"Honys"},{"last_name":"Dupláková","first_name":"Nikoleta","full_name":"Dupláková, Nikoleta"},{"last_name":"Lee","first_name":"Lan","full_name":"Lee, Lan"},{"first_name":"Stanton","full_name":"Gelvin, Stanton","last_name":"Gelvin"},{"full_name":"Sýkorová, Eva","first_name":"Eva","last_name":"Sýkorová"}],"issue":"5","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","month":"06","year":"2018","quality_controlled":"1","publist_id":"7625","isi":1,"article_type":"original","department":[{"_id":"EvBe"}],"article_processing_charge":"No","status":"public","oa":1,"date_created":"2018-12-11T11:45:34Z","_id":"277","publisher":"Springer","day":"12","date_updated":"2023-09-08T13:21:05Z","abstract":[{"text":"Arabidopsis and human ARM protein interact with telomerase. Deregulated mRNA levels of DNA repair and ribosomal protein genes in an Arabidopsis arm mutant suggest non-telomeric ARM function. The human homolog ARMC6 interacts with hTRF2. Abstract: Telomerase maintains telomeres and has proposed non-telomeric functions. We previously identified interaction of the C-terminal domain of Arabidopsis telomerase reverse transcriptase (AtTERT) with an armadillo/β-catenin-like repeat (ARM) containing protein. Here we explore protein–protein interactions of the ARM protein, AtTERT domains, POT1a, TRF-like family and SMH family proteins, and the chromatin remodeling protein CHR19 using bimolecular fluorescence complementation (BiFC), yeast two-hybrid (Y2H) analysis, and co-immunoprecipitation. The ARM protein interacts with both the N- and C-terminal domains of AtTERT in different cellular compartments. ARM interacts with CHR19 and TRF-like I family proteins that also bind AtTERT directly or through interaction with POT1a. The putative human ARM homolog co-precipitates telomerase activity and interacts with hTRF2 protein in vitro. Analysis of Arabidopsis arm mutants shows no obvious changes in telomere length or telomerase activity, suggesting that ARM is not essential for telomere maintenance. The observed interactions with telomerase and Myb-like domain proteins (TRF-like family I) may therefore reflect possible non-telomeric functions. Transcript levels of several DNA repair and ribosomal genes are affected in arm mutants, and ARM, likely in association with other proteins, suppressed expression of XRCC3 and RPSAA promoter constructs in luciferase reporter assays. In conclusion, ARM can participate in non-telomeric functions of telomerase, and can also perform its own telomerase-independent functions.","lang":"eng"}],"language":[{"iso":"eng"}],"volume":97,"citation":{"ieee":"L. Dokládal <i>et al.</i>, “An armadillo-domain protein participates in a telomerase interaction network,” <i>Plant Molecular Biology</i>, vol. 97, no. 5. Springer, pp. 407–420, 2018.","apa":"Dokládal, L., Benková, E., Honys, D., Dupláková, N., Lee, L., Gelvin, S., &#38; Sýkorová, E. (2018). An armadillo-domain protein participates in a telomerase interaction network. <i>Plant Molecular Biology</i>. Springer. <a href=\"https://doi.org/10.1007/s11103-018-0747-4\">https://doi.org/10.1007/s11103-018-0747-4</a>","chicago":"Dokládal, Ladislav, Eva Benková, David Honys, Nikoleta Dupláková, Lan Lee, Stanton Gelvin, and Eva Sýkorová. “An Armadillo-Domain Protein Participates in a Telomerase Interaction Network.” <i>Plant Molecular Biology</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s11103-018-0747-4\">https://doi.org/10.1007/s11103-018-0747-4</a>.","ama":"Dokládal L, Benková E, Honys D, et al. An armadillo-domain protein participates in a telomerase interaction network. <i>Plant Molecular Biology</i>. 2018;97(5):407-420. doi:<a href=\"https://doi.org/10.1007/s11103-018-0747-4\">10.1007/s11103-018-0747-4</a>","ista":"Dokládal L, Benková E, Honys D, Dupláková N, Lee L, Gelvin S, Sýkorová E. 2018. An armadillo-domain protein participates in a telomerase interaction network. Plant Molecular Biology. 97(5), 407–420.","short":"L. Dokládal, E. Benková, D. Honys, N. Dupláková, L. Lee, S. Gelvin, E. Sýkorová, Plant Molecular Biology 97 (2018) 407–420.","mla":"Dokládal, Ladislav, et al. “An Armadillo-Domain Protein Participates in a Telomerase Interaction Network.” <i>Plant Molecular Biology</i>, vol. 97, no. 5, Springer, 2018, pp. 407–20, doi:<a href=\"https://doi.org/10.1007/s11103-018-0747-4\">10.1007/s11103-018-0747-4</a>."},"file_date_updated":"2020-07-14T12:45:45Z","doi":"10.1007/s11103-018-0747-4","has_accepted_license":"1","title":"An armadillo-domain protein participates in a telomerase interaction network","ddc":["580"],"publication":"Plant Molecular Biology","date_published":"2018-06-12T00:00:00Z","type":"journal_article","scopus_import":"1"},{"publication_status":"published","day":"06","publisher":"Universität Wien","_id":"278","page":"94","date_created":"2018-12-11T11:45:34Z","oa":1,"oa_version":"Published Version","status":"public","article_processing_charge":"No","author":[{"last_name":"Villányi","orcid":"0000-0001-8126-0426","full_name":"Villányi, Márton","first_name":"Márton","id":"3FFCCD3A-F248-11E8-B48F-1D18A9856A87"}],"citation":{"short":"M. Villányi, Lizenzverträge mit Open-Access-Komponenten an österreichischen Bibliotheken, Universität Wien, 2018.","mla":"Villányi, Márton. <i>Lizenzverträge mit Open-Access-Komponenten an österreichischen Bibliotheken</i>. Universität Wien, 2018.","ieee":"M. Villányi, “Lizenzverträge mit Open-Access-Komponenten an österreichischen Bibliotheken,” Universität Wien, 2018.","ista":"Villányi M. 2018. Lizenzverträge mit Open-Access-Komponenten an österreichischen Bibliotheken. Universität Wien.","ama":"Villányi M. Lizenzverträge mit Open-Access-Komponenten an österreichischen Bibliotheken. 2018.","apa":"Villányi, M. (2018). <i>Lizenzverträge mit Open-Access-Komponenten an österreichischen Bibliotheken</i>. Universität Wien.","chicago":"Villányi, Márton. “Lizenzverträge mit Open-Access-Komponenten an österreichischen Bibliotheken.” Universität Wien, 2018."},"language":[{"iso":"ger"}],"main_file_link":[{"open_access":"1","url":"http://othes.univie.ac.at/51113/"}],"abstract":[{"lang":"eng","text":"Consortial subscription contracts regulate the digital access to publications between publishers and scientific libraries. However, since a couple of years the tendency towards a freely accessible publishing (Open Access) intensifies. As a consequence of this trend the contractual relationship between licensor and licensee is gradually changing as well: More and more contracts exercise influence on open access publishing. The present study attempts to compare Austrian examples of consortial licence contracts, which include components of open access. It describes the difference between pure subscription contracts and differing innovative deals including open access components. Thereby it becomes obvious that for the evaluation of this licence contracts new methods are needed. An essential new element of such analyses is the evaluation of the open access publication numbers. So this study tries to carry out such publication analyses for Austrian open access deals focusing on quantitative questions: How does the number of publications evolve? How does the open access share change? Publications reports of the publishers and database queries from Scopus form the data basis. The analysis of the data points out that differing approaches of contracts result in highly divergent results: Particular deals can prioritize a saving in costs or else the increase of the open access rate. It is to be assumed that within the following years further numerous open access deals will be negotiated. The finding of this study shall provide guidance."}],"date_updated":"2026-06-18T18:35:07Z","ddc":["020"],"publist_id":"7624","OA_place":"publisher","title":"Lizenzverträge mit Open-Access-Komponenten an österreichischen Bibliotheken","year":"2018","month":"04","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"id":"5577","relation":"dissertation_contains","status":"public"},{"status":"public","id":"5574","relation":"dissertation_contains"},{"relation":"dissertation_contains","id":"5578","status":"public"},{"status":"public","id":"5579","relation":"dissertation_contains"},{"id":"5576","relation":"dissertation_contains","status":"public"},{"id":"5575","relation":"dissertation_contains","status":"public"},{"status":"public","relation":"dissertation_contains","id":"5582"},{"relation":"dissertation_contains","id":"5581","status":"public"},{"status":"public","id":"5580","relation":"dissertation_contains"}]},"type":"dissertation","department":[{"_id":"E-Lib"}],"date_published":"2018-04-06T00:00:00Z","supervisor":[{"full_name":"Kromp, Brigitte","first_name":"Brigitte","last_name":"Kromp"}]},{"publist_id":"7620","quality_controlled":"1","year":"2018","month":"05","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","department":[{"_id":"FyKo"}],"article_number":"67","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"isi":1,"publication_status":"published","oa_version":"Published Version","file":[{"content_type":"application/pdf","date_updated":"2020-07-14T12:45:47Z","relation":"main_file","file_size":1414722,"creator":"dernst","file_id":"5708","access_level":"open_access","date_created":"2018-12-17T14:05:01Z","checksum":"f3e4922486bd9bf1483271bdbed394a7","file_name":"2018_GenomeBiology_Zapata.pdf"}],"author":[{"last_name":"Zapata","first_name":"Luis","full_name":"Zapata, Luis"},{"full_name":"Pich, Oriol","first_name":"Oriol","last_name":"Pich"},{"last_name":"Serrano","first_name":"Luis","full_name":"Serrano, Luis"},{"orcid":"0000-0001-8243-4694","last_name":"Kondrashov","full_name":"Kondrashov, Fyodor","id":"44FDEF62-F248-11E8-B48F-1D18A9856A87","first_name":"Fyodor"},{"last_name":"Ossowski","full_name":"Ossowski, Stephan","first_name":"Stephan"},{"full_name":"Schaefer, Martin","first_name":"Martin","last_name":"Schaefer"}],"external_id":{"isi":["000433986200001"]},"project":[{"_id":"26120F5C-B435-11E9-9278-68D0E5697425","name":"Systematic investigation of epistasis in molecular evolution","call_identifier":"FP7","grant_number":"335980"}],"intvolume":"        19","ddc":["570"],"has_accepted_license":"1","title":"Negative selection in tumor genome evolution acts on essential cellular functions and the immunopeptidome","scopus_import":"1","related_material":{"record":[{"relation":"research_data","id":"9811","status":"public"},{"status":"public","relation":"research_data","id":"9812"}]},"type":"journal_article","date_published":"2018-05-31T00:00:00Z","publication":"Genome Biology","ec_funded":1,"publisher":"BioMed Central","day":"31","_id":"279","date_created":"2018-12-11T11:45:35Z","oa":1,"status":"public","article_processing_charge":"No","file_date_updated":"2020-07-14T12:45:47Z","citation":{"mla":"Zapata, Luis, et al. “Negative Selection in Tumor Genome Evolution Acts on Essential Cellular Functions and the Immunopeptidome.” <i>Genome Biology</i>, vol. 19, 67, BioMed Central, 2018, doi:<a href=\"https://doi.org/10.1186/s13059-018-1434-0\">10.1186/s13059-018-1434-0</a>.","short":"L. Zapata, O. Pich, L. Serrano, F. Kondrashov, S. Ossowski, M. Schaefer, Genome Biology 19 (2018).","apa":"Zapata, L., Pich, O., Serrano, L., Kondrashov, F., Ossowski, S., &#38; Schaefer, M. (2018). Negative selection in tumor genome evolution acts on essential cellular functions and the immunopeptidome. <i>Genome Biology</i>. BioMed Central. <a href=\"https://doi.org/10.1186/s13059-018-1434-0\">https://doi.org/10.1186/s13059-018-1434-0</a>","chicago":"Zapata, Luis, Oriol Pich, Luis Serrano, Fyodor Kondrashov, Stephan Ossowski, and Martin Schaefer. “Negative Selection in Tumor Genome Evolution Acts on Essential Cellular Functions and the Immunopeptidome.” <i>Genome Biology</i>. BioMed Central, 2018. <a href=\"https://doi.org/10.1186/s13059-018-1434-0\">https://doi.org/10.1186/s13059-018-1434-0</a>.","ama":"Zapata L, Pich O, Serrano L, Kondrashov F, Ossowski S, Schaefer M. Negative selection in tumor genome evolution acts on essential cellular functions and the immunopeptidome. <i>Genome Biology</i>. 2018;19. doi:<a href=\"https://doi.org/10.1186/s13059-018-1434-0\">10.1186/s13059-018-1434-0</a>","ista":"Zapata L, Pich O, Serrano L, Kondrashov F, Ossowski S, Schaefer M. 2018. Negative selection in tumor genome evolution acts on essential cellular functions and the immunopeptidome. Genome Biology. 19, 67.","ieee":"L. Zapata, O. Pich, L. Serrano, F. Kondrashov, S. Ossowski, and M. Schaefer, “Negative selection in tumor genome evolution acts on essential cellular functions and the immunopeptidome,” <i>Genome Biology</i>, vol. 19. BioMed Central, 2018."},"doi":"10.1186/s13059-018-1434-0","language":[{"iso":"eng"}],"volume":19,"abstract":[{"text":"Background: Natural selection shapes cancer genomes. Previous studies used signatures of positive selection to identify genes driving malignant transformation. However, the contribution of negative selection against somatic mutations that affect essential tumor functions or specific domains remains a controversial topic. Results: Here, we analyze 7546 individual exomes from 26 tumor types from TCGA data to explore the portion of the cancer exome under negative selection. Although we find most of the genes neutrally evolving in a pan-cancer framework, we identify essential cancer genes and immune-exposed protein regions under significant negative selection. Moreover, our simulations suggest that the amount of negative selection is underestimated. We therefore choose an empirical approach to identify genes, functions, and protein regions under negative selection. We find that expression and mutation status of negatively selected genes is indicative of patient survival. Processes that are most strongly conserved are those that play fundamental cellular roles such as protein synthesis, glucose metabolism, and molecular transport. Intriguingly, we observe strong signals of selection in the immunopeptidome and proteins controlling peptide exposition, highlighting the importance of immune surveillance evasion. Additionally, tumor type-specific immune activity correlates with the strength of negative selection on human epitopes. Conclusions: In summary, our results show that negative selection is a hallmark of cell essentiality and immune response in cancer. The functional domains identified could be exploited therapeutically, ultimately allowing for the development of novel cancer treatments.","lang":"eng"}],"date_updated":"2025-04-15T08:30:30Z"}]