[{"publisher":"Springer Nature","page":"104–117","quality_controlled":"1","title":"Ad exchange: Envy-free auctions with mediators","alternative_title":["LNCS"],"intvolume":"      9470","publication_status":"published","date_created":"2022-08-08T13:33:56Z","article_processing_charge":"No","author":[{"full_name":"Ben-Zwi, Oren","last_name":"Ben-Zwi","first_name":"Oren"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger"},{"first_name":"Veronika","last_name":"Loitzenbauer","full_name":"Loitzenbauer, Veronika"}],"_id":"11773","scopus_import":"1","extern":"1","volume":9470,"abstract":[{"text":"Ad exchanges are an emerging platform for trading advertisement slots on the web with billions of dollars revenue per year. Every time a user visits a web page, the publisher of that web page can ask an ad exchange to auction off the ad slots on this page to determine which advertisements are shown at which price. Due to the high volume of traffic, ad networks typically act as mediators for individual advertisers at ad exchanges. If multiple advertisers in an ad network are interested in the ad slots of the same auction, the ad network might use a “local” auction to resell the obtained ad slots among its advertisers.\r\n\r\nIn this work we want to deepen the theoretical understanding of these new markets by analyzing them from the viewpoint of combinatorial auctions. Prior work studied mostly single-item auctions, while we allow the advertisers to express richer preferences over multiple items. We develop a game-theoretic model for the entanglement of the central auction at the ad exchange with the local auctions at the ad networks. We consider the incentives of all three involved parties and suggest a three-party competitive equilibrium, an extension of the Walrasian equilibrium that ensures envy-freeness for all participants. We show the existence of a three-party competitive equilibrium and a polynomial-time algorithm to find one for gross-substitute bidder valuations.","lang":"eng"}],"arxiv":1,"doi":"10.1007/978-3-662-48995-6_8","day":"09","external_id":{"arxiv":["1604.05562"]},"date_updated":"2023-02-10T09:06:23Z","year":"2015","citation":{"chicago":"Ben-Zwi, Oren, Monika H Henzinger, and Veronika Loitzenbauer. “Ad Exchange: Envy-Free Auctions with Mediators.” In <i>11th International Conference on Web and Internet Economics</i>, 9470:104–117. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-662-48995-6_8\">https://doi.org/10.1007/978-3-662-48995-6_8</a>.","ieee":"O. Ben-Zwi, M. H. Henzinger, and V. Loitzenbauer, “Ad exchange: Envy-free auctions with mediators,” in <i>11th International Conference on Web and Internet Economics</i>, Amsterdam, Netherlands, 2015, vol. 9470, pp. 104–117.","apa":"Ben-Zwi, O., Henzinger, M. H., &#38; Loitzenbauer, V. (2015). Ad exchange: Envy-free auctions with mediators. In <i>11th International Conference on Web and Internet Economics</i> (Vol. 9470, pp. 104–117). Amsterdam, Netherlands: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-48995-6_8\">https://doi.org/10.1007/978-3-662-48995-6_8</a>","ama":"Ben-Zwi O, Henzinger MH, Loitzenbauer V. Ad exchange: Envy-free auctions with mediators. In: <i>11th International Conference on Web and Internet Economics</i>. Vol 9470. Springer Nature; 2015:104–117. doi:<a href=\"https://doi.org/10.1007/978-3-662-48995-6_8\">10.1007/978-3-662-48995-6_8</a>","ista":"Ben-Zwi O, Henzinger MH, Loitzenbauer V. 2015. Ad exchange: Envy-free auctions with mediators. 11th International Conference on Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 9470, 104–117.","mla":"Ben-Zwi, Oren, et al. “Ad Exchange: Envy-Free Auctions with Mediators.” <i>11th International Conference on Web and Internet Economics</i>, vol. 9470, Springer Nature, 2015, pp. 104–117, doi:<a href=\"https://doi.org/10.1007/978-3-662-48995-6_8\">10.1007/978-3-662-48995-6_8</a>.","short":"O. Ben-Zwi, M.H. Henzinger, V. Loitzenbauer, in:, 11th International Conference on Web and Internet Economics, Springer Nature, 2015, pp. 104–117."},"conference":{"name":"WINE: International Conference on Web and Internet Economics","start_date":"2015-09-09","location":"Amsterdam, Netherlands","end_date":"2015-09-12"},"language":[{"iso":"eng"}],"month":"12","oa_version":"Preprint","publication":"11th International Conference on Web and Internet Economics","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1604.05562","open_access":"1"}],"oa":1,"publication_identifier":{"eisbn":["9783662489956"],"issn":["0302-9743"],"isbn":["9783662489949"]},"date_published":"2015-12-09T00:00:00Z","type":"conference"},{"extern":"1","volume":9470,"external_id":{"arxiv":["1509.09147"]},"year":"2015","citation":{"ieee":"Y. K. Cheung, M. H. Henzinger, M. Hoefer, and M. Starnberger, “Combinatorial auctions with conflict-based externalities,” in <i>11th International Conference on Web and Internet Economics</i>, Amsterdam, Netherlands, 2015, vol. 9470, pp. 230–243.","chicago":"Cheung, Yun Kuen, Monika H Henzinger, Martin Hoefer, and Martin Starnberger. “Combinatorial Auctions with Conflict-Based Externalities.” In <i>11th International Conference on Web and Internet Economics</i>, 9470:230–243. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-662-48995-6_17\">https://doi.org/10.1007/978-3-662-48995-6_17</a>.","ama":"Cheung YK, Henzinger MH, Hoefer M, Starnberger M. Combinatorial auctions with conflict-based externalities. In: <i>11th International Conference on Web and Internet Economics</i>. Vol 9470. Springer Nature; 2015:230–243. doi:<a href=\"https://doi.org/10.1007/978-3-662-48995-6_17\">10.1007/978-3-662-48995-6_17</a>","apa":"Cheung, Y. K., Henzinger, M. H., Hoefer, M., &#38; Starnberger, M. (2015). Combinatorial auctions with conflict-based externalities. In <i>11th International Conference on Web and Internet Economics</i> (Vol. 9470, pp. 230–243). Amsterdam, Netherlands: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-48995-6_17\">https://doi.org/10.1007/978-3-662-48995-6_17</a>","ista":"Cheung YK, Henzinger MH, Hoefer M, Starnberger M. 2015. Combinatorial auctions with conflict-based externalities. 11th International Conference on Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 9470, 230–243.","mla":"Cheung, Yun Kuen, et al. “Combinatorial Auctions with Conflict-Based Externalities.” <i>11th International Conference on Web and Internet Economics</i>, vol. 9470, Springer Nature, 2015, pp. 230–243, doi:<a href=\"https://doi.org/10.1007/978-3-662-48995-6_17\">10.1007/978-3-662-48995-6_17</a>.","short":"Y.K. Cheung, M.H. Henzinger, M. Hoefer, M. Starnberger, in:, 11th International Conference on Web and Internet Economics, Springer Nature, 2015, pp. 230–243."},"date_updated":"2023-02-10T09:08:30Z","abstract":[{"lang":"eng","text":"Combinatorial auctions (CA) are a well-studied area in algorithmic mechanism design. However, contrary to the standard model, empirical studies suggest that a bidder’s valuation often does not depend solely on the goods assigned to him. For instance, in adwords auctions an advertiser might not want his ads to be displayed next to his competitors’ ads. In this paper, we propose and analyze several natural graph-theoretic models that incorporate such negative externalities, in which bidders form a directed conflict graph with maximum out-degree Δ. We design algorithms and truthful mechanisms for social welfare maximization that attain approximation ratios depending on Δ.\r\n\r\nFor CA, our results are twofold: (1) A lottery that eliminates conflicts by discarding bidders/items independent of the bids. It allows to apply any truthful 𝛼-approximation mechanism for conflict-free valuations and yields an 𝒪(𝛼Δ)-approximation mechanism. (2) For fractionally sub-additive valuations, we design a rounding algorithm via a novel combination of a semi-definite program and a linear program, resulting in a cone program; the approximation ratio is 𝒪((ΔloglogΔ)/logΔ). The ratios are almost optimal given existing hardness results.\r\n\r\nFor adwords auctions, we present several algorithms for the most relevant scenario when the number of items is small. In particular, we design a truthful mechanism with approximation ratio 𝑜(Δ) when the number of items is only logarithmic in the number of bidders."}],"day":"09","arxiv":1,"doi":"10.1007/978-3-662-48995-6_17","quality_controlled":"1","page":"230–243","publisher":"Springer Nature","author":[{"first_name":"Yun Kuen","last_name":"Cheung","full_name":"Cheung, Yun Kuen"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Hoefer, Martin","last_name":"Hoefer","first_name":"Martin"},{"first_name":"Martin","last_name":"Starnberger","full_name":"Starnberger, Martin"}],"scopus_import":"1","_id":"11774","intvolume":"      9470","title":"Combinatorial auctions with conflict-based externalities","alternative_title":["LNCS"],"date_created":"2022-08-08T13:54:32Z","article_processing_charge":"No","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1509.09147"}],"type":"conference","date_published":"2015-12-09T00:00:00Z","oa":1,"publication_identifier":{"eisbn":["9783662489956"],"issn":["0302-9743"],"isbn":["9783662489949"]},"language":[{"iso":"eng"}],"conference":{"name":"WINE: International Conference on Web and Internet Economics","start_date":"2015-12-09","location":"Amsterdam, Netherlands","end_date":"2015-12-12"},"publication":"11th International Conference on Web and Internet Economics","month":"12","oa_version":"Preprint"},{"oa":1,"publication_identifier":{"isbn":["9783662476710"],"issn":["0302-9743"]},"date_published":"2015-01-01T00:00:00Z","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"url":"https://arxiv.org/abs/1612.03856","open_access":"1"}],"month":"01","oa_version":"Preprint","publication":"42nd International Colloquium on Automata, Languages and Programming","conference":{"name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"2015-07-06","end_date":"2015-07-10","location":"Kyoto, Japan"},"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with 𝑜(𝑚𝑛) total update time, where 𝑚 is the number of edges and 𝑛 is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different 𝑚 vs. 𝑛 trade-off. For the case of 𝑚=Θ(𝑛1.5) the running time is 𝑂(𝑛2.47), just barely below 𝑚𝑛=Θ(𝑛2.5). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of 𝑂̃ (min(𝑚7/6𝑛2/3,𝑚3/4𝑛5/4+𝑜(1),𝑚2/3𝑛4/3+𝑜(1)+𝑚3/7𝑛12/7+𝑜(1))). This gives, e.g., 𝑂(𝑛2.36) for the notorious case 𝑚=Θ(𝑛1.5). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary."}],"arxiv":1,"doi":"10.1007/978-3-662-47672-7_59","day":"01","external_id":{"arxiv":["1612.03856"]},"date_updated":"2023-02-10T09:10:26Z","year":"2015","citation":{"chicago":"Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.” In <i>42nd International Colloquium on Automata, Languages and Programming</i>, 9134:725–36. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_59\">https://doi.org/10.1007/978-3-662-47672-7_59</a>.","ieee":"M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Improved algorithms for decremental single-source reachability on directed graphs,” in <i>42nd International Colloquium on Automata, Languages and Programming</i>, Kyoto, Japan, 2015, vol. 9134, pp. 725–736.","ama":"Henzinger MH, Krinninger S, Nanongkai D. Improved algorithms for decremental single-source reachability on directed graphs. In: <i>42nd International Colloquium on Automata, Languages and Programming</i>. Vol 9134. Springer Nature; 2015:725-736. doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_59\">10.1007/978-3-662-47672-7_59</a>","apa":"Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2015). Improved algorithms for decremental single-source reachability on directed graphs. In <i>42nd International Colloquium on Automata, Languages and Programming</i> (Vol. 9134, pp. 725–736). Kyoto, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_59\">https://doi.org/10.1007/978-3-662-47672-7_59</a>","ista":"Henzinger MH, Krinninger S, Nanongkai D. 2015. Improved algorithms for decremental single-source reachability on directed graphs. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 725–736.","mla":"Henzinger, Monika H., et al. “Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.” <i>42nd International Colloquium on Automata, Languages and Programming</i>, vol. 9134, Springer Nature, 2015, pp. 725–36, doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_59\">10.1007/978-3-662-47672-7_59</a>.","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 725–736."},"extern":"1","volume":9134,"alternative_title":["LNCS"],"title":"Improved algorithms for decremental single-source reachability on directed graphs","intvolume":"      9134","publication_status":"published","article_processing_charge":"No","date_created":"2022-08-11T08:51:32Z","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Krinninger","first_name":"Sebastian","full_name":"Krinninger, Sebastian"},{"full_name":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"}],"_id":"11785","scopus_import":"1","publisher":"Springer Nature","page":"725 - 736","quality_controlled":"1"},{"date_published":"2015-01-01T00:00:00Z","type":"conference","oa":1,"publication_identifier":{"isbn":["9783662476710"],"issn":["0302-9743"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.05337"}],"publication":"42nd International Colloquium on Automata, Languages and Programming","month":"01","oa_version":"Preprint","language":[{"iso":"eng"}],"conference":{"end_date":"2015-07-10","location":"Kyoto, Japan","start_date":"2015-07-06","name":"ICALP: International Colloquium on Automata, Languages, and Programming"},"external_id":{"arxiv":["1604.05337"]},"date_updated":"2023-02-10T09:13:31Z","citation":{"apa":"Bhattacharya, S., Henzinger, M. H., &#38; Italiano, G. F. (2015). Design of dynamic algorithms via primal-dual method. In <i>42nd International Colloquium on Automata, Languages and Programming</i> (Vol. 9134, pp. 206–218). Kyoto, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_17\">https://doi.org/10.1007/978-3-662-47672-7_17</a>","ama":"Bhattacharya S, Henzinger MH, Italiano GF. Design of dynamic algorithms via primal-dual method. In: <i>42nd International Colloquium on Automata, Languages and Programming</i>. Vol 9134. Springer Nature; 2015:206-218. doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_17\">10.1007/978-3-662-47672-7_17</a>","ieee":"S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Design of dynamic algorithms via primal-dual method,” in <i>42nd International Colloquium on Automata, Languages and Programming</i>, Kyoto, Japan, 2015, vol. 9134, pp. 206–218.","chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Design of Dynamic Algorithms via Primal-Dual Method.” In <i>42nd International Colloquium on Automata, Languages and Programming</i>, 9134:206–18. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_17\">https://doi.org/10.1007/978-3-662-47672-7_17</a>.","short":"S. Bhattacharya, M.H. Henzinger, G.F. Italiano, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 206–218.","mla":"Bhattacharya, Sayan, et al. “Design of Dynamic Algorithms via Primal-Dual Method.” <i>42nd International Colloquium on Automata, Languages and Programming</i>, vol. 9134, Springer Nature, 2015, pp. 206–18, doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_17\">10.1007/978-3-662-47672-7_17</a>.","ista":"Bhattacharya S, Henzinger MH, Italiano GF. 2015. Design of dynamic algorithms via primal-dual method. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 206–218."},"year":"2015","abstract":[{"text":"In this paper, 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 𝑂(𝑓2)-approximately optimal solution in 𝑂(𝑓⋅log(𝑚+𝑛)) amortized update time, where 𝑓 is the maximum “frequency” of an element, 𝑛 is the number of sets, and 𝑚 is the maximum number of elements in the universe at any point in time. (2) For the dynamic 𝑏-matching problem, we maintain an 𝑂(1)-approximately optimal solution in 𝑂(log3𝑛) amortized update time, where 𝑛 is the number of nodes in the graph.","lang":"eng"}],"arxiv":1,"doi":"10.1007/978-3-662-47672-7_17","day":"01","extern":"1","volume":9134,"author":[{"first_name":"Sayan","last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan"},{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Italiano, Giuseppe F.","first_name":"Giuseppe F.","last_name":"Italiano"}],"_id":"11786","scopus_import":"1","alternative_title":["LNCS"],"title":"Design of dynamic algorithms via primal-dual method","intvolume":"      9134","publication_status":"published","article_processing_charge":"No","date_created":"2022-08-11T09:28:49Z","page":"206 - 218","quality_controlled":"1","publisher":"Springer Nature"},{"extern":"1","volume":9134,"abstract":[{"lang":"eng","text":"We present faster algorithms for computing the 2-edge and 2-vertex strongly connected components of a directed graph. While in undirected graphs the 2-edge and 2-vertex connected components can be found in linear time, in directed graphs with m edges and n vertices only rather simple O(m n)-time algorithms were known. We use a hierarchical sparsification technique to obtain algorithms that run in time 𝑂(𝑛2). For 2-edge strongly connected components our algorithm gives the first running time improvement in 20 years. Additionally we present an 𝑂(𝑚2/log𝑛)-time algorithm for 2-edge strongly connected components, and thus improve over the O(m n) running time also when 𝑚=𝑂(𝑛). Our approach extends to k-edge and k-vertex strongly connected components for any constant k with a running time of 𝑂(𝑛2log𝑛) for k-edge-connectivity and 𝑂(𝑛3) for k-vertex-connectivity."}],"doi":"10.1007/978-3-662-47672-7_58","arxiv":1,"day":"06","external_id":{"arxiv":["1412.6466"]},"date_updated":"2023-02-10T09:21:47Z","citation":{"ista":"Henzinger MH, Krinninger S, Loitzenbauer V. 2015. Finding 2-edge and 2-vertex strongly connected components in quadratic time. 2nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 713–724.","short":"M.H. Henzinger, S. Krinninger, V. Loitzenbauer, in:, 2nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 713–724.","mla":"Henzinger, Monika H., et al. “Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” <i>2nd International Colloquium on Automata, Languages and Programming</i>, vol. 9134, Springer Nature, 2015, pp. 713–24, doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_58\">10.1007/978-3-662-47672-7_58</a>.","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Veronika Loitzenbauer. “Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” In <i>2nd International Colloquium on Automata, Languages and Programming</i>, 9134:713–24. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_58\">https://doi.org/10.1007/978-3-662-47672-7_58</a>.","ieee":"M. H. Henzinger, S. Krinninger, and V. Loitzenbauer, “Finding 2-edge and 2-vertex strongly connected components in quadratic time,” in <i>2nd International Colloquium on Automata, Languages and Programming</i>, Kyoto, Japan, 2015, vol. 9134, pp. 713–724.","apa":"Henzinger, M. H., Krinninger, S., &#38; Loitzenbauer, V. (2015). Finding 2-edge and 2-vertex strongly connected components in quadratic time. In <i>2nd International Colloquium on Automata, Languages and Programming</i> (Vol. 9134, pp. 713–724). Kyoto, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_58\">https://doi.org/10.1007/978-3-662-47672-7_58</a>","ama":"Henzinger MH, Krinninger S, Loitzenbauer V. Finding 2-edge and 2-vertex strongly connected components in quadratic time. In: <i>2nd International Colloquium on Automata, Languages and Programming</i>. Vol 9134. Springer Nature; 2015:713-724. doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_58\">10.1007/978-3-662-47672-7_58</a>"},"year":"2015","publisher":"Springer Nature","page":"713 - 724","quality_controlled":"1","alternative_title":["LNCS"],"title":"Finding 2-edge and 2-vertex strongly connected components in quadratic time","intvolume":"      9134","publication_status":"published","article_processing_charge":"No","date_created":"2022-08-11T09:38:34Z","author":[{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"full_name":"Loitzenbauer, Veronika","last_name":"Loitzenbauer","first_name":"Veronika"}],"_id":"11787","scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"url":"https://arxiv.org/abs/1412.6466","open_access":"1"}],"oa":1,"publication_identifier":{"issn":["0302-9743"],"isbn":["9783662476710"]},"date_published":"2015-07-06T00:00:00Z","type":"conference","conference":{"name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"2015-07-06","location":"Kyoto, Japan","end_date":"2015-07-10"},"language":[{"iso":"eng"}],"month":"07","oa_version":"Preprint","publication":"2nd International Colloquium on Automata, Languages and Programming"},{"volume":8952,"extern":"1","day":"01","arxiv":1,"doi":"10.1007/978-3-319-18263-6_14","abstract":[{"text":"Ad exchanges are becoming an increasingly popular way to sell advertisement slots on the internet. An ad exchange is basically a spot market for ad impressions. A publisher who has already signed contracts reserving advertisement impressions on his pages can choose between assigning a new ad impression for a new page view to a contracted advertiser or to sell it at an ad exchange. This leads to an online revenue maximization problem for the publisher. Given a new impression to sell decide whether (a) to assign it to a contracted advertiser and if so to which one or (b) to sell it at the ad exchange and if so at which reserve price. We make no assumptions about the distribution of the advertiser valuations that participate in the ad exchange and show that there exists a simple primal-dual based online algorithm, whose lower bound for the revenue converges to 𝑅𝐴𝐷𝑋+𝑅𝐴(1−1/𝑒), where 𝑅𝐴𝐷𝑋 is the revenue that the optimum algorithm achieves from the ad exchange and 𝑅𝐴 is the revenue that the optimum algorithm achieves from the contracted advertisers.","lang":"eng"}],"year":"2015","citation":{"chicago":"Dvořák, Wolfgang, and Monika H Henzinger. “Online Ad Assignment with an Ad Exchange.” In <i>12th International Workshop of Approximation and Online Algorithms</i>, 8952:156–167. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-319-18263-6_14\">https://doi.org/10.1007/978-3-319-18263-6_14</a>.","ieee":"W. Dvořák and M. H. Henzinger, “Online ad assignment with an ad exchange,” in <i>12th International Workshop of Approximation and Online Algorithms</i>, Wroclaw, Poland, 2015, vol. 8952, pp. 156–167.","ama":"Dvořák W, Henzinger MH. Online ad assignment with an ad exchange. In: <i>12th International Workshop of Approximation and Online Algorithms</i>. Vol 8952. Springer Nature; 2015:156–167. doi:<a href=\"https://doi.org/10.1007/978-3-319-18263-6_14\">10.1007/978-3-319-18263-6_14</a>","apa":"Dvořák, W., &#38; Henzinger, M. H. (2015). Online ad assignment with an ad exchange. In <i>12th International Workshop of Approximation and Online Algorithms</i> (Vol. 8952, pp. 156–167). Wroclaw, Poland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-319-18263-6_14\">https://doi.org/10.1007/978-3-319-18263-6_14</a>","ista":"Dvořák W, Henzinger MH. 2015. Online ad assignment with an ad exchange. 12th International Workshop of Approximation and Online Algorithms. WAOA: International Workshop on Approximation and Online Algorithms, LNCS, vol. 8952, 156–167.","mla":"Dvořák, Wolfgang, and Monika H. Henzinger. “Online Ad Assignment with an Ad Exchange.” <i>12th International Workshop of Approximation and Online Algorithms</i>, vol. 8952, Springer Nature, 2015, pp. 156–167, doi:<a href=\"https://doi.org/10.1007/978-3-319-18263-6_14\">10.1007/978-3-319-18263-6_14</a>.","short":"W. Dvořák, M.H. Henzinger, in:, 12th International Workshop of Approximation and Online Algorithms, Springer Nature, 2015, pp. 156–167."},"date_updated":"2023-02-10T09:26:06Z","external_id":{"arxiv":["1604.05603"]},"publisher":"Springer Nature","quality_controlled":"1","page":"156–167","article_processing_charge":"No","date_created":"2022-08-11T09:43:32Z","publication_status":"published","intvolume":"      8952","alternative_title":["LNCS"],"title":"Online ad assignment with an ad exchange","scopus_import":"1","_id":"11788","author":[{"last_name":"Dvořák","first_name":"Wolfgang","full_name":"Dvořák, Wolfgang"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"main_file_link":[{"url":"https://arxiv.org/abs/1604.05603","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publication_identifier":{"issn":["0302-9743"]},"oa":1,"type":"conference","date_published":"2015-01-01T00:00:00Z","conference":{"name":"WAOA: International Workshop on Approximation and Online Algorithms","start_date":"2014-09-11","location":"Wroclaw, Poland","end_date":"2014-09-12"},"language":[{"iso":"eng"}],"oa_version":"Preprint","month":"01","publication":"12th International Workshop of Approximation and Online Algorithms"},{"day":"01","doi":"10.1007/978-3-662-45803-7_36","arxiv":1,"abstract":[{"lang":"eng","text":"The Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this classical result to clustered graphs with two disjoint clusters, and show that a straightforward extension of our result to flat clustered graphs with three or more disjoint clusters is not possible.\r\n\r\nWe also give a new and short proof for a related result by Di Battista and Frati based on the matroid intersection algorithm."}],"citation":{"chicago":"Fulek, Radoslav, Jan Kynčl, Igor Malinović, and Dömötör Pálvölgyi. “Clustered Planarity Testing Revisited.” In <i>International Symposium on Graph Drawing</i>, 8871:428–36. Cham: Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-662-45803-7_36\">https://doi.org/10.1007/978-3-662-45803-7_36</a>.","ieee":"R. Fulek, J. Kynčl, I. Malinović, and D. Pálvölgyi, “Clustered planarity testing revisited,” in <i>International Symposium on Graph Drawing</i>, 2014, vol. 8871, pp. 428–436.","ama":"Fulek R, Kynčl J, Malinović I, Pálvölgyi D. Clustered planarity testing revisited. In: <i>International Symposium on Graph Drawing</i>. Vol 8871. Cham: Springer Nature; 2014:428-436. doi:<a href=\"https://doi.org/10.1007/978-3-662-45803-7_36\">10.1007/978-3-662-45803-7_36</a>","apa":"Fulek, R., Kynčl, J., Malinović, I., &#38; Pálvölgyi, D. (2014). Clustered planarity testing revisited. In <i>International Symposium on Graph Drawing</i> (Vol. 8871, pp. 428–436). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-45803-7_36\">https://doi.org/10.1007/978-3-662-45803-7_36</a>","ista":"Fulek R, Kynčl J, Malinović I, Pálvölgyi D. 2014. Clustered planarity testing revisited. International Symposium on Graph Drawing. , LNCS, vol. 8871, 428–436.","mla":"Fulek, Radoslav, et al. “Clustered Planarity Testing Revisited.” <i>International Symposium on Graph Drawing</i>, vol. 8871, Springer Nature, 2014, pp. 428–36, doi:<a href=\"https://doi.org/10.1007/978-3-662-45803-7_36\">10.1007/978-3-662-45803-7_36</a>.","short":"R. Fulek, J. Kynčl, I. Malinović, D. Pálvölgyi, in:, International Symposium on Graph Drawing, Springer Nature, Cham, 2014, pp. 428–436."},"year":"2014","date_updated":"2023-02-23T10:08:04Z","external_id":{"arxiv":["1305.4519"]},"volume":8871,"department":[{"_id":"UlWa"}],"date_created":"2022-02-25T10:32:14Z","article_processing_charge":"No","publication_status":"published","intvolume":"      8871","title":"Clustered planarity testing revisited","alternative_title":["LNCS"],"scopus_import":"1","_id":"10793","author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav"},{"full_name":"Kynčl, Jan","last_name":"Kynčl","first_name":"Jan"},{"first_name":"Igor","last_name":"Malinović","full_name":"Malinović, Igor"},{"last_name":"Pálvölgyi","first_name":"Dömötör","full_name":"Pálvölgyi, Dömötör"}],"publisher":"Springer Nature","quality_controlled":"1","page":"428-436","publication_identifier":{"issn":["0302-9743"]},"type":"conference","date_published":"2014-01-01T00:00:00Z","place":"Cham","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","id":"1642","relation":"later_version"}]},"status":"public","oa_version":"Preprint","month":"01","publication":"International Symposium on Graph Drawing","language":[{"iso":"eng"}]},{"author":[{"id":"4A55BD00-F248-11E8-B48F-1D18A9856A87","last_name":"Aminof","first_name":"Benjamin","full_name":"Aminof, Benjamin"},{"last_name":"Jacobs","first_name":"Swen","full_name":"Jacobs, Swen"},{"first_name":"Ayrat","last_name":"Khalimov","full_name":"Khalimov, Ayrat"},{"last_name":"Rubin","first_name":"Sasha","full_name":"Rubin, Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87"}],"_id":"10884","scopus_import":"1","alternative_title":["LNCS"],"title":"Parameterized model checking of token-passing systems","intvolume":"      8318","publication_status":"published","article_processing_charge":"No","date_created":"2022-03-18T13:01:22Z","department":[{"_id":"KrCh"}],"page":"262-281","ec_funded":1,"quality_controlled":"1","publisher":"Springer Nature","external_id":{"arxiv":["1311.4425"]},"date_updated":"2022-05-17T08:36:01Z","year":"2014","citation":{"ista":"Aminof B, Jacobs S, Khalimov A, Rubin S. 2014. Parameterized model checking of token-passing systems. Verification, Model Checking, and Abstract Interpretation. VMCAI: Verifcation, Model Checking, and Abstract Interpretation, LNCS, vol. 8318, 262–281.","short":"B. Aminof, S. Jacobs, A. Khalimov, S. Rubin, in:, Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2014, pp. 262–281.","mla":"Aminof, Benjamin, et al. “Parameterized Model Checking of Token-Passing Systems.” <i>Verification, Model Checking, and Abstract Interpretation</i>, vol. 8318, Springer Nature, 2014, pp. 262–81, doi:<a href=\"https://doi.org/10.1007/978-3-642-54013-4_15\">10.1007/978-3-642-54013-4_15</a>.","ieee":"B. Aminof, S. Jacobs, A. Khalimov, and S. Rubin, “Parameterized model checking of token-passing systems,” in <i>Verification, Model Checking, and Abstract Interpretation</i>, San Diego, CA, United States, 2014, vol. 8318, pp. 262–281.","chicago":"Aminof, Benjamin, Swen Jacobs, Ayrat Khalimov, and Sasha Rubin. “Parameterized Model Checking of Token-Passing Systems.” In <i>Verification, Model Checking, and Abstract Interpretation</i>, 8318:262–81. Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-642-54013-4_15\">https://doi.org/10.1007/978-3-642-54013-4_15</a>.","ama":"Aminof B, Jacobs S, Khalimov A, Rubin S. Parameterized model checking of token-passing systems. In: <i>Verification, Model Checking, and Abstract Interpretation</i>. Vol 8318. Springer Nature; 2014:262-281. doi:<a href=\"https://doi.org/10.1007/978-3-642-54013-4_15\">10.1007/978-3-642-54013-4_15</a>","apa":"Aminof, B., Jacobs, S., Khalimov, A., &#38; Rubin, S. (2014). Parameterized model checking of token-passing systems. In <i>Verification, Model Checking, and Abstract Interpretation</i> (Vol. 8318, pp. 262–281). San Diego, CA, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-642-54013-4_15\">https://doi.org/10.1007/978-3-642-54013-4_15</a>"},"abstract":[{"text":"We revisit the parameterized model checking problem for token-passing systems and specifications in indexed CTL  ∗ \\X. Emerson and Namjoshi (1995, 2003) have shown that parameterized model checking of indexed CTL  ∗ \\X in uni-directional token rings can be reduced to checking rings up to some cutoff size. Clarke et al. (2004) have shown a similar result for general topologies and indexed LTL \\X, provided processes cannot choose the directions for sending or receiving the token.\r\nWe unify and substantially extend these results by systematically exploring fragments of indexed CTL  ∗ \\X with respect to general topologies. For each fragment we establish whether a cutoff exists, and for some concrete topologies, such as rings, cliques and stars, we infer small cutoffs. Finally, we show that the problem becomes undecidable, and thus no cutoffs exist, if processes are allowed to choose the directions in which they send or from which they receive the token.","lang":"eng"}],"arxiv":1,"doi":"10.1007/978-3-642-54013-4_15","day":"30","acknowledgement":"This work was supported by the Austrian Science Fund through grant P23499-N23\r\nand through the RiSE network (S11403, S11405, S11406, S11407-N23); ERC Starting Grant (279307: Graph Games); Vienna Science and Technology Fund (WWTF)\r\ngrants PROSEED, ICT12-059, and VRG11-005.","volume":8318,"publication":"Verification, Model Checking, and Abstract Interpretation","month":"01","oa_version":"Preprint","project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"conference":{"name":"VMCAI: Verifcation, Model Checking, and Abstract Interpretation","start_date":"2014-01-19","end_date":"2014-01-21","location":"San Diego, CA, United States"},"date_published":"2014-01-30T00:00:00Z","type":"conference","oa":1,"publication_identifier":{"eisbn":["9783642540134"],"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783642540127"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.1311.4425"}]},{"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"id":"681","relation":"later_version","status":"public"}]},"publication_identifier":{"isbn":["9783642540127"],"eisbn":["9783642540134"],"eissn":["1611-3349"],"issn":["0302-9743"]},"date_published":"2014-01-30T00:00:00Z","type":"conference","conference":{"location":"San Diego, CA, United States","end_date":"2014-01-21","name":"VMCAI: Verifcation, Model Checking, and Abstract Interpretation","start_date":"2014-01-19"},"language":[{"iso":"eng"}],"month":"01","oa_version":"Preprint","project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"publication":"VMCAI 2014: Verification, Model Checking, and Abstract Interpretation","acknowledgement":" Supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No\r\nS11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","volume":8318,"abstract":[{"lang":"eng","text":"Two-player games on graphs provide the theoretical framework for many important problems such as reactive synthesis. While the traditional study of two-player zero-sum games has been extended to multi-player games with several notions of equilibria, they are decidable only for perfect-information games, whereas several applications require imperfect-information games.\r\nIn this paper we propose a new notion of equilibria, called doomsday equilibria, which is a strategy profile such that all players satisfy their own objective, and if any coalition of players deviates and violates even one of the players objective, then the objective of every player is violated.\r\nWe present algorithms and complexity results for deciding the existence of doomsday equilibria for various classes of ω-regular objectives, both for imperfect-information games, and for perfect-information games.We provide optimal complexity bounds for imperfect-information games, and in most cases for perfect-information games."}],"doi":"10.1007/978-3-642-54013-4_5","arxiv":1,"day":"30","external_id":{"arxiv":["1311.3238"]},"date_updated":"2023-02-23T12:52:24Z","citation":{"ista":"Chatterjee K, Doyen L, Filiot E, Raskin J-F. 2014. Doomsday equilibria for omega-regular games. VMCAI 2014: Verification, Model Checking, and Abstract Interpretation. VMCAI: Verifcation, Model Checking, and Abstract Interpretation, LNCS, vol. 8318, 78–97.","short":"K. Chatterjee, L. Doyen, E. Filiot, J.-F. Raskin, in:, VMCAI 2014: Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2014, pp. 78–97.","mla":"Chatterjee, Krishnendu, et al. “Doomsday Equilibria for Omega-Regular Games.” <i>VMCAI 2014: Verification, Model Checking, and Abstract Interpretation</i>, vol. 8318, Springer Nature, 2014, pp. 78–97, doi:<a href=\"https://doi.org/10.1007/978-3-642-54013-4_5\">10.1007/978-3-642-54013-4_5</a>.","ieee":"K. Chatterjee, L. Doyen, E. Filiot, and J.-F. Raskin, “Doomsday equilibria for omega-regular games,” in <i>VMCAI 2014: Verification, Model Checking, and Abstract Interpretation</i>, San Diego, CA, United States, 2014, vol. 8318, pp. 78–97.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Emmanuel Filiot, and Jean-François Raskin. “Doomsday Equilibria for Omega-Regular Games.” In <i>VMCAI 2014: Verification, Model Checking, and Abstract Interpretation</i>, 8318:78–97. Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-642-54013-4_5\">https://doi.org/10.1007/978-3-642-54013-4_5</a>.","apa":"Chatterjee, K., Doyen, L., Filiot, E., &#38; Raskin, J.-F. (2014). Doomsday equilibria for omega-regular games. In <i>VMCAI 2014: Verification, Model Checking, and Abstract Interpretation</i> (Vol. 8318, pp. 78–97). San Diego, CA, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-642-54013-4_5\">https://doi.org/10.1007/978-3-642-54013-4_5</a>","ama":"Chatterjee K, Doyen L, Filiot E, Raskin J-F. Doomsday equilibria for omega-regular games. In: <i>VMCAI 2014: Verification, Model Checking, and Abstract Interpretation</i>. Vol 8318. Springer Nature; 2014:78-97. doi:<a href=\"https://doi.org/10.1007/978-3-642-54013-4_5\">10.1007/978-3-642-54013-4_5</a>"},"year":"2014","publisher":"Springer Nature","page":"78-97","quality_controlled":"1","ec_funded":1,"title":"Doomsday equilibria for omega-regular games","alternative_title":["LNCS"],"intvolume":"      8318","publication_status":"published","department":[{"_id":"KrCh"}],"date_created":"2022-03-18T13:03:15Z","article_processing_charge":"No","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"},{"last_name":"Filiot","first_name":"Emmanuel","full_name":"Filiot, Emmanuel"},{"full_name":"Raskin, Jean-François","first_name":"Jean-François","last_name":"Raskin"}],"_id":"10885","scopus_import":"1"},{"quality_controlled":"1","page":"117-127","publisher":"Springer Nature","author":[{"first_name":"Therese","last_name":"Biedl","full_name":"Biedl, Therese"},{"id":"4700A070-F248-11E8-B48F-1D18A9856A87","first_name":"Stefan","last_name":"Huber","orcid":"0000-0002-8871-5814","full_name":"Huber, Stefan"},{"full_name":"Palfrader, Peter","first_name":"Peter","last_name":"Palfrader"}],"scopus_import":"1","_id":"10892","intvolume":"      8889","title":"Planar matchings for weighted straight skeletons","alternative_title":["LNCS"],"date_created":"2022-03-21T07:09:03Z","article_processing_charge":"No","department":[{"_id":"HeEd"}],"publication_status":"published","volume":8889,"acknowledgement":"T. Biedl was supported by NSERC and the Ross and Muriel Cheriton Fellowship. P. Palfrader was supported by Austrian Science Fund (FWF): P25816-N15.","year":"2014","citation":{"ista":"Biedl T, Huber S, Palfrader P. 2014. Planar matchings for weighted straight skeletons. 25th International Symposium, ISAAC 2014. ISAAC: International Symposium on Algorithms and Computation, LNCS, vol. 8889, 117–127.","short":"T. Biedl, S. Huber, P. Palfrader, in:, 25th International Symposium, ISAAC 2014, Springer Nature, 2014, pp. 117–127.","mla":"Biedl, Therese, et al. “Planar Matchings for Weighted Straight Skeletons.” <i>25th International Symposium, ISAAC 2014</i>, vol. 8889, Springer Nature, 2014, pp. 117–27, doi:<a href=\"https://doi.org/10.1007/978-3-319-13075-0_10\">10.1007/978-3-319-13075-0_10</a>.","chicago":"Biedl, Therese, Stefan Huber, and Peter Palfrader. “Planar Matchings for Weighted Straight Skeletons.” In <i>25th International Symposium, ISAAC 2014</i>, 8889:117–27. Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-319-13075-0_10\">https://doi.org/10.1007/978-3-319-13075-0_10</a>.","ieee":"T. Biedl, S. Huber, and P. Palfrader, “Planar matchings for weighted straight skeletons,” in <i>25th International Symposium, ISAAC 2014</i>, Jeonju, Korea, 2014, vol. 8889, pp. 117–127.","apa":"Biedl, T., Huber, S., &#38; Palfrader, P. (2014). Planar matchings for weighted straight skeletons. In <i>25th International Symposium, ISAAC 2014</i> (Vol. 8889, pp. 117–127). Jeonju, Korea: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-319-13075-0_10\">https://doi.org/10.1007/978-3-319-13075-0_10</a>","ama":"Biedl T, Huber S, Palfrader P. Planar matchings for weighted straight skeletons. In: <i>25th International Symposium, ISAAC 2014</i>. Vol 8889. Springer Nature; 2014:117-127. doi:<a href=\"https://doi.org/10.1007/978-3-319-13075-0_10\">10.1007/978-3-319-13075-0_10</a>"},"date_updated":"2023-02-23T12:20:55Z","abstract":[{"lang":"eng","text":"In this paper, we introduce planar matchings on directed pseudo-line arrangements, which yield a planar set of pseudo-line segments such that only matching-partners are adjacent. By translating the planar matching problem into a corresponding stable roommates problem we show that such matchings always exist.\r\nUsing our new framework, we establish, for the first time, a complete, rigorous definition of weighted straight skeletons, which are based on a so-called wavefront propagation process. We present a generalized and unified approach to treat structural changes in the wavefront that focuses on the restoration of weak planarity by finding planar matchings."}],"day":"08","doi":"10.1007/978-3-319-13075-0_10","language":[{"iso":"eng"}],"conference":{"start_date":"2014-12-15","name":"ISAAC: International Symposium on Algorithms and Computation","end_date":"2014-12-17","location":"Jeonju, Korea"},"publication":"25th International Symposium, ISAAC 2014","month":"11","oa_version":"None","related_material":{"record":[{"status":"public","relation":"later_version","id":"481"}]},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","date_published":"2014-11-08T00:00:00Z","publication_identifier":{"eisbn":["9783319130750"],"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783319130743"]}},{"abstract":[{"text":"PHAT is a C++ library for the computation of persistent homology by matrix reduction. We aim for a simple generic design that decouples algorithms from data structures without sacrificing efficiency or user-friendliness. This makes PHAT a versatile platform for experimenting with algorithmic ideas and comparing them to state of the art implementations.","lang":"eng"}],"doi":"10.1007/978-3-662-44199-2_24","day":"01","date_updated":"2023-09-20T09:42:40Z","citation":{"ieee":"U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner, “PHAT – Persistent Homology Algorithms Toolbox,” in <i>ICMS 2014: International Congress on Mathematical Software</i>, Seoul, South Korea, 2014, vol. 8592, pp. 137–143.","chicago":"Bauer, Ulrich, Michael Kerber, Jan Reininghaus, and Hubert Wagner. “PHAT – Persistent Homology Algorithms Toolbox.” In <i>ICMS 2014: International Congress on Mathematical Software</i>, 8592:137–43. LNCS. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014. <a href=\"https://doi.org/10.1007/978-3-662-44199-2_24\">https://doi.org/10.1007/978-3-662-44199-2_24</a>.","apa":"Bauer, U., Kerber, M., Reininghaus, J., &#38; Wagner, H. (2014). PHAT – Persistent Homology Algorithms Toolbox. In <i>ICMS 2014: International Congress on Mathematical Software</i> (Vol. 8592, pp. 137–143). Berlin, Heidelberg: Springer Berlin Heidelberg. <a href=\"https://doi.org/10.1007/978-3-662-44199-2_24\">https://doi.org/10.1007/978-3-662-44199-2_24</a>","ama":"Bauer U, Kerber M, Reininghaus J, Wagner H. PHAT – Persistent Homology Algorithms Toolbox. In: <i>ICMS 2014: International Congress on Mathematical Software</i>. Vol 8592. LNCS. Berlin, Heidelberg: Springer Berlin Heidelberg; 2014:137-143. doi:<a href=\"https://doi.org/10.1007/978-3-662-44199-2_24\">10.1007/978-3-662-44199-2_24</a>","ista":"Bauer U, Kerber M, Reininghaus J, Wagner H. 2014. PHAT – Persistent Homology Algorithms Toolbox. ICMS 2014: International Congress on Mathematical Software. ICMS: International Congress on Mathematical SoftwareLNCS vol. 8592, 137–143.","mla":"Bauer, Ulrich, et al. “PHAT – Persistent Homology Algorithms Toolbox.” <i>ICMS 2014: International Congress on Mathematical Software</i>, vol. 8592, Springer Berlin Heidelberg, 2014, pp. 137–43, doi:<a href=\"https://doi.org/10.1007/978-3-662-44199-2_24\">10.1007/978-3-662-44199-2_24</a>.","short":"U. Bauer, M. Kerber, J. Reininghaus, H. Wagner, in:, ICMS 2014: International Congress on Mathematical Software, Springer Berlin Heidelberg, Berlin, Heidelberg, 2014, pp. 137–143."},"year":"2014","volume":8592,"title":"PHAT – Persistent Homology Algorithms Toolbox","intvolume":"      8592","publication_status":"published","department":[{"_id":"HeEd"}],"article_processing_charge":"No","date_created":"2022-03-21T07:12:16Z","author":[{"id":"2ADD483A-F248-11E8-B48F-1D18A9856A87","first_name":"Ulrich","last_name":"Bauer","orcid":"0000-0002-9683-0724","full_name":"Bauer, Ulrich"},{"last_name":"Kerber","first_name":"Michael","full_name":"Kerber, Michael"},{"full_name":"Reininghaus, Jan","first_name":"Jan","last_name":"Reininghaus","id":"4505473A-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Wagner","first_name":"Hubert","full_name":"Wagner, Hubert"}],"_id":"10894","scopus_import":"1","publisher":"Springer Berlin Heidelberg","page":"137-143","series_title":"LNCS","quality_controlled":"1","publication_identifier":{"isbn":["9783662441985"],"eisbn":["9783662441992"],"eissn":["1611-3349"],"issn":["0302-9743"]},"date_published":"2014-09-01T00:00:00Z","type":"conference","status":"public","related_material":{"record":[{"status":"public","relation":"later_version","id":"1433"}]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","place":"Berlin, Heidelberg","month":"09","oa_version":"None","publication":"ICMS 2014: International Congress on Mathematical Software","conference":{"end_date":"2014-08-09","location":"Seoul, South Korea","start_date":"2014-08-05","name":"ICMS: International Congress on Mathematical Software"},"language":[{"iso":"eng"}]},{"scopus_import":"1","_id":"11789","author":[{"full_name":"Charikar, Moses","first_name":"Moses","last_name":"Charikar"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Huy L.","last_name":"Nguyễn","full_name":"Nguyễn, Huy L."}],"date_created":"2022-08-11T10:41:47Z","article_processing_charge":"No","publication_status":"published","intvolume":"      8737","alternative_title":["LNCS"],"title":"Online bipartite matching with decomposable weights","quality_controlled":"1","page":"260 - 271","publisher":"Springer Nature","year":"2014","citation":{"short":"M. Charikar, M.H. Henzinger, H.L. Nguyễn, in:, 22nd Annual European Symposium on Algorithms, Springer Nature, 2014, pp. 260–271.","mla":"Charikar, Moses, et al. “Online Bipartite Matching with Decomposable Weights.” <i>22nd Annual European Symposium on Algorithms</i>, vol. 8737, Springer Nature, 2014, pp. 260–71, doi:<a href=\"https://doi.org/10.1007/978-3-662-44777-2_22\">10.1007/978-3-662-44777-2_22</a>.","ista":"Charikar M, Henzinger MH, Nguyễn HL. 2014. Online bipartite matching with decomposable weights. 22nd Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LNCS, vol. 8737, 260–271.","ama":"Charikar M, Henzinger MH, Nguyễn HL. Online bipartite matching with decomposable weights. In: <i>22nd Annual European Symposium on Algorithms</i>. Vol 8737. Springer Nature; 2014:260-271. doi:<a href=\"https://doi.org/10.1007/978-3-662-44777-2_22\">10.1007/978-3-662-44777-2_22</a>","apa":"Charikar, M., Henzinger, M. H., &#38; Nguyễn, H. L. (2014). Online bipartite matching with decomposable weights. In <i>22nd Annual European Symposium on Algorithms</i> (Vol. 8737, pp. 260–271). Wroclaw, Poland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-44777-2_22\">https://doi.org/10.1007/978-3-662-44777-2_22</a>","chicago":"Charikar, Moses, Monika H Henzinger, and Huy L. Nguyễn. “Online Bipartite Matching with Decomposable Weights.” In <i>22nd Annual European Symposium on Algorithms</i>, 8737:260–71. Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-662-44777-2_22\">https://doi.org/10.1007/978-3-662-44777-2_22</a>.","ieee":"M. Charikar, M. H. Henzinger, and H. L. Nguyễn, “Online bipartite matching with decomposable weights,” in <i>22nd Annual European Symposium on Algorithms</i>, Wroclaw, Poland, 2014, vol. 8737, pp. 260–271."},"date_updated":"2023-02-13T11:16:24Z","external_id":{"arxiv":["1409.2139"]},"day":"01","doi":"10.1007/978-3-662-44777-2_22","arxiv":1,"abstract":[{"lang":"eng","text":"We study a weighted online bipartite matching problem: G(V 1, V 2, E) is a weighted bipartite graph where V 1 is known beforehand and the vertices of V 2 arrive online. The goal is to match vertices of V 2 as they arrive to vertices in V 1, so as to maximize the sum of weights of edges in the matching. If assignments to V 1 cannot be changed, no bounded competitive ratio is achievable. We study the weighted online matching problem with free disposal, where vertices in V 1 can be assigned multiple times, but only get credit for the maximum weight edge assigned to them over the course of the algorithm. For this problem, the greedy algorithm is 0.5-competitive and determining whether a better competitive ratio is achievable is a well known open problem.\r\n\r\nWe identify an interesting special case where the edge weights are decomposable as the product of two factors, one corresponding to each end point of the edge. This is analogous to the well studied related machines model in the scheduling literature, although the objective functions are different. For this case of decomposable edge weights, we design a 0.5664 competitive randomized algorithm in complete bipartite graphs. We show that such instances with decomposable weights are non-trivial by establishing upper bounds of 0.618 for deterministic and 0.8 for randomized algorithms.\r\n\r\nA tight competitive ratio of 1 − 1/e ≈ 0.632 was known previously for both the 0-1 case as well as the case where edge weights depend on the offline vertices only, but for these cases, reassignments cannot change the quality of the solution. Beating 0.5 for weighted matching where reassignments are necessary has been a significant challenge. We thus give the first online algorithm with competitive ratio strictly better than 0.5 for a non-trivial case of weighted matching with free disposal."}],"volume":8737,"extern":"1","publication":"22nd Annual European Symposium on Algorithms","oa_version":"Preprint","month":"09","language":[{"iso":"eng"}],"conference":{"end_date":"2014-09-10","location":"Wroclaw, Poland","start_date":"2014-09-08","name":"ESA: Annual European Symposium on Algorithms"},"type":"conference","date_published":"2014-09-01T00:00:00Z","publication_identifier":{"issn":["0302-9743"],"isbn":["978-366244776-5"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1409.2139"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public"},{"author":[{"full_name":"Cigler, Luděk","first_name":"Luděk","last_name":"Cigler"},{"first_name":"Wolfgang","last_name":"Dvořák","full_name":"Dvořák, Wolfgang"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Starnberger, Martin","last_name":"Starnberger","first_name":"Martin"}],"_id":"11790","publication":"10th International Conference of Web and Internet Economics","scopus_import":"1","alternative_title":["LNCS"],"title":"Limiting price discrimination when selling products with positive network externalities","month":"12","intvolume":"      8877","publication_status":"published","oa_version":"None","article_processing_charge":"No","date_created":"2022-08-11T10:58:44Z","language":[{"iso":"eng"}],"page":"44 - 57","quality_controlled":"1","conference":{"end_date":"2014-12-17","location":"Beijing, China","name":"WINE: International Conference on Web and Internet Economics","start_date":"2014-12-14"},"publisher":"Springer Nature","date_published":"2014-12-01T00:00:00Z","type":"conference","date_updated":"2023-02-13T11:18:30Z","citation":{"ista":"Cigler L, Dvořák W, Henzinger MH, Starnberger M. 2014. Limiting price discrimination when selling products with positive network externalities. 10th International Conference of Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 8877, 44–57.","short":"L. Cigler, W. Dvořák, M.H. Henzinger, M. Starnberger, in:, 10th International Conference of Web and Internet Economics, Springer Nature, 2014, pp. 44–57.","mla":"Cigler, Luděk, et al. “Limiting Price Discrimination When Selling Products with Positive Network Externalities.” <i>10th International Conference of Web and Internet Economics</i>, vol. 8877, Springer Nature, 2014, pp. 44–57, doi:<a href=\"https://doi.org/10.1007/978-3-319-13129-0_4\">10.1007/978-3-319-13129-0_4</a>.","ieee":"L. Cigler, W. Dvořák, M. H. Henzinger, and M. Starnberger, “Limiting price discrimination when selling products with positive network externalities,” in <i>10th International Conference of Web and Internet Economics</i>, Beijing, China, 2014, vol. 8877, pp. 44–57.","chicago":"Cigler, Luděk, Wolfgang Dvořák, Monika H Henzinger, and Martin Starnberger. “Limiting Price Discrimination When Selling Products with Positive Network Externalities.” In <i>10th International Conference of Web and Internet Economics</i>, 8877:44–57. Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-319-13129-0_4\">https://doi.org/10.1007/978-3-319-13129-0_4</a>.","ama":"Cigler L, Dvořák W, Henzinger MH, Starnberger M. Limiting price discrimination when selling products with positive network externalities. In: <i>10th International Conference of Web and Internet Economics</i>. Vol 8877. Springer Nature; 2014:44-57. doi:<a href=\"https://doi.org/10.1007/978-3-319-13129-0_4\">10.1007/978-3-319-13129-0_4</a>","apa":"Cigler, L., Dvořák, W., Henzinger, M. H., &#38; Starnberger, M. (2014). Limiting price discrimination when selling products with positive network externalities. In <i>10th International Conference of Web and Internet Economics</i> (Vol. 8877, pp. 44–57). Beijing, China: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-319-13129-0_4\">https://doi.org/10.1007/978-3-319-13129-0_4</a>"},"year":"2014","abstract":[{"lang":"eng","text":"Assume a seller wants to sell a digital product in a social network where a buyer’s valuation of the item has positive network externalities from her neighbors that already have the item. The goal of the seller is to maximize his revenue. Previous work on this problem [7] studies the case where clients are offered the item in sequence and have to pay personalized prices. This is highly infeasible in large scale networks such as the Facebook graph: (1) Offering items to the clients one after the other consumes a large amount of time, and (2) price-discrimination of clients could appear unfair to them and result in negative client reaction or could conflict with legal requirements.\r\n\r\nWe study a setting dealing with these issues. Specifically, the item is offered in parallel to multiple clients at the same time and at the same price. This is called a round. We show that with O(logn) rounds, where n is the number of clients, a constant factor of the revenue with price discrimination can be achieved and that this is not possible with o(logn) rounds. Moreover we show that it is APX-hard to maximize the revenue and we give constant factor approximation algorithms for various further settings of limited price discrimination."}],"doi":"10.1007/978-3-319-13129-0_4","publication_identifier":{"issn":["0302-9743"]},"day":"01","extern":"1","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":8877},{"place":"Berlin, Heidelberg","volume":8668,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","extern":"1","citation":{"short":"R. Biswas, P. Bhowmick, 8668 (2014) 396–409.","mla":"Biswas, Ranita, and Partha Bhowmick. <i>On Finding Spherical Geodesic Paths and Circles in ℤ3</i>. Vol. 8668, Springer, 2014, pp. 396–409, doi:<a href=\"https://doi.org/10.1007/978-3-319-09955-2_33\">10.1007/978-3-319-09955-2_33</a>.","ista":"Biswas R, Bhowmick P. 2014. On Finding Spherical Geodesic Paths and Circles in ℤ3. 8668, 396–409.","apa":"Biswas, R., &#38; Bhowmick, P. (2014). On Finding Spherical Geodesic Paths and Circles in ℤ3. Presented at the DGCI: International Conference on Discrete Geometry for Computer Imagery, Berlin, Heidelberg: Springer. <a href=\"https://doi.org/10.1007/978-3-319-09955-2_33\">https://doi.org/10.1007/978-3-319-09955-2_33</a>","ama":"Biswas R, Bhowmick P. On Finding Spherical Geodesic Paths and Circles in ℤ3. 2014;8668:396-409. doi:<a href=\"https://doi.org/10.1007/978-3-319-09955-2_33\">10.1007/978-3-319-09955-2_33</a>","chicago":"Biswas, Ranita, and Partha Bhowmick. “On Finding Spherical Geodesic Paths and Circles in ℤ3.” Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-319-09955-2_33\">https://doi.org/10.1007/978-3-319-09955-2_33</a>.","ieee":"R. Biswas and P. Bhowmick, “On Finding Spherical Geodesic Paths and Circles in ℤ3,” vol. 8668. Springer, Berlin, Heidelberg, pp. 396–409, 2014."},"year":"2014","date_updated":"2019-01-24T13:22:49Z","type":"conference","date_published":"2014-01-01T00:00:00Z","publication_identifier":{"isbn":["9783642387081","9783642387098"],"issn":["0302-9743","1611-3349"]},"doi":"10.1007/978-3-319-09955-2_33","abstract":[{"lang":"eng","text":"A discrete spherical geodesic path between two voxels s and t lying on a discrete sphere is a/the 1-connected shortest path from s to t, comprising voxels of the discrete sphere intersected by the real plane passing through s, t, and the center of the sphere. We show that the set of sphere voxels intersected by the aforesaid real plane always contains a 1-connected cycle passing through s and t, and each voxel in this set lies within an isothetic distance of 32 from the concerned plane. Hence, to compute the path, the algorithm starts from s, and iteratively computes each voxel p of the path from the predecessor of p. A novel number-theoretic property and the 48-symmetry of discrete sphere are used for searching the 1-connected voxels comprising the path. The algorithm is output-sensitive, having its time and space complexities both linear in the length of the path. It can be extended for constructing 1-connected discrete 3D circles of arbitrary orientations, specified by a few appropriate input parameters. Experimental results and related analysis demonstrate its efficiency and versatility."}],"quality_controlled":"1","series_title":"Lecture Notes in Computer Science","page":"396-409","language":[{"iso":"eng"}],"publisher":"Springer","conference":{"start_date":"2014-09-10","name":"DGCI: International Conference on Discrete Geometry for Computer Imagery","end_date":"2014-09-12","location":"Siena, Italy"},"_id":"5810","author":[{"id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","last_name":"Biswas","first_name":"Ranita","full_name":"Biswas, Ranita","orcid":"0000-0002-5372-7890"},{"full_name":"Bhowmick, Partha","first_name":"Partha","last_name":"Bhowmick"}],"date_created":"2019-01-08T20:45:32Z","publication_status":"published","oa_version":"None","intvolume":"      8668","title":"On Finding Spherical Geodesic Paths and Circles in ℤ3"},{"acknowledgement":"This research is partially supported by the European Science Foundation (ESF) under the Research Network Programme, the European Union under the Toposys Project FP7-ICT-318493-STREP, the Russian Government under the Mega Project 11.G34.31.0053.","volume":7877,"doi":"10.1007/978-3-642-38221-5_19","day":"01","abstract":[{"lang":"eng","text":"Taking images is an efficient way to collect data about the physical world. It can be done fast and in exquisite detail. By definition, image processing is the field that concerns itself with the computation aimed at harnessing the information contained in images [10]. This talk is concerned with topological information. Our main thesis is that persistent homology [5] is a useful method to quantify and summarize topological information, building a bridge that connects algebraic topology with applications. We provide supporting evidence for this thesis by touching upon four technical developments in the overlap between persistent homology and image processing."}],"date_updated":"2023-09-05T15:10:20Z","year":"2013","citation":{"ista":"Edelsbrunner H. 2013. Persistent homology in image processing. Graph-Based Representations in Pattern Recognition. GbRPR: Graph-based Representations in Pattern RecognitionLNCS vol. 7877, 182–183.","short":"H. Edelsbrunner, in:, Graph-Based Representations in Pattern Recognition, Springer Nature, Berlin, Heidelberg, 2013, pp. 182–183.","mla":"Edelsbrunner, Herbert. “Persistent Homology in Image Processing.” <i>Graph-Based Representations in Pattern Recognition</i>, vol. 7877, Springer Nature, 2013, pp. 182–83, doi:<a href=\"https://doi.org/10.1007/978-3-642-38221-5_19\">10.1007/978-3-642-38221-5_19</a>.","chicago":"Edelsbrunner, Herbert. “Persistent Homology in Image Processing.” In <i>Graph-Based Representations in Pattern Recognition</i>, 7877:182–83. LNCS. Berlin, Heidelberg: Springer Nature, 2013. <a href=\"https://doi.org/10.1007/978-3-642-38221-5_19\">https://doi.org/10.1007/978-3-642-38221-5_19</a>.","ieee":"H. Edelsbrunner, “Persistent homology in image processing,” in <i>Graph-Based Representations in Pattern Recognition</i>, Vienna, Austria, 2013, vol. 7877, pp. 182–183.","apa":"Edelsbrunner, H. (2013). Persistent homology in image processing. In <i>Graph-Based Representations in Pattern Recognition</i> (Vol. 7877, pp. 182–183). Berlin, Heidelberg: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-642-38221-5_19\">https://doi.org/10.1007/978-3-642-38221-5_19</a>","ama":"Edelsbrunner H. Persistent homology in image processing. In: <i>Graph-Based Representations in Pattern Recognition</i>. Vol 7877. LNCS. Berlin, Heidelberg: Springer Nature; 2013:182-183. doi:<a href=\"https://doi.org/10.1007/978-3-642-38221-5_19\">10.1007/978-3-642-38221-5_19</a>"},"publisher":"Springer Nature","page":"182-183","series_title":"LNCS","quality_controlled":"1","ec_funded":1,"publication_status":"published","department":[{"_id":"HeEd"}],"date_created":"2022-03-21T07:30:33Z","article_processing_charge":"No","title":"Persistent homology in image processing","intvolume":"      7877","_id":"10897","scopus_import":"1","author":[{"first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"place":"Berlin, Heidelberg","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_identifier":{"isbn":["9783642382208"],"eisbn":["9783642382215"],"issn":["0302-9743"],"eissn":["1611-3349"]},"date_published":"2013-06-01T00:00:00Z","type":"conference","conference":{"location":"Vienna, Austria","end_date":"2013-05-17","name":"GbRPR: Graph-based Representations in Pattern Recognition","start_date":"2013-05-15"},"language":[{"iso":"eng"}],"oa_version":"None","project":[{"grant_number":"318493","name":"Topological Complex Systems","_id":"255D761E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"month":"06","publication":"Graph-Based Representations in Pattern Recognition"},{"acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award. Thanks to Gabriele Puppis for suggesting the problem of identifying a deterministic transducer to compute the optimal cost, and to Martin Chmelik for his comments on the introduction.","volume":7810,"abstract":[{"text":"We consider how to edit strings from a source language so that the edited strings belong to a target language, where the languages are given as deterministic finite automata. Non-streaming (or offline) transducers perform edits given the whole source string. We show that the class of deterministic one-pass transducers with registers along with increment and min operation suffices for computing optimal edit distance, whereas the same class of transducers without the min operation is not sufficient. Streaming (or online) transducers perform edits as the letters of the source string are received. We present a polynomial time algorithm for the partial-repair problem that given a bound α asks for the construction of a deterministic streaming transducer (if one exists) that ensures that the ‘maximum fraction’ η of the strings of the source language are edited, within cost α, to the target language.","lang":"eng"}],"doi":"10.1007/978-3-642-37064-9_20","day":"15","date_updated":"2023-09-05T15:10:38Z","citation":{"short":"K. Chatterjee, S. Chaubal, S. Rubin, in:, 7th International Conference on Language and Automata Theory and Applications, Springer Nature, Berlin, Heidelberg, 2013, pp. 214–225.","mla":"Chatterjee, Krishnendu, et al. “How to Travel between Languages.” <i>7th International Conference on Language and Automata Theory and Applications</i>, vol. 7810, Springer Nature, 2013, pp. 214–25, doi:<a href=\"https://doi.org/10.1007/978-3-642-37064-9_20\">10.1007/978-3-642-37064-9_20</a>.","ista":"Chatterjee K, Chaubal S, Rubin S. 2013. How to travel between languages. 7th International Conference on Language and Automata Theory and Applications. LATA: Conference on Language and Automata Theory and ApplicationsLNCS, LNCS, vol. 7810, 214–225.","ama":"Chatterjee K, Chaubal S, Rubin S. How to travel between languages. In: <i>7th International Conference on Language and Automata Theory and Applications</i>. Vol 7810. LNCS. Berlin, Heidelberg: Springer Nature; 2013:214-225. doi:<a href=\"https://doi.org/10.1007/978-3-642-37064-9_20\">10.1007/978-3-642-37064-9_20</a>","apa":"Chatterjee, K., Chaubal, S., &#38; Rubin, S. (2013). How to travel between languages. In <i>7th International Conference on Language and Automata Theory and Applications</i> (Vol. 7810, pp. 214–225). Berlin, Heidelberg: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-642-37064-9_20\">https://doi.org/10.1007/978-3-642-37064-9_20</a>","chicago":"Chatterjee, Krishnendu, Siddhesh Chaubal, and Sasha Rubin. “How to Travel between Languages.” In <i>7th International Conference on Language and Automata Theory and Applications</i>, 7810:214–25. LNCS. Berlin, Heidelberg: Springer Nature, 2013. <a href=\"https://doi.org/10.1007/978-3-642-37064-9_20\">https://doi.org/10.1007/978-3-642-37064-9_20</a>.","ieee":"K. Chatterjee, S. Chaubal, and S. Rubin, “How to travel between languages,” in <i>7th International Conference on Language and Automata Theory and Applications</i>, Bilbao, Spain, 2013, vol. 7810, pp. 214–225."},"year":"2013","publisher":"Springer Nature","page":"214-225","ec_funded":1,"series_title":"LNCS","quality_controlled":"1","title":"How to travel between languages","alternative_title":["LNCS"],"intvolume":"      7810","publication_status":"published","date_created":"2022-03-21T07:56:21Z","article_processing_charge":"No","department":[{"_id":"KrCh"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Siddhesh","last_name":"Chaubal","full_name":"Chaubal, Siddhesh"},{"full_name":"Rubin, Sasha","last_name":"Rubin","first_name":"Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87"}],"_id":"10902","scopus_import":"1","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","place":"Berlin, Heidelberg","publication_identifier":{"isbn":["9783642370632"],"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["9783642370649"]},"date_published":"2013-04-15T00:00:00Z","type":"conference","conference":{"end_date":"2013-04-05","location":"Bilbao, Spain","start_date":"2013-04-02","name":"LATA: Conference on Language and Automata Theory and Applications"},"language":[{"iso":"eng"}],"month":"04","oa_version":"None","project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Game Theory","grant_number":"S11407"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"publication":"7th International Conference on Language and Automata Theory and Applications"},{"volume":8044,"ddc":["005"],"doi":"10.1007/978-3-642-39799-8_11","date_updated":"2023-09-05T14:16:07Z","year":"2013","citation":{"short":"C. Dragoi, A. Gupta, T.A. Henzinger, in:, Computer Aided Verification, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013, pp. 174–190.","mla":"Dragoi, Cezara, et al. “Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates.” <i>Computer Aided Verification</i>, vol. 8044, Springer Berlin Heidelberg, 2013, pp. 174–90, doi:<a href=\"https://doi.org/10.1007/978-3-642-39799-8_11\">10.1007/978-3-642-39799-8_11</a>.","ista":"Dragoi C, Gupta A, Henzinger TA. 2013.Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates. In: Computer Aided Verification. vol. 8044, 174–190.","apa":"Dragoi, C., Gupta, A., &#38; Henzinger, T. A. (2013). Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates. In <i>Computer Aided Verification</i> (Vol. 8044, pp. 174–190). Berlin, Heidelberg: Springer Berlin Heidelberg. <a href=\"https://doi.org/10.1007/978-3-642-39799-8_11\">https://doi.org/10.1007/978-3-642-39799-8_11</a>","ama":"Dragoi C, Gupta A, Henzinger TA. Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates. In: <i>Computer Aided Verification</i>. Vol 8044. CAV. Berlin, Heidelberg: Springer Berlin Heidelberg; 2013:174-190. doi:<a href=\"https://doi.org/10.1007/978-3-642-39799-8_11\">10.1007/978-3-642-39799-8_11</a>","chicago":"Dragoi, Cezara, Ashutosh Gupta, and Thomas A Henzinger. “Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates.” In <i>Computer Aided Verification</i>, 8044:174–90. CAV. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. <a href=\"https://doi.org/10.1007/978-3-642-39799-8_11\">https://doi.org/10.1007/978-3-642-39799-8_11</a>.","ieee":"C. Dragoi, A. Gupta, and T. A. Henzinger, “Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates,” in <i>Computer Aided Verification</i>, vol. 8044, Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, pp. 174–190."},"publisher":"Springer Berlin Heidelberg","page":"174-190","series_title":"CAV","quality_controlled":"1","ec_funded":1,"file_date_updated":"2020-07-14T12:47:10Z","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-18T13:10:21Z","department":[{"_id":"ToHe"}],"title":"Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates","pubrep_id":"195","intvolume":"      8044","_id":"5747","scopus_import":"1","author":[{"full_name":"Dragoi, Cezara","last_name":"Dragoi","first_name":"Cezara","id":"2B2B5ED0-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Gupta, Ashutosh","last_name":"Gupta","first_name":"Ashutosh","id":"335E5684-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"place":"Berlin, Heidelberg","file":[{"creator":"dernst","file_id":"5748","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_name":"2013_CAV_Dragoi.pdf","date_updated":"2020-07-14T12:47:10Z","checksum":"a901cc6b71db08b61c0d4c0cbacc6287","file_size":236480,"date_created":"2018-12-18T13:13:33Z"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","publication_identifier":{"isbn":["9783642397981","9783642397998"],"issn":["0302-9743"],"eissn":["1611-3349"]},"oa":1,"date_published":"2013-01-01T00:00:00Z","type":"book_chapter","conference":{"name":"CAV 2013","start_date":"2013-07-13","end_date":"2013-07-19","location":"Saint Petersburg, Russia"},"language":[{"iso":"eng"}],"oa_version":"None","project":[{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"267989","name":"Quantitative Reactive Modeling"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"}],"publication":"Computer Aided Verification","has_accepted_license":"1"},{"publication":"Automated Technology for Verification and Analysis","month":"10","oa_version":"None","language":[{"iso":"eng"}],"conference":{"location":"Thiruvananthapuram, India","end_date":"2012-10-06","start_date":"2012-10-03","name":"ATVA: Automated Technology for Verification and Analysis"},"date_published":"2012-10-15T00:00:00Z","type":"conference","publication_identifier":{"eisbn":["9783642333866"],"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783642333859"]},"status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","place":"Berlin, Heidelberg","author":[{"full_name":"Bouajjani, Ahmed","first_name":"Ahmed","last_name":"Bouajjani"},{"id":"2B2B5ED0-F248-11E8-B48F-1D18A9856A87","first_name":"Cezara","last_name":"Dragoi","full_name":"Dragoi, Cezara"},{"first_name":"Constantin","last_name":"Enea","full_name":"Enea, Constantin"},{"first_name":"Mihaela","last_name":"Sighireanu","full_name":"Sighireanu, Mihaela"}],"_id":"10903","scopus_import":"1","alternative_title":["LNCS"],"title":"Accurate invariant checking for programs manipulating lists and arrays with infinite data","intvolume":"      7561","publication_status":"published","department":[{"_id":"ToHe"}],"date_created":"2022-03-21T07:58:39Z","article_processing_charge":"No","page":"167-182","series_title":"LNCS","quality_controlled":"1","publisher":"Springer","date_updated":"2023-09-05T14:07:24Z","citation":{"ista":"Bouajjani A, Dragoi C, Enea C, Sighireanu M. 2012. Accurate invariant checking for programs manipulating lists and arrays with infinite data. Automated Technology for Verification and Analysis. ATVA: Automated Technology for Verification and AnalysisLNCS, LNCS, vol. 7561, 167–182.","mla":"Bouajjani, Ahmed, et al. “Accurate Invariant Checking for Programs Manipulating Lists and Arrays with Infinite Data.” <i>Automated Technology for Verification and Analysis</i>, vol. 7561, Springer, 2012, pp. 167–82, doi:<a href=\"https://doi.org/10.1007/978-3-642-33386-6_14\">10.1007/978-3-642-33386-6_14</a>.","short":"A. Bouajjani, C. Dragoi, C. Enea, M. Sighireanu, in:, Automated Technology for Verification and Analysis, Springer, Berlin, Heidelberg, 2012, pp. 167–182.","chicago":"Bouajjani, Ahmed, Cezara Dragoi, Constantin Enea, and Mihaela Sighireanu. “Accurate Invariant Checking for Programs Manipulating Lists and Arrays with Infinite Data.” In <i>Automated Technology for Verification and Analysis</i>, 7561:167–82. LNCS. Berlin, Heidelberg: Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-33386-6_14\">https://doi.org/10.1007/978-3-642-33386-6_14</a>.","ieee":"A. Bouajjani, C. Dragoi, C. Enea, and M. Sighireanu, “Accurate invariant checking for programs manipulating lists and arrays with infinite data,” in <i>Automated Technology for Verification and Analysis</i>, Thiruvananthapuram, India, 2012, vol. 7561, pp. 167–182.","apa":"Bouajjani, A., Dragoi, C., Enea, C., &#38; Sighireanu, M. (2012). Accurate invariant checking for programs manipulating lists and arrays with infinite data. In <i>Automated Technology for Verification and Analysis</i> (Vol. 7561, pp. 167–182). Berlin, Heidelberg: Springer. <a href=\"https://doi.org/10.1007/978-3-642-33386-6_14\">https://doi.org/10.1007/978-3-642-33386-6_14</a>","ama":"Bouajjani A, Dragoi C, Enea C, Sighireanu M. Accurate invariant checking for programs manipulating lists and arrays with infinite data. In: <i>Automated Technology for Verification and Analysis</i>. Vol 7561. LNCS. Berlin, Heidelberg: Springer; 2012:167-182. doi:<a href=\"https://doi.org/10.1007/978-3-642-33386-6_14\">10.1007/978-3-642-33386-6_14</a>"},"year":"2012","abstract":[{"lang":"eng","text":"We propose a logic-based framework for automated reasoning about sequential programs manipulating singly-linked lists and arrays with unbounded data. We introduce the logic SLAD, which allows combining shape constraints, written in a fragment of Separation Logic, with data and size constraints. We address the problem of checking the entailment between SLAD formulas, which is crucial in performing pre-post condition reasoning. Although this problem is undecidable in general for SLAD, we propose a sound and powerful procedure that is able to solve this problem for a large class of formulas, beyond the capabilities of existing techniques and tools. We prove that this procedure is complete, i.e., it is actually a decision procedure for this problem, for an important fragment of SLAD including known decidable logics. We implemented this procedure and shown its preciseness and its efficiency on a significant benchmark of formulas."}],"doi":"10.1007/978-3-642-33386-6_14","day":"15","acknowledgement":"This work has been partially supported by the French ANR project Veridyc","volume":7561},{"external_id":{"arxiv":["1201.5073"]},"year":"2012","citation":{"apa":"Chatterjee, K., Randour, M., &#38; Raskin, J.-F. (2012). Strategy synthesis for multi-dimensional quantitative objectives. In M. Koutny &#38; I. Ulidowski (Eds.), <i>CONCUR 2012 - Concurrency Theory</i> (Vol. 7454, pp. 115–131). Berlin, Heidelberg: Springer. <a href=\"https://doi.org/10.1007/978-3-642-32940-1_10\">https://doi.org/10.1007/978-3-642-32940-1_10</a>","ama":"Chatterjee K, Randour M, Raskin J-F. Strategy synthesis for multi-dimensional quantitative objectives. In: Koutny M, Ulidowski I, eds. <i>CONCUR 2012 - Concurrency Theory</i>. Vol 7454. Berlin, Heidelberg: Springer; 2012:115-131. doi:<a href=\"https://doi.org/10.1007/978-3-642-32940-1_10\">10.1007/978-3-642-32940-1_10</a>","ieee":"K. Chatterjee, M. Randour, and J.-F. Raskin, “Strategy synthesis for multi-dimensional quantitative objectives,” in <i>CONCUR 2012 - Concurrency Theory</i>, Newcastle upon Tyne, United Kingdom, 2012, vol. 7454, pp. 115–131.","chicago":"Chatterjee, Krishnendu, Mickael Randour, and Jean-François Raskin. “Strategy Synthesis for Multi-Dimensional Quantitative Objectives.” In <i>CONCUR 2012 - Concurrency Theory</i>, edited by Maciej Koutny and Irek Ulidowski, 7454:115–31. Berlin, Heidelberg: Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-32940-1_10\">https://doi.org/10.1007/978-3-642-32940-1_10</a>.","short":"K. Chatterjee, M. Randour, J.-F. Raskin, in:, M. Koutny, I. Ulidowski (Eds.), CONCUR 2012 - Concurrency Theory, Springer, Berlin, Heidelberg, 2012, pp. 115–131.","mla":"Chatterjee, Krishnendu, et al. “Strategy Synthesis for Multi-Dimensional Quantitative Objectives.” <i>CONCUR 2012 - Concurrency Theory</i>, edited by Maciej Koutny and Irek Ulidowski, vol. 7454, Springer, 2012, pp. 115–31, doi:<a href=\"https://doi.org/10.1007/978-3-642-32940-1_10\">10.1007/978-3-642-32940-1_10</a>.","ista":"Chatterjee K, Randour M, Raskin J-F. 2012. Strategy synthesis for multi-dimensional quantitative objectives. CONCUR 2012 - Concurrency Theory. CONCUR: Conference on Concurrency Theory, LNCS, vol. 7454, 115–131."},"date_updated":"2023-02-23T10:55:06Z","abstract":[{"text":"Multi-dimensional mean-payoff and energy games provide the mathematical foundation for the quantitative study of reactive systems, and play a central role in the emerging quantitative theory of verification and synthesis. In this work, we study the strategy synthesis problem for games with such multi-dimensional objectives along with a parity condition, a canonical way to express ω-regular conditions. While in general, the winning strategies in such games may require infinite memory, for synthesis the most relevant problem is the construction of a finite-memory winning strategy (if one exists). Our main contributions are as follows. First, we show a tight exponential bound (matching upper and lower bounds) on the memory required for finite-memory winning strategies in both multi-dimensional mean-payoff and energy games along with parity objectives. This significantly improves the triple exponential upper bound for multi energy games (without parity) that could be derived from results in literature for games on VASS (vector addition systems with states). Second, we present an optimal symbolic and incremental algorithm to compute a finite-memory winning strategy (if one exists) in such games. Finally, we give a complete characterization of when finite memory of strategies can be traded off for randomness. In particular, we show that for one-dimension mean-payoff parity games, randomized memoryless strategies are as powerful as their pure finite-memory counterparts.","lang":"eng"}],"day":"15","arxiv":1,"doi":"10.1007/978-3-642-32940-1_10","volume":7454,"acknowledgement":"Author supported by Austrian Science Fund (FWF) Grant No P 23499-N23, FWF NFN Grant No S11407 (RiSE), ERC Start Grant (279307: Graph Games), Microsoft faculty fellowship.","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Mickael","last_name":"Randour","full_name":"Randour, Mickael"},{"full_name":"Raskin, Jean-François","first_name":"Jean-François","last_name":"Raskin"}],"scopus_import":"1","_id":"10904","intvolume":"      7454","alternative_title":["LNCS"],"title":"Strategy synthesis for multi-dimensional quantitative objectives","date_created":"2022-03-21T08:00:21Z","article_processing_charge":"No","department":[{"_id":"KrCh"}],"publication_status":"published","ec_funded":1,"quality_controlled":"1","page":"115-131","editor":[{"full_name":"Koutny, Maciej","first_name":"Maciej","last_name":"Koutny"},{"first_name":"Irek","last_name":"Ulidowski","full_name":"Ulidowski, Irek"}],"publisher":"Springer","type":"conference","date_published":"2012-09-15T00:00:00Z","publication_identifier":{"eisbn":["9783642329401"],"issn":["0302-9743","1611-3349"],"isbn":["9783642329395"]},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"id":"2716","relation":"later_version","status":"public"}]},"place":"Berlin, Heidelberg","publication":"CONCUR 2012 - Concurrency Theory","month":"09","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407","name":"Game Theory"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"oa_version":"Preprint","language":[{"iso":"eng"}],"conference":{"start_date":"2012-09-04","name":"CONCUR: Conference on Concurrency Theory","end_date":"2012-09-07","location":"Newcastle upon Tyne, United Kingdom"}},{"language":[{"iso":"eng"}],"conference":{"name":"ESA: European Symposium on Algorithms","start_date":"2012-09-10","end_date":"2012-09-12","location":"Ljubljana, Slovenia"},"publication":"Algorithms – ESA 2012","oa_version":"Preprint","project":[{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"month":"10","main_file_link":[{"url":"https://arxiv.org/abs/1604.08234","open_access":"1"}],"status":"public","related_material":{"record":[{"status":"public","id":"535","relation":"later_version"}]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","date_published":"2012-10-01T00:00:00Z","type":"conference","publication_identifier":{"isbn":["9783642330896"],"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["9783642330902"]},"oa":1,"page":"301-312","ec_funded":1,"quality_controlled":"1","publisher":"Springer","_id":"10905","scopus_import":"1","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Krinninger, Sebastian","first_name":"Sebastian","last_name":"Krinninger"},{"full_name":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"}],"publication_status":"published","date_created":"2022-03-21T08:01:45Z","article_processing_charge":"No","department":[{"_id":"KrCh"}],"title":"Polynomial-time algorithms for energy games with special weight structures","alternative_title":["LNCS"],"intvolume":"      7501","volume":7501,"acknowledgement":"Supported by the Austrian Science Fund (FWF): P23499-N23, the Austrian Science Fund (FWF): S11407-N23 (RiSE), an ERC Start Grant (279307: Graph Games), and a Microsoft Faculty Fellows Award","date_updated":"2023-09-05T14:09:30Z","year":"2012","citation":{"short":"K. Chatterjee, M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, Algorithms – ESA 2012, Springer, 2012, pp. 301–312.","mla":"Chatterjee, Krishnendu, et al. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” <i>Algorithms – ESA 2012</i>, vol. 7501, Springer, 2012, pp. 301–12, doi:<a href=\"https://doi.org/10.1007/978-3-642-33090-2_27\">10.1007/978-3-642-33090-2_27</a>.","ista":"Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. 2012. Polynomial-time algorithms for energy games with special weight structures. Algorithms – ESA 2012. ESA: European Symposium on Algorithms, LNCS, vol. 7501, 301–312.","apa":"Chatterjee, K., Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2012). Polynomial-time algorithms for energy games with special weight structures. In <i>Algorithms – ESA 2012</i> (Vol. 7501, pp. 301–312). Ljubljana, Slovenia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-33090-2_27\">https://doi.org/10.1007/978-3-642-33090-2_27</a>","ama":"Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. Polynomial-time algorithms for energy games with special weight structures. In: <i>Algorithms – ESA 2012</i>. Vol 7501. Springer; 2012:301-312. doi:<a href=\"https://doi.org/10.1007/978-3-642-33090-2_27\">10.1007/978-3-642-33090-2_27</a>","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” In <i>Algorithms – ESA 2012</i>, 7501:301–12. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-33090-2_27\">https://doi.org/10.1007/978-3-642-33090-2_27</a>.","ieee":"K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time algorithms for energy games with special weight structures,” in <i>Algorithms – ESA 2012</i>, Ljubljana, Slovenia, 2012, vol. 7501, pp. 301–312."},"external_id":{"arxiv":["1604.08234"]},"doi":"10.1007/978-3-642-33090-2_27","arxiv":1,"day":"01","abstract":[{"lang":"eng","text":"Energy games belong to a class of turn-based two-player infinite-duration games played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in NP ∩ co−NP, but are not known to be in P. While the existence of polynomial-time algorithms has been a major open problem for decades, there is no algorithm that solves any non-trivial subclass in polynomial time.\r\nIn this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several counter examples that show that many previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting graph structures need not help."}]}]