--- _id: '11670' abstract: - lang: eng text: Auctions are widely used on the Web. Applications range from sponsored search to platforms such as eBay. In these and in many other applications the auctions in use are single-/multi-item auctions with unit demand. The main drawback of standard mechanisms for this type of auctions, such as VCG and GSP, is the limited expressiveness that they offer to the bidders. The General Auction Mechanism (GAM) of Aggarwal et al. [2009] takes a first step toward addressing the problem of limited expressiveness by computing a bidder optimal, envy-free outcome for linear utility functions with identical slopes and a single discontinuity per bidder-item pair. We show that in many practical situations this does not suffice to adequately model the preferences of the bidders, and we overcome this problem by presenting the first mechanism for piecewise linear utility functions with nonidentical slopes and multiple discontinuities. Our mechanism runs in polynomial time. Like GAM it is incentive compatible for inputs that fulfill a certain nondegeneracy assumption, but our requirement is more general than the requirement of GAM. For discontinuous utility functions that are nondegenerate as well as for continuous utility functions the outcome of our mechanism is a competitive equilibrium. We also show how our mechanism can be used to compute approximately bidder optimal, envy-free outcomes for a general class of continuous utility functions via piecewise linear approximation. Finally, we prove hardness results for even more expressive settings. acknowledgement: We would like to thank Veronika Loitzenbauer and the anonymous referees for their valuable feedback. article_number: '1' article_processing_charge: No article_type: original author: - first_name: Paul full_name: Dütting, Paul last_name: Dütting - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Ingmar full_name: Weber, Ingmar last_name: Weber citation: ama: Dütting P, Henzinger M, Weber I. An expressive mechanism for auctions on the web. ACM Transactions on Economics and Computation. 2015;4(1). doi:10.1145/2716312 apa: Dütting, P., Henzinger, M., & Weber, I. (2015). An expressive mechanism for auctions on the web. ACM Transactions on Economics and Computation. Association for Computing Machinery. https://doi.org/10.1145/2716312 chicago: Dütting, Paul, Monika Henzinger, and Ingmar Weber. “An Expressive Mechanism for Auctions on the Web.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2015. https://doi.org/10.1145/2716312. ieee: P. Dütting, M. Henzinger, and I. Weber, “An expressive mechanism for auctions on the web,” ACM Transactions on Economics and Computation, vol. 4, no. 1. Association for Computing Machinery, 2015. ista: Dütting P, Henzinger M, Weber I. 2015. An expressive mechanism for auctions on the web. ACM Transactions on Economics and Computation. 4(1), 1. mla: Dütting, Paul, et al. “An Expressive Mechanism for Auctions on the Web.” ACM Transactions on Economics and Computation, vol. 4, no. 1, 1, Association for Computing Machinery, 2015, doi:10.1145/2716312. short: P. Dütting, M. Henzinger, I. Weber, ACM Transactions on Economics and Computation 4 (2015). date_created: 2022-07-27T12:43:18Z date_published: 2015-12-02T00:00:00Z date_updated: 2024-11-06T12:07:05Z day: '02' doi: 10.1145/2716312 extern: '1' fulldoi: https://doi.org/10.1145/2716312 intvolume: ' 4' issue: '1' keyword: - Computational Mathematics - Marketing - Economics and Econometrics - Statistics and Probability - Computer Science (miscellaneous) language: - iso: eng month: '12' oa_version: None publication: ACM Transactions on Economics and Computation publication_identifier: eissn: - 2167-8383 issn: - 2167-8375 publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' scopus_import: '1' status: public title: An expressive mechanism for auctions on the web type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 4 year: '2015' ... --- _id: '11773' abstract: - lang: eng 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." alternative_title: - LNCS article_processing_charge: No arxiv: 1 author: - first_name: Oren full_name: Ben-Zwi, Oren last_name: Ben-Zwi - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Veronika full_name: Loitzenbauer, Veronika last_name: Loitzenbauer citation: ama: 'Ben-Zwi O, Henzinger M, Loitzenbauer V. Ad exchange: Envy-free auctions with mediators. In: 11th International Conference on Web and Internet Economics. Vol 9470. Springer Nature; 2015:104–117. doi:10.1007/978-3-662-48995-6_8' apa: 'Ben-Zwi, O., Henzinger, M., & Loitzenbauer, V. (2015). Ad exchange: Envy-free auctions with mediators. In 11th International Conference on Web and Internet Economics (Vol. 9470, pp. 104–117). Amsterdam, Netherlands: Springer Nature. https://doi.org/10.1007/978-3-662-48995-6_8' chicago: 'Ben-Zwi, Oren, Monika Henzinger, and Veronika Loitzenbauer. “Ad Exchange: Envy-Free Auctions with Mediators.” In 11th International Conference on Web and Internet Economics, 9470:104–117. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-48995-6_8.' ieee: 'O. Ben-Zwi, M. Henzinger, and V. Loitzenbauer, “Ad exchange: Envy-free auctions with mediators,” in 11th International Conference on Web and Internet Economics, Amsterdam, Netherlands, 2015, vol. 9470, pp. 104–117.' ista: 'Ben-Zwi O, Henzinger M, 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.” 11th International Conference on Web and Internet Economics, vol. 9470, Springer Nature, 2015, pp. 104–117, doi:10.1007/978-3-662-48995-6_8.' short: O. Ben-Zwi, M. Henzinger, V. Loitzenbauer, in:, 11th International Conference on Web and Internet Economics, Springer Nature, 2015, pp. 104–117. conference: end_date: 2015-09-12 location: Amsterdam, Netherlands name: 'WINE: International Conference on Web and Internet Economics' start_date: 2015-09-09 date_created: 2022-08-08T13:33:56Z date_published: 2015-12-09T00:00:00Z date_updated: 2024-11-06T12:10:25Z day: '09' doi: 10.1007/978-3-662-48995-6_8 extern: '1' external_id: arxiv: - '1604.05562' fulldoi: https://doi.org/10.1007/978-3-662-48995-6_8 intvolume: ' 9470' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.1604.05562 month: '12' oa: 1 oa_version: Preprint page: 104–117 publication: 11th International Conference on Web and Internet Economics publication_identifier: eisbn: - '9783662489956' isbn: - '9783662489949' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: 'Ad exchange: Envy-free auctions with mediators' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9470 year: '2015' ... --- _id: '11774' 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 \U0001D6FC-approximation mechanism for conflict-free valuations and yields an \U0001D4AA(\U0001D6FCΔ)-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 \U0001D4AA((Δ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 \U0001D45C(Δ) when the number of items is only logarithmic in the number of bidders." alternative_title: - LNCS article_processing_charge: No arxiv: 1 author: - first_name: Yun Kuen full_name: Cheung, Yun Kuen last_name: Cheung - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Martin full_name: Hoefer, Martin last_name: Hoefer - first_name: Martin full_name: Starnberger, Martin last_name: Starnberger citation: ama: 'Cheung YK, Henzinger M, Hoefer M, Starnberger M. Combinatorial auctions with conflict-based externalities. In: 11th International Conference on Web and Internet Economics. Vol 9470. Springer Nature; 2015:230–243. doi:10.1007/978-3-662-48995-6_17' apa: 'Cheung, Y. K., Henzinger, M., Hoefer, M., & Starnberger, M. (2015). Combinatorial auctions with conflict-based externalities. In 11th International Conference on Web and Internet Economics (Vol. 9470, pp. 230–243). Amsterdam, Netherlands: Springer Nature. https://doi.org/10.1007/978-3-662-48995-6_17' chicago: Cheung, Yun Kuen, Monika Henzinger, Martin Hoefer, and Martin Starnberger. “Combinatorial Auctions with Conflict-Based Externalities.” In 11th International Conference on Web and Internet Economics, 9470:230–243. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-48995-6_17. ieee: Y. K. Cheung, M. Henzinger, M. Hoefer, and M. Starnberger, “Combinatorial auctions with conflict-based externalities,” in 11th International Conference on Web and Internet Economics, Amsterdam, Netherlands, 2015, vol. 9470, pp. 230–243. ista: 'Cheung YK, Henzinger M, 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.” 11th International Conference on Web and Internet Economics, vol. 9470, Springer Nature, 2015, pp. 230–243, doi:10.1007/978-3-662-48995-6_17. short: Y.K. Cheung, M. Henzinger, M. Hoefer, M. Starnberger, in:, 11th International Conference on Web and Internet Economics, Springer Nature, 2015, pp. 230–243. conference: end_date: 2015-12-12 location: Amsterdam, Netherlands name: 'WINE: International Conference on Web and Internet Economics' start_date: 2015-12-09 date_created: 2022-08-08T13:54:32Z date_published: 2015-12-09T00:00:00Z date_updated: 2024-11-06T12:10:38Z day: '09' doi: 10.1007/978-3-662-48995-6_17 extern: '1' external_id: arxiv: - '1509.09147' fulldoi: https://doi.org/10.1007/978-3-662-48995-6_17 intvolume: ' 9470' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.1509.09147 month: '12' oa: 1 oa_version: Preprint page: 230–243 publication: 11th International Conference on Web and Internet Economics publication_identifier: eisbn: - '9783662489956' isbn: - '9783662489949' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Combinatorial auctions with conflict-based externalities type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9470 year: '2015' ... --- _id: '11785' 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 \U0001D45C(\U0001D45A\U0001D45B) total update time, where \U0001D45A is the number of edges and \U0001D45B 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 \U0001D45A vs. \U0001D45B trade-off. For the case of \U0001D45A=Θ(\U0001D45B1.5) the running time is \U0001D442(\U0001D45B2.47), just barely below \U0001D45A\U0001D45B=Θ(\U0001D45B2.5). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of \U0001D442̃ (min(\U0001D45A7/6\U0001D45B2/3,\U0001D45A3/4\U0001D45B5/4+\U0001D45C(1),\U0001D45A2/3\U0001D45B4/3+\U0001D45C(1)+\U0001D45A3/7\U0001D45B12/7+\U0001D45C(1))). This gives, e.g., \U0001D442(\U0001D45B2.36) for the notorious case \U0001D45A=Θ(\U0001D45B1.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." alternative_title: - LNCS article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Sebastian full_name: Krinninger, Sebastian last_name: Krinninger - first_name: Danupon full_name: Nanongkai, Danupon last_name: Nanongkai citation: ama: 'Henzinger M, Krinninger S, Nanongkai D. Improved algorithms for decremental single-source reachability on directed graphs. In: 42nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:725-736. doi:10.1007/978-3-662-47672-7_59' apa: 'Henzinger, M., Krinninger, S., & Nanongkai, D. (2015). Improved algorithms for decremental single-source reachability on directed graphs. In 42nd International Colloquium on Automata, Languages and Programming (Vol. 9134, pp. 725–736). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47672-7_59' chicago: Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.” In 42nd International Colloquium on Automata, Languages and Programming, 9134:725–36. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_59. ieee: M. Henzinger, S. Krinninger, and D. Nanongkai, “Improved algorithms for decremental single-source reachability on directed graphs,” in 42nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 725–736. ista: 'Henzinger M, 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, et al. “Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.” 42nd International Colloquium on Automata, Languages and Programming, vol. 9134, Springer Nature, 2015, pp. 725–36, doi:10.1007/978-3-662-47672-7_59. short: M. Henzinger, S. Krinninger, D. Nanongkai, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 725–736. conference: end_date: 2015-07-10 location: Kyoto, Japan name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2015-07-06 date_created: 2022-08-11T08:51:32Z date_published: 2015-01-01T00:00:00Z date_updated: 2024-11-06T12:10:50Z day: '01' doi: 10.1007/978-3-662-47672-7_59 extern: '1' external_id: arxiv: - '1612.03856' fulldoi: https://doi.org/10.1007/978-3-662-47672-7_59 intvolume: ' 9134' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1612.03856 month: '01' oa: 1 oa_version: Preprint page: 725 - 736 publication: 42nd International Colloquium on Automata, Languages and Programming publication_identifier: isbn: - '9783662476710' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Improved algorithms for decremental single-source reachability on directed graphs type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9134 year: '2015' ... --- _id: '11786' abstract: - lang: eng 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 \U0001D442(\U0001D4532)-approximately optimal solution in \U0001D442(\U0001D453⋅log(\U0001D45A+\U0001D45B)) amortized update time, where \U0001D453 is the maximum “frequency” of an element, \U0001D45B is the number of sets, and \U0001D45A is the maximum number of elements in the universe at any point in time. (2) For the dynamic \U0001D44F-matching problem, we maintain an \U0001D442(1)-approximately optimal solution in \U0001D442(log3\U0001D45B) amortized update time, where \U0001D45B is the number of nodes in the graph." alternative_title: - LNCS article_processing_charge: No arxiv: 1 author: - first_name: Sayan full_name: Bhattacharya, Sayan last_name: Bhattacharya - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Giuseppe F. full_name: Italiano, Giuseppe F. last_name: Italiano citation: ama: 'Bhattacharya S, Henzinger M, Italiano GF. Design of dynamic algorithms via primal-dual method. In: 42nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:206-218. doi:10.1007/978-3-662-47672-7_17' apa: 'Bhattacharya, S., Henzinger, M., & Italiano, G. F. (2015). Design of dynamic algorithms via primal-dual method. In 42nd International Colloquium on Automata, Languages and Programming (Vol. 9134, pp. 206–218). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47672-7_17' chicago: Bhattacharya, Sayan, Monika Henzinger, and Giuseppe F. Italiano. “Design of Dynamic Algorithms via Primal-Dual Method.” In 42nd International Colloquium on Automata, Languages and Programming, 9134:206–18. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_17. ieee: S. Bhattacharya, M. Henzinger, and G. F. Italiano, “Design of dynamic algorithms via primal-dual method,” in 42nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 206–218. ista: 'Bhattacharya S, Henzinger M, 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.' mla: Bhattacharya, Sayan, et al. “Design of Dynamic Algorithms via Primal-Dual Method.” 42nd International Colloquium on Automata, Languages and Programming, vol. 9134, Springer Nature, 2015, pp. 206–18, doi:10.1007/978-3-662-47672-7_17. short: S. Bhattacharya, M. Henzinger, G.F. Italiano, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 206–218. conference: end_date: 2015-07-10 location: Kyoto, Japan name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2015-07-06 date_created: 2022-08-11T09:28:49Z date_published: 2015-01-01T00:00:00Z date_updated: 2024-11-06T12:11:02Z day: '01' doi: 10.1007/978-3-662-47672-7_17 extern: '1' external_id: arxiv: - '1604.05337' fulldoi: https://doi.org/10.1007/978-3-662-47672-7_17 intvolume: ' 9134' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1604.05337 month: '01' oa: 1 oa_version: Preprint page: 206 - 218 publication: 42nd International Colloquium on Automata, Languages and Programming publication_identifier: isbn: - '9783662476710' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Design of dynamic algorithms via primal-dual method type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9134 year: '2015' ... --- _id: '11787' 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 \U0001D442(\U0001D45B2). For 2-edge strongly connected components our algorithm gives the first running time improvement in 20 years. Additionally we present an \U0001D442(\U0001D45A2/log\U0001D45B)-time algorithm for 2-edge strongly connected components, and thus improve over the O(m n) running time also when \U0001D45A=\U0001D442(\U0001D45B). Our approach extends to k-edge and k-vertex strongly connected components for any constant k with a running time of \U0001D442(\U0001D45B2log\U0001D45B) for k-edge-connectivity and \U0001D442(\U0001D45B3) for k-vertex-connectivity." alternative_title: - LNCS article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Sebastian full_name: Krinninger, Sebastian last_name: Krinninger - first_name: Veronika full_name: Loitzenbauer, Veronika last_name: Loitzenbauer citation: ama: 'Henzinger M, Krinninger S, Loitzenbauer V. Finding 2-edge and 2-vertex strongly connected components in quadratic time. In: 2nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:713-724. doi:10.1007/978-3-662-47672-7_58' apa: 'Henzinger, M., Krinninger, S., & Loitzenbauer, V. (2015). Finding 2-edge and 2-vertex strongly connected components in quadratic time. In 2nd International Colloquium on Automata, Languages and Programming (Vol. 9134, pp. 713–724). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47672-7_58' chicago: Henzinger, Monika, Sebastian Krinninger, and Veronika Loitzenbauer. “Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” In 2nd International Colloquium on Automata, Languages and Programming, 9134:713–24. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_58. ieee: M. Henzinger, S. Krinninger, and V. Loitzenbauer, “Finding 2-edge and 2-vertex strongly connected components in quadratic time,” in 2nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 713–724. ista: 'Henzinger M, 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.' mla: Henzinger, Monika, et al. “Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” 2nd International Colloquium on Automata, Languages and Programming, vol. 9134, Springer Nature, 2015, pp. 713–24, doi:10.1007/978-3-662-47672-7_58. short: M. Henzinger, S. Krinninger, V. Loitzenbauer, in:, 2nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 713–724. conference: end_date: 2015-07-10 location: Kyoto, Japan name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2015-07-06 date_created: 2022-08-11T09:38:34Z date_published: 2015-07-06T00:00:00Z date_updated: 2024-11-06T12:11:13Z day: '06' doi: 10.1007/978-3-662-47672-7_58 extern: '1' external_id: arxiv: - '1412.6466' fulldoi: https://doi.org/10.1007/978-3-662-47672-7_58 intvolume: ' 9134' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1412.6466 month: '07' oa: 1 oa_version: Preprint page: 713 - 724 publication: 2nd International Colloquium on Automata, Languages and Programming publication_identifier: isbn: - '9783662476710' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Finding 2-edge and 2-vertex strongly connected components in quadratic time type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9134 year: '2015' ... --- _id: '11788' abstract: - lang: eng 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 \U0001D445\U0001D434\U0001D437\U0001D44B+\U0001D445\U0001D434(1−1/\U0001D452), where \U0001D445\U0001D434\U0001D437\U0001D44B is the revenue that the optimum algorithm achieves from the ad exchange and \U0001D445\U0001D434 is the revenue that the optimum algorithm achieves from the contracted advertisers." alternative_title: - LNCS article_processing_charge: No arxiv: 1 author: - first_name: Wolfgang full_name: Dvořák, Wolfgang last_name: Dvořák - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 citation: ama: 'Dvořák W, Henzinger M. Online ad assignment with an ad exchange. In: 12th International Workshop of Approximation and Online Algorithms. Vol 8952. Springer Nature; 2015:156–167. doi:10.1007/978-3-319-18263-6_14' apa: 'Dvořák, W., & Henzinger, M. (2015). Online ad assignment with an ad exchange. In 12th International Workshop of Approximation and Online Algorithms (Vol. 8952, pp. 156–167). Wroclaw, Poland: Springer Nature. https://doi.org/10.1007/978-3-319-18263-6_14' chicago: Dvořák, Wolfgang, and Monika Henzinger. “Online Ad Assignment with an Ad Exchange.” In 12th International Workshop of Approximation and Online Algorithms, 8952:156–167. Springer Nature, 2015. https://doi.org/10.1007/978-3-319-18263-6_14. ieee: W. Dvořák and M. Henzinger, “Online ad assignment with an ad exchange,” in 12th International Workshop of Approximation and Online Algorithms, Wroclaw, Poland, 2015, vol. 8952, pp. 156–167. ista: 'Dvořák W, Henzinger M. 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 Henzinger. “Online Ad Assignment with an Ad Exchange.” 12th International Workshop of Approximation and Online Algorithms, vol. 8952, Springer Nature, 2015, pp. 156–167, doi:10.1007/978-3-319-18263-6_14. short: W. Dvořák, M. Henzinger, in:, 12th International Workshop of Approximation and Online Algorithms, Springer Nature, 2015, pp. 156–167. conference: end_date: 2014-09-12 location: Wroclaw, Poland name: 'WAOA: International Workshop on Approximation and Online Algorithms' start_date: 2014-09-11 date_created: 2022-08-11T09:43:32Z date_published: 2015-01-01T00:00:00Z date_updated: 2024-11-06T12:11:24Z day: '01' doi: 10.1007/978-3-319-18263-6_14 extern: '1' external_id: arxiv: - '1604.05603' fulldoi: https://doi.org/10.1007/978-3-319-18263-6_14 intvolume: ' 8952' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1604.05603 month: '01' oa: 1 oa_version: Preprint page: 156–167 publication: 12th International Workshop of Approximation and Online Algorithms publication_identifier: issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Online ad assignment with an ad exchange type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8952 year: '2015' ... --- _id: '11837' abstract: - lang: eng text: "Online social networks allow the collection of large amounts of data about the influence between users connected by a friendship-like relationship. When distributing items among agents forming a social network, this information allows us to exploit network externalities that each agent receives from his neighbors that get the same item. In this paper we consider Friends-of-Friends (2-hop) network externalities, i.e., externalities that not only depend on the neighbors that get the same item but also on neighbors of neighbors. For these externalities we study a setting where multiple different items are assigned to unit-demand agents. Specifically, we study the problem of welfare maximization under different types of externality functions. Let n be the number of agents and m be the number of items. Our contributions are the following: (1) We show that welfare maximization is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop) externalities it is NP-hard to approximate social welfare better than (1-1/e). (2) On the positive side we present (i) an O(sqrt n)-approximation algorithm for general concave externality functions,\r\n(ii) an O(\\log m)-approximation algorithm for linear externality functions, and (iii) an (1-1/e)\\frac{1}{6}-approximation algorithm for 2-hop step function externalities. We also improve the result from [6] for 1-hop step function externalities by giving a (1-1/e)/2-approximation algorithm." alternative_title: - LIPIcs article_processing_charge: No author: - first_name: Sayan full_name: Bhattacharya, Sayan last_name: Bhattacharya - first_name: Wolfgang full_name: Dvorák, Wolfgang last_name: Dvorák - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: ' Martin' full_name: Starnberger, Martin last_name: Starnberger citation: ama: 'Bhattacharya S, Dvorák W, Henzinger M, Starnberger Martin. Welfare maximization with friends-of-friends network externalities. In: 32nd International Symposium on Theoretical Aspects of Computer Science. Vol 30. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:90-102. doi:10.4230/LIPICS.STACS.2015.90' apa: 'Bhattacharya, S., Dvorák, W., Henzinger, M., & Starnberger, Martin. (2015). Welfare maximization with friends-of-friends network externalities. In 32nd International Symposium on Theoretical Aspects of Computer Science (Vol. 30, pp. 90–102). Garching, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.STACS.2015.90' chicago: Bhattacharya, Sayan, Wolfgang Dvorák, Monika Henzinger, and Martin Starnberger. “Welfare Maximization with Friends-of-Friends Network Externalities.” In 32nd International Symposium on Theoretical Aspects of Computer Science, 30:90–102. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. https://doi.org/10.4230/LIPICS.STACS.2015.90. ieee: S. Bhattacharya, W. Dvorák, M. Henzinger, and Martin Starnberger, “Welfare maximization with friends-of-friends network externalities,” in 32nd International Symposium on Theoretical Aspects of Computer Science, Garching, Germany, 2015, vol. 30, pp. 90–102. ista: 'Bhattacharya S, Dvorák W, Henzinger M, Starnberger Martin. 2015. Welfare maximization with friends-of-friends network externalities. 32nd International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 30, 90–102.' mla: Bhattacharya, Sayan, et al. “Welfare Maximization with Friends-of-Friends Network Externalities.” 32nd International Symposium on Theoretical Aspects of Computer Science, vol. 30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 90–102, doi:10.4230/LIPICS.STACS.2015.90. short: S. Bhattacharya, W. Dvorák, M. Henzinger, Martin Starnberger, in:, 32nd International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 90–102. conference: end_date: 2015-03-07 location: Garching, Germany name: 'STACS: Symposium on Theoretical Aspects of Computer Science' start_date: 2015-03-04 date_created: 2022-08-12T11:39:40Z date_published: 2015-02-26T00:00:00Z date_updated: 2024-11-06T12:24:23Z day: '26' doi: 10.4230/LIPICS.STACS.2015.90 extern: '1' fulldoi: https://doi.org/10.4230/LIPICS.STACS.2015.90 intvolume: ' 30' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPICS.STACS.2015.90 month: '02' oa: 1 oa_version: Published Version page: 90-102 publication: 32nd International Symposium on Theoretical Aspects of Computer Science publication_identifier: isbn: - 978-3-939897-78-1 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '11903' relation: later_version status: public scopus_import: '1' status: public title: Welfare maximization with friends-of-friends network externalities type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 30 year: '2015' ... --- _id: '11845' abstract: - lang: eng text: "Phylogenetic diversity (PD) is a measure of biodiversity based on the evolutionary history of species. Here, we discuss several optimization problems related to the use of PD, and the more general measure split diversity (SD), in conservation prioritization.\r\nDepending on the conservation goal and the information available about species, one can construct optimization routines that incorporate various conservation constraints. We demonstrate how this information can be used to select sets of species for conservation action. Specifically, we discuss the use of species' geographic distributions, the choice of candidates under economic pressure, and the use of predator–prey interactions between the species in a community to define viability constraints.\r\nDespite such optimization problems falling into the area of NP hard problems, it is possible to solve them in a reasonable amount of time using integer programming. We apply integer linear programming to a variety of models for conservation prioritization that incorporate the SD measure.\r\nWe exemplarily show the results for two data sets: the Cape region of South Africa and a Caribbean coral reef community. Finally, we provide user-friendly software at http://www.cibiv.at/software/pda." article_processing_charge: No article_type: original author: - first_name: Olga full_name: Chernomor, Olga last_name: Chernomor - first_name: Bui Quang full_name: Minh, Bui Quang last_name: Minh - first_name: Félix full_name: Forest, Félix last_name: Forest - first_name: Steffen full_name: Klaere, Steffen last_name: Klaere - first_name: Travis full_name: Ingram, Travis last_name: Ingram - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Arndt full_name: von Haeseler, Arndt last_name: von Haeseler citation: ama: Chernomor O, Minh BQ, Forest F, et al. Split diversity in constrained conservation prioritization using integer linear programming. Methods in Ecology and Evolution. 2015;6(1):83-91. doi:10.1111/2041-210x.12299 apa: Chernomor, O., Minh, B. Q., Forest, F., Klaere, S., Ingram, T., Henzinger, M., & von Haeseler, A. (2015). Split diversity in constrained conservation prioritization using integer linear programming. Methods in Ecology and Evolution. Wiley. https://doi.org/10.1111/2041-210x.12299 chicago: Chernomor, Olga, Bui Quang Minh, Félix Forest, Steffen Klaere, Travis Ingram, Monika Henzinger, and Arndt von Haeseler. “Split Diversity in Constrained Conservation Prioritization Using Integer Linear Programming.” Methods in Ecology and Evolution. Wiley, 2015. https://doi.org/10.1111/2041-210x.12299. ieee: O. Chernomor et al., “Split diversity in constrained conservation prioritization using integer linear programming,” Methods in Ecology and Evolution, vol. 6, no. 1. Wiley, pp. 83–91, 2015. ista: Chernomor O, Minh BQ, Forest F, Klaere S, Ingram T, Henzinger M, von Haeseler A. 2015. Split diversity in constrained conservation prioritization using integer linear programming. Methods in Ecology and Evolution. 6(1), 83–91. mla: Chernomor, Olga, et al. “Split Diversity in Constrained Conservation Prioritization Using Integer Linear Programming.” Methods in Ecology and Evolution, vol. 6, no. 1, Wiley, 2015, pp. 83–91, doi:10.1111/2041-210x.12299. short: O. Chernomor, B.Q. Minh, F. Forest, S. Klaere, T. Ingram, M. Henzinger, A. von Haeseler, Methods in Ecology and Evolution 6 (2015) 83–91. date_created: 2022-08-16T06:43:49Z date_published: 2015-01-01T00:00:00Z date_updated: 2024-11-06T12:16:55Z day: '01' ddc: - '570' doi: 10.1111/2041-210x.12299 extern: '1' external_id: pmid: - '25893087' file: - access_level: open_access checksum: 880e78f09f0ac99cb351c48dc97623b6 content_type: application/pdf creator: asandaue date_created: 2022-08-16T06:52:53Z date_updated: 2022-08-16T06:52:53Z file_id: '11846' file_name: 2015_MethodsInEcologyAndEvolutionChernomor.pdf file_size: 411415 relation: main_file success: 1 file_date_updated: 2022-08-16T06:52:53Z fulldoi: https://doi.org/10.1111/2041-210x.12299 has_accepted_license: '1' intvolume: ' 6' issue: '1' language: - iso: eng license: https://creativecommons.org/licenses/by/4.0/ month: '01' oa: 1 oa_version: Published Version page: 83-91 pmid: 1 publication: Methods in Ecology and Evolution publication_identifier: eissn: - 2041-210X publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: Split diversity in constrained conservation prioritization using integer linear programming tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 6 year: '2015' ... --- _id: '11868' abstract: - lang: eng text: "Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n x n matrix M and will receive n column-vectors of size n, denoted by v1, ..., vn, one by one. After seeing each vector vi, we have to output the product Mvi before we can see the next vector. A naive algorithm can solve this problem using O(n3) time in total, and its running time can be slightly improved to O(n3/log2 n) [Williams SODA'07]. We show that a conjecture that there is no truly subcubic (O(n3-ε)) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term \"combinatorial algorithms\" is interpreted as \"Strassen-like algorithms\" [Ballard et al. SPAA'11].\r\n\r\nThe conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures -- such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase -- thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results, e.g., for the fully-dynamic densest subgraph and diameter problems." article_number: 21-30 article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Sebastian full_name: Krinninger, Sebastian last_name: Krinninger - first_name: Danupon full_name: Nanongkai, Danupon last_name: Nanongkai - first_name: Thatchaphol full_name: Saranurak, Thatchaphol last_name: Saranurak citation: ama: 'Henzinger M, Krinninger S, Nanongkai D, Saranurak T. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: 47th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2015. doi:10.1145/2746539.2746609' apa: 'Henzinger, M., Krinninger, S., Nanongkai, D., & Saranurak, T. (2015). Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In 47th Annual ACM Symposium on Theory of Computing. Portland, OR, United States: Association for Computing Machinery. https://doi.org/10.1145/2746539.2746609' chicago: Henzinger, Monika, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. “Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.” In 47th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 2015. https://doi.org/10.1145/2746539.2746609. ieee: M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak, “Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture,” in 47th Annual ACM Symposium on Theory of Computing, Portland, OR, United States, 2015. ista: 'Henzinger M, Krinninger S, Nanongkai D, Saranurak T. 2015. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. 47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 21–30.' mla: Henzinger, Monika, et al. “Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.” 47th Annual ACM Symposium on Theory of Computing, 21–30, Association for Computing Machinery, 2015, doi:10.1145/2746539.2746609. short: M. Henzinger, S. Krinninger, D. Nanongkai, T. Saranurak, in:, 47th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2015. conference: end_date: 2015-06-17 location: Portland, OR, United States name: 'STOC: Symposium on Theory of Computing' start_date: 2015-06-14 date_created: 2022-08-16T09:31:21Z date_published: 2015-06-14T00:00:00Z date_updated: 2024-11-06T12:19:48Z day: '14' doi: 10.1145/2746539.2746609 extern: '1' external_id: arxiv: - '1511.06773' fulldoi: https://doi.org/10.1145/2746539.2746609 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1511.06773 month: '06' oa: 1 oa_version: Preprint publication: 47th Annual ACM Symposium on Theory of Computing publication_identifier: isbn: - 978-145033536-2 issn: - '0737.8017' publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' scopus_import: '1' status: public title: Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ... --- _id: '11869' abstract: - lang: eng text: "While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of both time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called densest subgraph problem. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge.\r\n\r\nGiven an input graph, the densest subgraph is the subgraph that maximizes the ratio between the number of edges and the number of nodes. For any ε>0, our algorithm can, with high probability, maintain a (4+ε)-approximate solution under edge insertions and deletions using ~O(n) space and ~O(1) amortized time per update; here, $n$ is the number of nodes in the graph and ~O hides the O(polylog_{1+ε} n) term. The approximation ratio can be improved to (2+ε) with more time. It can be extended to a (2+ε)-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in one pass. Prior to this, no algorithm could do so even in the special case of an incremental stream and even when there is no time restriction. The previously best algorithm in this setting required O(log n) passes [BahmaniKV12]. The space required by our algorithm is tight up to a polylogarithmic factor." article_processing_charge: No arxiv: 1 author: - first_name: Sayan full_name: Bhattacharya, Sayan last_name: Bhattacharya - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Danupon full_name: Nanongkai, Danupon last_name: Nanongkai - first_name: Charalampos full_name: Tsourakakis, Charalampos last_name: Tsourakakis citation: ama: 'Bhattacharya S, Henzinger M, Nanongkai D, Tsourakakis C. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: 47th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2015:173-182. doi:10.1145/2746539.2746592' apa: 'Bhattacharya, S., Henzinger, M., Nanongkai, D., & Tsourakakis, C. (2015). Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In 47th Annual ACM Symposium on Theory of Computing (pp. 173–182). Portland, OR, United States: Association for Computing Machinery. https://doi.org/10.1145/2746539.2746592' chicago: Bhattacharya, Sayan, Monika Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.” In 47th Annual ACM Symposium on Theory of Computing, 173–82. Association for Computing Machinery, 2015. https://doi.org/10.1145/2746539.2746592. ieee: S. Bhattacharya, M. Henzinger, D. Nanongkai, and C. Tsourakakis, “Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams,” in 47th Annual ACM Symposium on Theory of Computing, Portland, OR, United States, 2015, pp. 173–182. ista: 'Bhattacharya S, Henzinger M, Nanongkai D, Tsourakakis C. 2015. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. 47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 173–182.' mla: Bhattacharya, Sayan, et al. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.” 47th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2015, pp. 173–82, doi:10.1145/2746539.2746592. short: S. Bhattacharya, M. Henzinger, D. Nanongkai, C. Tsourakakis, in:, 47th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2015, pp. 173–182. conference: end_date: 2015-06-17 location: Portland, OR, United States name: 'STOC: Symposium on Theory of Computing' start_date: 2015-06-14 date_created: 2022-08-16T09:36:48Z date_published: 2015-06-01T00:00:00Z date_updated: 2024-11-06T12:20:01Z day: '01' doi: 10.1145/2746539.2746592 extern: '1' external_id: arxiv: - '1504.02268' fulldoi: https://doi.org/10.1145/2746539.2746592 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1504.02268 month: '06' oa: 1 oa_version: Preprint page: 173 - 182 publication: 47th Annual ACM Symposium on Theory of Computing publication_identifier: isbn: - 978-145033536-2 issn: - 0737-8017 publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' scopus_import: '1' status: public title: Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ... --- _id: '11901' abstract: - lang: eng text: We consider auctions of indivisible items to unit-demand bidders with budgets. This setting was suggested as an expressive model for single sponsored search auctions. Prior work presented mechanisms that compute bidder-optimal outcomes and are truthful for a restricted set of inputs, i.e., inputs in so-called general position. This condition is easily violated. We provide the first mechanism that is truthful in expectation for all inputs and achieves for each bidder no worse utility than the bidder-optimal outcome. Additionally we give a complete characterization for which inputs mechanisms that compute bidder-optimal outcomes are truthful. article_processing_charge: No article_type: original author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Veronika full_name: Loitzenbauer, Veronika last_name: Loitzenbauer citation: ama: Henzinger M, Loitzenbauer V. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 2015;573:1-15. doi:10.1016/j.tcs.2015.01.033 apa: Henzinger, M., & Loitzenbauer, V. (2015). Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2015.01.033 chicago: Henzinger, Monika, and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions with Budgets Revisited.” Theoretical Computer Science. Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.01.033. ieee: M. Henzinger and V. Loitzenbauer, “Truthful unit-demand auctions with budgets revisited,” Theoretical Computer Science, vol. 573. Elsevier, pp. 1–15, 2015. ista: Henzinger M, Loitzenbauer V. 2015. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 573, 1–15. mla: Henzinger, Monika, and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions with Budgets Revisited.” Theoretical Computer Science, vol. 573, Elsevier, 2015, pp. 1–15, doi:10.1016/j.tcs.2015.01.033. short: M. Henzinger, V. Loitzenbauer, Theoretical Computer Science 573 (2015) 1–15. date_created: 2022-08-17T09:06:53Z date_published: 2015-03-30T00:00:00Z date_updated: 2024-11-06T12:24:01Z day: '30' doi: 10.1016/j.tcs.2015.01.033 extern: '1' fulldoi: https://doi.org/10.1016/j.tcs.2015.01.033 intvolume: ' 573' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1016/j.tcs.2015.01.033 month: '03' oa: 1 oa_version: None page: 1-15 publication: Theoretical Computer Science publication_identifier: issn: - 0304-3975 publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: Truthful unit-demand auctions with budgets revisited type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 573 year: '2015' ... --- _id: '11962' abstract: - lang: eng text: One of the rare alternative reagents for the reduction of carbon–carbon double bonds is diimide (HNNH), which can be generated in situ from hydrazine hydrate (N2H4⋅H2O) and O2. Although this selective method is extremely clean and powerful, it is rarely used, as the rate-determining oxidation of hydrazine in the absence of a catalyst is relatively slow using conventional batch protocols. A continuous high-temperature/high-pressure methodology dramatically enhances the initial oxidation step, at the same time allowing for a safe and scalable processing of the hazardous reaction mixture. Simple alkenes can be selectively reduced within 10–20 min at 100–120 °C and 20 bar O2 pressure. The development of a multi-injection reactor platform for the periodic addition of N2H4⋅H2O enables the reduction of less reactive olefins even at lower reaction temperatures. This concept was utilized for the highly selective reduction of artemisinic acid to dihydroartemisinic acid, the precursor molecule for the semisynthesis of the antimalarial drug artemisinin. The industrially relevant reduction was achieved by using four consecutive liquid feeds (of N2H4⋅H2O) and residence time units resulting in a highly selective reduction within approximately 40 min at 60 °C and 20 bar O2 pressure, providing dihydroartemisinic acid in ≥93 % yield and ≥95 % selectivity. article_processing_charge: No article_type: original author: - first_name: Bartholomäus full_name: Pieber, Bartholomäus id: 93e5e5b2-0da6-11ed-8a41-af589a024726 last_name: Pieber orcid: 0000-0001-8689-388X - first_name: Toma full_name: Glasnov, Toma last_name: Glasnov - first_name: C. Oliver full_name: Kappe, C. Oliver last_name: Kappe citation: ama: Pieber B, Glasnov T, Kappe CO. Continuous flow reduction of artemisinic acid utilizing multi-injection strategies-closing the gap towards a fully continuous synthesis of antimalarial drugs. Chemistry - A European Journal. 2015;21(11):4368-4376. doi:10.1002/chem.201406439 apa: Pieber, B., Glasnov, T., & Kappe, C. O. (2015). Continuous flow reduction of artemisinic acid utilizing multi-injection strategies-closing the gap towards a fully continuous synthesis of antimalarial drugs. Chemistry - A European Journal. Wiley. https://doi.org/10.1002/chem.201406439 chicago: Pieber, Bartholomäus, Toma Glasnov, and C. Oliver Kappe. “Continuous Flow Reduction of Artemisinic Acid Utilizing Multi-Injection Strategies-Closing the Gap towards a Fully Continuous Synthesis of Antimalarial Drugs.” Chemistry - A European Journal. Wiley, 2015. https://doi.org/10.1002/chem.201406439. ieee: B. Pieber, T. Glasnov, and C. O. Kappe, “Continuous flow reduction of artemisinic acid utilizing multi-injection strategies-closing the gap towards a fully continuous synthesis of antimalarial drugs,” Chemistry - A European Journal, vol. 21, no. 11. Wiley, pp. 4368–4376, 2015. ista: Pieber B, Glasnov T, Kappe CO. 2015. Continuous flow reduction of artemisinic acid utilizing multi-injection strategies-closing the gap towards a fully continuous synthesis of antimalarial drugs. Chemistry - A European Journal. 21(11), 4368–4376. mla: Pieber, Bartholomäus, et al. “Continuous Flow Reduction of Artemisinic Acid Utilizing Multi-Injection Strategies-Closing the Gap towards a Fully Continuous Synthesis of Antimalarial Drugs.” Chemistry - A European Journal, vol. 21, no. 11, Wiley, 2015, pp. 4368–76, doi:10.1002/chem.201406439. short: B. Pieber, T. Glasnov, C.O. Kappe, Chemistry - A European Journal 21 (2015) 4368–4376. date_created: 2022-08-24T11:11:10Z date_published: 2015-03-09T00:00:00Z date_updated: 2023-02-21T10:09:30Z day: '09' doi: 10.1002/chem.201406439 extern: '1' external_id: pmid: - '25655090' fulldoi: https://doi.org/10.1002/chem.201406439 intvolume: ' 21' issue: '11' language: - iso: eng month: '03' oa_version: None page: 4368-4376 pmid: 1 publication: Chemistry - A European Journal publication_identifier: eissn: - 1521-3765 issn: - 0947-6539 publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: Continuous flow reduction of artemisinic acid utilizing multi-injection strategies-closing the gap towards a fully continuous synthesis of antimalarial drugs type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 21 year: '2015' ... --- _id: '11977' abstract: - lang: eng text: The development of a continuous flow multistep strategy for the synthesis of linear peptoids and their subsequent macrocyclization via Click chemistry is described. The central transformation of this process is an Ugi four-component reaction generating the peptidomimetic core structure. In order to avoid exposure to the often toxic and malodorous isocyanide building blocks, the continuous approach was telescoped by the dehydration of the corresponding formamide. In a concurrent operation, the highly energetic azide moiety required for the subsequent intramolecular copper-catalyzed azide–alkyne cycloaddition (Click reaction) was installed by nucleophilic substitution from a bromide precursor. All steps yielding to the linear core structures can be conveniently coupled without the need for purification steps resulting in a single process generating the desired peptidomimetics in good to excellent yields within a 25 min reaction time. The following macrocyclization was realized in a coil reactor made of copper without any additional additive. A careful process intensification study demonstrated that this transformation occurs quantitatively within 25 min at 140 °C. Depending on the resulting ring strain, either a dimeric or a monomeric form of the cyclic product was obtained. article_processing_charge: No article_type: original author: - first_name: Carlos Eduardo M. full_name: Salvador, Carlos Eduardo M. last_name: Salvador - first_name: Bartholomäus full_name: Pieber, Bartholomäus id: 93e5e5b2-0da6-11ed-8a41-af589a024726 last_name: Pieber orcid: 0000-0001-8689-388X - first_name: Philipp M. full_name: Neu, Philipp M. last_name: Neu - first_name: Ana full_name: Torvisco, Ana last_name: Torvisco - first_name: Carlos full_name: Kleber Z. Andrade, Carlos last_name: Kleber Z. Andrade - first_name: C. Oliver full_name: Kappe, C. Oliver last_name: Kappe citation: ama: Salvador CEM, Pieber B, Neu PM, Torvisco A, Kleber Z. Andrade C, Kappe CO. A sequential Ugi multicomponent/Cu-catalyzed azide–alkyne cycloaddition approach for the continuous flow generation of cyclic peptoids. The Journal of Organic Chemistry. 2015;80(9):4590-4602. doi:10.1021/acs.joc.5b00445 apa: Salvador, C. E. M., Pieber, B., Neu, P. M., Torvisco, A., Kleber Z. Andrade, C., & Kappe, C. O. (2015). A sequential Ugi multicomponent/Cu-catalyzed azide–alkyne cycloaddition approach for the continuous flow generation of cyclic peptoids. The Journal of Organic Chemistry. American Chemical Society. https://doi.org/10.1021/acs.joc.5b00445 chicago: Salvador, Carlos Eduardo M., Bartholomäus Pieber, Philipp M. Neu, Ana Torvisco, Carlos Kleber Z. Andrade, and C. Oliver Kappe. “A Sequential Ugi Multicomponent/Cu-Catalyzed Azide–Alkyne Cycloaddition Approach for the Continuous Flow Generation of Cyclic Peptoids.” The Journal of Organic Chemistry. American Chemical Society, 2015. https://doi.org/10.1021/acs.joc.5b00445. ieee: C. E. M. Salvador, B. Pieber, P. M. Neu, A. Torvisco, C. Kleber Z. Andrade, and C. O. Kappe, “A sequential Ugi multicomponent/Cu-catalyzed azide–alkyne cycloaddition approach for the continuous flow generation of cyclic peptoids,” The Journal of Organic Chemistry, vol. 80, no. 9. American Chemical Society, pp. 4590–4602, 2015. ista: Salvador CEM, Pieber B, Neu PM, Torvisco A, Kleber Z. Andrade C, Kappe CO. 2015. A sequential Ugi multicomponent/Cu-catalyzed azide–alkyne cycloaddition approach for the continuous flow generation of cyclic peptoids. The Journal of Organic Chemistry. 80(9), 4590–4602. mla: Salvador, Carlos Eduardo M., et al. “A Sequential Ugi Multicomponent/Cu-Catalyzed Azide–Alkyne Cycloaddition Approach for the Continuous Flow Generation of Cyclic Peptoids.” The Journal of Organic Chemistry, vol. 80, no. 9, American Chemical Society, 2015, pp. 4590–602, doi:10.1021/acs.joc.5b00445. short: C.E.M. Salvador, B. Pieber, P.M. Neu, A. Torvisco, C. Kleber Z. Andrade, C.O. Kappe, The Journal of Organic Chemistry 80 (2015) 4590–4602. date_created: 2022-08-25T10:52:24Z date_published: 2015-05-01T00:00:00Z date_updated: 2023-02-21T10:10:04Z day: '01' doi: 10.1021/acs.joc.5b00445 extern: '1' external_id: pmid: - '25842982' fulldoi: https://doi.org/10.1021/acs.joc.5b00445 intvolume: ' 80' issue: '9' language: - iso: eng month: '05' oa_version: None page: 4590-4602 pmid: 1 publication: The Journal of Organic Chemistry publication_identifier: eissn: - 1520-6904 issn: - 0022-3263 publication_status: published publisher: American Chemical Society quality_controlled: '1' scopus_import: '1' status: public title: A sequential Ugi multicomponent/Cu-catalyzed azide–alkyne cycloaddition approach for the continuous flow generation of cyclic peptoids type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 80 year: '2015' ... --- _id: '11989' abstract: - lang: eng text: In recent years, the high demand for sustainable processes resulted in the development of highly attractive oxidation protocols utilizing molecular oxygen or even air instead of more uneconomic and often toxic reagents. The application of these sustainable, gaseous oxidants in conventional batch reactors is often associated with severe safety risks and process challenges especially on larger scales. Continuous flow technology offers the possibility to minimize these safety hazards and concurrently allows working in high-temperature/high-pressure regimes to access highly efficient oxidation protocols. This review article critically discusses recent literature examples of flow methodologies for selective aerobic oxidations of organic compounds. Several technologies and reactor designs for biphasic gas/liquid as well as supercritical reaction media are presented in detail. © Springer International Publishing Switzerland 2015. alternative_title: - Topics in Organometallic Chemistry article_processing_charge: No author: - first_name: Bartholomäus full_name: Pieber, Bartholomäus id: 93e5e5b2-0da6-11ed-8a41-af589a024726 last_name: Pieber orcid: 0000-0001-8689-388X - first_name: C. Oliver full_name: Kappe, C. Oliver last_name: Kappe citation: ama: 'Pieber B, Kappe CO. Aerobic oxidations in continuous flow. In: Noël T, ed. Organometallic Flow Chemistry. Vol 57. 1st ed. TOPORGAN. Cham: Springer Nature; 2015:97–136. doi:10.1007/3418_2015_133' apa: 'Pieber, B., & Kappe, C. O. (2015). Aerobic oxidations in continuous flow. In T. Noël (Ed.), Organometallic Flow Chemistry (1st ed., Vol. 57, pp. 97–136). Cham: Springer Nature. https://doi.org/10.1007/3418_2015_133' chicago: 'Pieber, Bartholomäus, and C. Oliver Kappe. “Aerobic Oxidations in Continuous Flow.” In Organometallic Flow Chemistry, edited by Timothy Noël, 1st ed., 57:97–136. TOPORGAN. Cham: Springer Nature, 2015. https://doi.org/10.1007/3418_2015_133.' ieee: 'B. Pieber and C. O. Kappe, “Aerobic oxidations in continuous flow,” in Organometallic Flow Chemistry, 1st ed., vol. 57, T. Noël, Ed. Cham: Springer Nature, 2015, pp. 97–136.' ista: 'Pieber B, Kappe CO. 2015.Aerobic oxidations in continuous flow. In: Organometallic Flow Chemistry. Topics in Organometallic Chemistry, vol. 57, 97–136.' mla: Pieber, Bartholomäus, and C. Oliver Kappe. “Aerobic Oxidations in Continuous Flow.” Organometallic Flow Chemistry, edited by Timothy Noël, 1st ed., vol. 57, Springer Nature, 2015, pp. 97–136, doi:10.1007/3418_2015_133. short: B. Pieber, C.O. Kappe, in:, T. Noël (Ed.), Organometallic Flow Chemistry, 1st ed., Springer Nature, Cham, 2015, pp. 97–136. date_created: 2022-08-25T11:58:38Z date_published: 2015-06-10T00:00:00Z date_updated: 2023-02-21T10:10:35Z day: '10' doi: 10.1007/3418_2015_133 edition: '1' editor: - first_name: Timothy full_name: Noël, Timothy last_name: Noël extern: '1' fulldoi: https://doi.org/10.1007/3418_2015_133 intvolume: ' 57' language: - iso: eng month: '06' oa_version: None page: 97–136 place: Cham publication: Organometallic Flow Chemistry publication_identifier: eisbn: - '9783319332437' eissn: - 1616-8534 isbn: - '9783319332413' issn: - 1436-6002 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' series_title: TOPORGAN status: public title: Aerobic oxidations in continuous flow type: book_chapter user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 57 year: '2015' ... --- _id: '120' abstract: - lang: eng text: Clustering of fine particles is of crucial importance in settings ranging from the early stages of planet formation to the coagulation of industrial powders and airborne pollutants. Models of such clustering typically focus on inelastic deformation and cohesion. However, even in charge-neutral particle systems comprising grains of the same dielectric material, tribocharging can generate large amounts of net positive or negative charge on individual particles, resulting in long-range electrostatic forces. The effects of such forces on cluster formation are not well understood and have so far not been studied in situ. Here we report the first observations of individual collide-and-capture events between charged submillimetre particles, including Kepler-like orbits. Charged particles can become trapped in their mutual electrostatic energy well and aggregate via multiple bounces. This enables the initiation of clustering at relative velocities much larger than the upper limit for sticking after a head-on collision, a long-standing issue known from pre-planetary dust aggregation. Moreover, Coulomb interactions together with dielectric polarization are found to stabilize characteristic molecule-like configurations, providing new insights for the modelling of clustering dynamics in a wide range of microscopic dielectric systems, such as charged polarizable ions, biomolecules and colloids. acknowledgement: This research was supported by NSF through DMR-1309611. The Chicago MRSEC, supported by NSF DMR-1420709, is gratefully acknowledged for access to its shared experimental facilities. author: - first_name: Victor full_name: Lee, Victor last_name: Lee - first_name: Scott R full_name: Waitukaitis, Scott R id: 3A1FFC16-F248-11E8-B48F-1D18A9856A87 last_name: Waitukaitis orcid: 0000-0002-2299-3176 - first_name: Marc full_name: Miskin, Marc last_name: Miskin - first_name: Heinrich full_name: Jaeger, Heinrich last_name: Jaeger citation: ama: Lee V, Waitukaitis SR, Miskin M, Jaeger H. Direct observation of particle interactions and clustering in charged granular streams. Nature Physics. 2015;11(9):733-737. doi:10.1038/nphys3396 apa: Lee, V., Waitukaitis, S. R., Miskin, M., & Jaeger, H. (2015). Direct observation of particle interactions and clustering in charged granular streams. Nature Physics. Nature Publishing Group. https://doi.org/10.1038/nphys3396 chicago: Lee, Victor, Scott R Waitukaitis, Marc Miskin, and Heinrich Jaeger. “Direct Observation of Particle Interactions and Clustering in Charged Granular Streams.” Nature Physics. Nature Publishing Group, 2015. https://doi.org/10.1038/nphys3396. ieee: V. Lee, S. R. Waitukaitis, M. Miskin, and H. Jaeger, “Direct observation of particle interactions and clustering in charged granular streams,” Nature Physics, vol. 11, no. 9. Nature Publishing Group, pp. 733–737, 2015. ista: Lee V, Waitukaitis SR, Miskin M, Jaeger H. 2015. Direct observation of particle interactions and clustering in charged granular streams. Nature Physics. 11(9), 733–737. mla: Lee, Victor, et al. “Direct Observation of Particle Interactions and Clustering in Charged Granular Streams.” Nature Physics, vol. 11, no. 9, Nature Publishing Group, 2015, pp. 733–37, doi:10.1038/nphys3396. short: V. Lee, S.R. Waitukaitis, M. Miskin, H. Jaeger, Nature Physics 11 (2015) 733–737. date_created: 2018-12-11T11:44:44Z date_published: 2015-07-13T00:00:00Z date_updated: 2021-01-12T06:49:02Z day: '13' doi: 10.1038/nphys3396 extern: '1' fulldoi: https://doi.org/10.1038/nphys3396 intvolume: ' 11' issue: '9' language: - iso: eng month: '07' oa_version: None page: 733 - 737 publication: Nature Physics publication_status: published publisher: Nature Publishing Group publist_id: '7934' quality_controlled: '1' status: public title: Direct observation of particle interactions and clustering in charged granular streams type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 11 year: '2015' ... --- _id: '121' abstract: - lang: eng text: We show that the simplest building blocks of origami-based materials - rigid, degree-four vertices - are generically multistable. The existence of two distinct branches of folding motion emerging from the flat state suggests at least bistability, but we show how nonlinearities in the folding motions allow generic vertex geometries to have as many as five stable states. In special geometries with collinear folds and symmetry, more branches emerge leading to as many as six stable states. Tuning the fold energy parameters, we show how monostability is also possible. Finally, we show how to program the stability features of a single vertex into a periodic fold tessellation. The resulting metasheets provide a previously unanticipated functionality - tunable and switchable shape and size via multistability. acknowledgement: B. G. C. acknowledges support from FOM, and S. W. and M. v. H. acknowledge support from NWO. article_number: '055503' arxiv: 1 author: - first_name: Scott R full_name: Waitukaitis, Scott R id: 3A1FFC16-F248-11E8-B48F-1D18A9856A87 last_name: Waitukaitis orcid: 0000-0002-2299-3176 - first_name: Rémi full_name: Menaut, Rémi last_name: Menaut - first_name: Bryan full_name: Chen, Bryan last_name: Chen - first_name: Martin full_name: Van Hecke, Martin last_name: Van Hecke citation: ama: 'Waitukaitis SR, Menaut R, Chen B, Van Hecke M. Origami multistability: From single vertices to metasheets. APS Physics, Physical Review Letters. 2015;114(5). doi:10.1103/PhysRevLett.114.055503' apa: 'Waitukaitis, S. R., Menaut, R., Chen, B., & Van Hecke, M. (2015). Origami multistability: From single vertices to metasheets. APS Physics, Physical Review Letters. American Physical Society. https://doi.org/10.1103/PhysRevLett.114.055503' chicago: 'Waitukaitis, Scott R, Rémi Menaut, Bryan Chen, and Martin Van Hecke. “Origami Multistability: From Single Vertices to Metasheets.” APS Physics, Physical Review Letters. American Physical Society, 2015. https://doi.org/10.1103/PhysRevLett.114.055503.' ieee: 'S. R. Waitukaitis, R. Menaut, B. Chen, and M. Van Hecke, “Origami multistability: From single vertices to metasheets,” APS Physics, Physical Review Letters, vol. 114, no. 5. American Physical Society, 2015.' ista: 'Waitukaitis SR, Menaut R, Chen B, Van Hecke M. 2015. Origami multistability: From single vertices to metasheets. APS Physics, Physical Review Letters. 114(5), 055503.' mla: 'Waitukaitis, Scott R., et al. “Origami Multistability: From Single Vertices to Metasheets.” APS Physics, Physical Review Letters, vol. 114, no. 5, 055503, American Physical Society, 2015, doi:10.1103/PhysRevLett.114.055503.' short: S.R. Waitukaitis, R. Menaut, B. Chen, M. Van Hecke, APS Physics, Physical Review Letters 114 (2015). date_created: 2018-12-11T11:44:44Z date_published: 2015-02-04T00:00:00Z date_updated: 2021-01-12T06:49:07Z day: '04' doi: 10.1103/PhysRevLett.114.055503 extern: '1' external_id: arxiv: - '1408.1607' fulldoi: https://doi.org/10.1103/PhysRevLett.114.055503 intvolume: ' 114' issue: '5' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1408.1607 month: '02' oa: 1 oa_version: Preprint publication: APS Physics, Physical Review Letters publication_status: published publisher: American Physical Society publist_id: '7933' quality_controlled: '1' status: public title: 'Origami multistability: From single vertices to metasheets' type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 114 year: '2015' ... --- _id: '2271' abstract: - lang: eng text: "A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. Finite-valued constraint languages contain functions that take on rational costs and general-valued constraint languages contain functions that take on rational or infinite costs. An instance of the problem is specified by a sum of functions from the language with the goal to minimise the sum. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs).\r\nOur main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a general-valued constraint language Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language Γ, BLP is a decision procedure if and only if Γ admits a symmetric fractional polymorphism of some arity, or equivalently, if Γ admits a symmetric fractional polymorphism of arity 2.\r\nUsing these results, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) bisubmodular (also known as k-submodular) on arbitrary finite domains; (3) weakly (and hence strongly) tree-submodular on arbitrary trees. " article_processing_charge: No arxiv: 1 author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Johan full_name: Thapper, Johan last_name: Thapper - first_name: Stanislav full_name: Živný, Stanislav last_name: Živný citation: ama: Kolmogorov V, Thapper J, Živný S. The power of linear programming for general-valued CSPs. SIAM Journal on Computing. 2015;44(1):1-36. doi:10.1137/130945648 apa: Kolmogorov, V., Thapper, J., & Živný, S. (2015). The power of linear programming for general-valued CSPs. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/130945648 chicago: Kolmogorov, Vladimir, Johan Thapper, and Stanislav Živný. “The Power of Linear Programming for General-Valued CSPs.” SIAM Journal on Computing. SIAM, 2015. https://doi.org/10.1137/130945648. ieee: V. Kolmogorov, J. Thapper, and S. Živný, “The power of linear programming for general-valued CSPs,” SIAM Journal on Computing, vol. 44, no. 1. SIAM, pp. 1–36, 2015. ista: Kolmogorov V, Thapper J, Živný S. 2015. The power of linear programming for general-valued CSPs. SIAM Journal on Computing. 44(1), 1–36. mla: Kolmogorov, Vladimir, et al. “The Power of Linear Programming for General-Valued CSPs.” SIAM Journal on Computing, vol. 44, no. 1, SIAM, 2015, pp. 1–36, doi:10.1137/130945648. short: V. Kolmogorov, J. Thapper, S. Živný, SIAM Journal on Computing 44 (2015) 1–36. date_created: 2018-12-11T11:56:41Z date_published: 2015-02-01T00:00:00Z date_updated: 2025-09-23T14:14:57Z day: '01' department: - _id: VlKo doi: 10.1137/130945648 external_id: arxiv: - '1311.4219' isi: - '000353967100001' fulldoi: https://doi.org/10.1137/130945648 intvolume: ' 44' isi: 1 issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1311.4219 month: '02' oa: 1 oa_version: Preprint page: 1 - 36 publication: SIAM Journal on Computing publication_status: published publisher: SIAM publist_id: '4673' quality_controlled: '1' related_material: record: - id: '2518' relation: earlier_version status: public scopus_import: '1' status: public title: The power of linear programming for general-valued CSPs type: journal_article user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 44 year: '2015' ... --- OA_place: repository OA_type: green _id: '257' abstract: - lang: eng text: For suitable pairs of diagonal quadratic forms in eight variables we use the circle method to investigate the density of simultaneous integer solutions and relate this to the problem of estimating linear correlations among sums of two squares. acknowledgement: While working on this paper the first author was supported by ERC grant 306457 and the second author was supported by SwarnaJayanti Fellowship 2011–12, DST, Government of India. article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Timothy D full_name: Browning, Timothy D id: 35827D50-F248-11E8-B48F-1D18A9856A87 last_name: Browning orcid: 0000-0002-8314-0177 - first_name: Ritabrata full_name: Munshi, Ritabrata last_name: Munshi citation: ama: Browning TD, Munshi R. Pairs of diagonal quadratic forms and linear correlations among sums of two squares. Forum Mathematicum. 2015;27(4):2025-2050. doi:10.1515/forum-2013-6024 apa: Browning, T. D., & Munshi, R. (2015). Pairs of diagonal quadratic forms and linear correlations among sums of two squares. Forum Mathematicum. De Gruyter. https://doi.org/10.1515/forum-2013-6024 chicago: Browning, Timothy D, and Ritabrata Munshi. “Pairs of Diagonal Quadratic Forms and Linear Correlations among Sums of Two Squares.” Forum Mathematicum. De Gruyter, 2015. https://doi.org/10.1515/forum-2013-6024. ieee: T. D. Browning and R. Munshi, “Pairs of diagonal quadratic forms and linear correlations among sums of two squares,” Forum Mathematicum, vol. 27, no. 4. De Gruyter, pp. 2025–2050, 2015. ista: Browning TD, Munshi R. 2015. Pairs of diagonal quadratic forms and linear correlations among sums of two squares. Forum Mathematicum. 27(4), 2025–2050. mla: Browning, Timothy D., and Ritabrata Munshi. “Pairs of Diagonal Quadratic Forms and Linear Correlations among Sums of Two Squares.” Forum Mathematicum, vol. 27, no. 4, De Gruyter, 2015, pp. 2025–50, doi:10.1515/forum-2013-6024. short: T.D. Browning, R. Munshi, Forum Mathematicum 27 (2015) 2025–2050. date_created: 2018-12-11T11:45:28Z date_published: 2015-07-10T00:00:00Z date_updated: 2026-05-19T13:08:06Z day: '10' doi: 10.1515/forum-2013-6024 extern: '1' external_id: arxiv: - '1302.2434' fulldoi: https://doi.org/10.1515/forum-2013-6024 intvolume: ' 27' issue: '4' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1302.2434 month: '07' oa: 1 oa_version: Preprint page: 2025 - 2050 publication: Forum Mathematicum publication_identifier: eissn: - 1435-5337 issn: - 0933-7741 publication_status: published publisher: De Gruyter publist_id: '7645' quality_controlled: '1' scopus_import: '1' status: public title: Pairs of diagonal quadratic forms and linear correlations among sums of two squares type: journal_article user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd volume: 27 year: '2015' ... --- _id: '258' abstract: - lang: eng text: Given a number field k and a projective algebraic variety X defined over k, the question of whether X contains a k-rational point is both very natural and very difficult. In the event that the set X(k) of k-rational points is not empty, one can also ask how the points of X(k) are distributed. Are they dense in X under the Zariski topology? Are they dense in the set. author: - first_name: Timothy D full_name: Browning, Timothy D id: 35827D50-F248-11E8-B48F-1D18A9856A87 last_name: Browning orcid: 0000-0002-8314-0177 citation: ama: 'Browning TD. A survey of applications of the circle method to rational points. In: Arithmetic and Geometry. Cambridge University Press; 2015:89-113. doi:10.1017/CBO9781316106877.009' apa: Browning, T. D. (2015). A survey of applications of the circle method to rational points. In Arithmetic and Geometry (pp. 89–113). Cambridge University Press. https://doi.org/10.1017/CBO9781316106877.009 chicago: Browning, Timothy D. “A Survey of Applications of the Circle Method to Rational Points.” In Arithmetic and Geometry, 89–113. Cambridge University Press, 2015. https://doi.org/10.1017/CBO9781316106877.009. ieee: T. D. Browning, “A survey of applications of the circle method to rational points,” in Arithmetic and Geometry, Cambridge University Press, 2015, pp. 89–113. ista: 'Browning TD. 2015.A survey of applications of the circle method to rational points. In: Arithmetic and Geometry. , 89–113.' mla: Browning, Timothy D. “A Survey of Applications of the Circle Method to Rational Points.” Arithmetic and Geometry, Cambridge University Press, 2015, pp. 89–113, doi:10.1017/CBO9781316106877.009. short: T.D. Browning, in:, Arithmetic and Geometry, Cambridge University Press, 2015, pp. 89–113. date_created: 2018-12-11T11:45:28Z date_published: 2015-08-01T00:00:00Z date_updated: 2021-01-12T06:58:22Z day: '01' doi: 10.1017/CBO9781316106877.009 extern: '1' fulldoi: https://doi.org/10.1017/CBO9781316106877.009 language: - iso: eng month: '08' oa_version: None page: 89 - 113 publication: Arithmetic and Geometry publication_status: published publisher: Cambridge University Press publist_id: '7644' quality_controlled: '1' status: public title: A survey of applications of the circle method to rational points type: book_chapter user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ...