--- _id: '10045' abstract: - lang: eng text: "Given a fixed finite metric space (V,μ), the {\\em minimum 0-extension problem}, denoted as 0-Ext[μ], is equivalent to the following optimization problem: minimize function of the form minx∈Vn∑ifi(xi)+∑ijcijμ(xi,xj) where cij,cvi are given nonnegative costs and fi:V→R are functions given by fi(xi)=∑v∈Vcviμ(xi,v). The computational complexity of 0-Ext[μ] has been recently established by Karzanov and by Hirai: if metric μ is {\\em orientable modular} then 0-Ext[μ] can be solved in polynomial time, otherwise 0-Ext[μ] is NP-hard. To prove the tractability part, Hirai developed a theory of discrete convex functions on orientable modular graphs generalizing several known classes of functions in discrete convex analysis, such as L♮-convex functions. We consider a more general version of the problem in which unary functions fi(xi) can additionally have terms of the form cuv;iμ(xi,{u,v}) for {u,v}∈F, where set F⊆(V2) is fixed. We extend the complexity classification above by providing an explicit condition on (μ,F) for the problem to be tractable. In order to prove the tractability part, we generalize Hirai's theory and define a larger class of discrete convex functions. It covers, in particular, another well-known class of functions, namely submodular functions on an integer lattice. Finally, we improve the complexity of Hirai's algorithm for solving 0-Ext on orientable modular graphs.\r\n" acknowledgement: We thank the anonymous reviewers for their careful reading of our manuscript and their many insightful comments and suggestions. Open access funding provided by Institute of Science and Technology (IST Austria). article_number: '2109.10203' article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Martin full_name: Dvorak, Martin id: 40ED02A8-C8B4-11E9-A9C0-453BE6697425 last_name: Dvorak orcid: 0000-0001-5293-214X - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete convexity. Mathematical Programming. 2024. doi:10.1007/s10107-024-02064-5 apa: Dvorak, M., & Kolmogorov, V. (2024). Generalized minimum 0-extension problem and discrete convexity. Mathematical Programming. Springer Nature. https://doi.org/10.1007/s10107-024-02064-5 chicago: Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” Mathematical Programming. Springer Nature, 2024. https://doi.org/10.1007/s10107-024-02064-5. ieee: M. Dvorak and V. Kolmogorov, “Generalized minimum 0-extension problem and discrete convexity,” Mathematical Programming. Springer Nature, 2024. ista: Dvorak M, Kolmogorov V. 2024. Generalized minimum 0-extension problem and discrete convexity. Mathematical Programming., 2109.10203. mla: Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” Mathematical Programming, 2109.10203, Springer Nature, 2024, doi:10.1007/s10107-024-02064-5. short: M. Dvorak, V. Kolmogorov, Mathematical Programming (2024). date_created: 2021-09-27T10:48:23Z date_published: 2024-03-07T00:00:00Z date_updated: 2024-03-19T08:20:31Z day: '07' ddc: - '004' department: - _id: GradSch - _id: VlKo doi: 10.1007/s10107-024-02064-5 external_id: arxiv: - '2109.10203' file: - access_level: open_access checksum: e7e83065f7bc18b9c188bf93b5ca5db6 content_type: application/pdf creator: mdvorak date_created: 2021-09-27T10:54:51Z date_updated: 2021-09-27T10:54:51Z file_id: '10046' file_name: Generalized-0-Ext.pdf file_size: 603672 relation: main_file success: 1 file_date_updated: 2021-09-27T10:54:51Z has_accepted_license: '1' keyword: - minimum 0-extension problem - metric labeling problem - discrete metric spaces - metric extensions - computational complexity - valued constraint satisfaction problems - discrete convex analysis - L-convex functions language: - iso: eng month: '03' oa: 1 oa_version: Preprint publication: Mathematical Programming publication_identifier: eissn: - 1436-4646 issn: - 0025-5610 publication_status: epub_ahead publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Generalized minimum 0-extension problem and discrete convexity 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 year: '2024' ... --- _id: '15121' abstract: - lang: eng text: We present an auction algorithm using multiplicative instead of constant weight updates to compute a (1-E)-approximate maximum weight matching (MWM) in a bipartite graph with n vertices and m edges in time 0(mE-1), beating the running time of the fastest known approximation algorithm of Duan and Pettie [JACM ’14] that runs in 0(mE-1 log E-1). Our algorithm is very simple and it can be extended to give a dynamic data structure that maintains a (1-E)-approximate maximum weight matching under (1) one-sided vertex deletions (with incident edges) and (2) one-sided vertex insertions (with incident edges sorted by weight) to the other side. The total time time used is 0(mE-1), where m is the sum of the number of initially existing and inserted edges. acknowledgement: The first author thanks Chandra Chekuri for useful discussions about this paper. This work was done in part at the University of Vienna. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. article_processing_charge: No article_type: original author: - first_name: Da Wei full_name: Zheng, Da Wei last_name: Zheng - 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: Zheng DW, Henzinger MH. Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. 2024. doi:10.1007/s10107-024-02066-3 apa: Zheng, D. W., & Henzinger, M. H. (2024). Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. Springer Nature. https://doi.org/10.1007/s10107-024-02066-3 chicago: Zheng, Da Wei, and Monika H Henzinger. “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching.” Mathematical Programming. Springer Nature, 2024. https://doi.org/10.1007/s10107-024-02066-3. ieee: D. W. Zheng and M. H. Henzinger, “Multiplicative auction algorithm for approximate maximum weight bipartite matching,” Mathematical Programming. Springer Nature, 2024. ista: Zheng DW, Henzinger MH. 2024. Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. mla: Zheng, Da Wei, and Monika H. Henzinger. “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching.” Mathematical Programming, Springer Nature, 2024, doi:10.1007/s10107-024-02066-3. short: D.W. Zheng, M.H. Henzinger, Mathematical Programming (2024). date_created: 2024-03-17T23:00:58Z date_published: 2024-03-06T00:00:00Z date_updated: 2024-03-19T08:32:32Z day: '06' department: - _id: MoHe doi: 10.1007/s10107-024-02066-3 ec_funded: 1 external_id: arxiv: - '2301.09217' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2301.09217 month: '03' oa: 1 oa_version: Preprint project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: 'P33775 ' name: Fast Algorithms for a Reactive Network Layer publication: Mathematical Programming publication_identifier: eissn: - 1436-4646 issn: - 0025-5610 publication_status: epub_ahead publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '13236' relation: earlier_version status: public scopus_import: '1' status: public title: Multiplicative auction algorithm for approximate maximum weight bipartite matching type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2024' ... --- _id: '15116' abstract: - lang: eng text: Water is known to play an important role in collagen self-assembly, but it is still largely unclear how water–collagen interactions influence the assembly process and determine the fibril network properties. Here, we use the H2O/D2O isotope effect on the hydrogen-bond strength in water to investigate the role of hydration in collagen self-assembly. We dissolve collagen in H2O and D2O and compare the growth kinetics and the structure of the collagen assemblies formed in these water isotopomers. Surprisingly, collagen assembly occurs ten times faster in D2O than in H2O, and collagen in D2O self-assembles into much thinner fibrils, that form a more inhomogeneous and softer network, with a fourfold reduction in elastic modulus when compared to H2O. Combining spectroscopic measurements with atomistic simulations, we show that collagen in D2O is less hydrated than in H2O. This partial dehydration lowers the enthalpic penalty for water removal and reorganization at the collagen–water interface, increasing the self-assembly rate and the number of nucleation centers, leading to thinner fibrils and a softer network. Coarse-grained simulations show that the acceleration in the initial nucleation rate can be reproduced by the enhancement of electrostatic interactions. These results show that water acts as a mediator between collagen monomers, by modulating their interactions so as to optimize the assembly process and, thus, the final network properties. We believe that isotopically modulating the hydration of proteins can be a valuable method to investigate the role of water in protein structural dynamics and protein self-assembly. acknowledgement: We thank Dr. Steven Roeters (Aarhus University), Dr. Federica Burla, and Prof. Dr. Mischa Bonn (Institute for Polymer Research, Mainz, Germany) for the useful discussions. We thank Dr. Wim Roeterdink and Michiel Hilberts for technical support. G.H.K. acknowledges financial support by the “BaSyC Building a Synthetic Cell” Gravitation grant (024.003.019) of The Netherlands Ministry of Education, Culture and Science (OCW) and The Netherlands Organization for Scientific Research and from NWO grant OCENW.GROOT.2019.022. This work has received support from the National Research Foundation of Korea (NRF), funded by the Ministry of Science and ICT, under Grant No. 2022K1A3A1A04062969. This publication is part of the project (with Project Number VI.Veni.212.240) of the research programme NWO Talent Programme Veni 2021, which is financed by the Dutch Research Council (NWO). I.M.I. acknowledges support from the Sectorplan Bèta & Techniek of the Dutch Government and the Dementia Research - Synapsis Foundation Switzerland. A.Š. and K.K. acknowledge support from Royal Society and European Research Council Starting Grant. G. Giubertoni kindly thanks to the Care4Bones community and the Collagen Café community for reminding that we do not own the knowledge we create, but it is, rather, a collective resource intended for the advancement of human progress. article_number: e2313162121 article_processing_charge: Yes (in subscription journal) article_type: original author: - first_name: Giulia full_name: Giubertoni, Giulia last_name: Giubertoni - first_name: Liru full_name: Feng, Liru last_name: Feng - first_name: Kevin full_name: Klein, Kevin last_name: Klein - first_name: Guido full_name: Giannetti, Guido last_name: Giannetti - first_name: Luco full_name: Rutten, Luco last_name: Rutten - first_name: Yeji full_name: Choi, Yeji last_name: Choi - first_name: Anouk full_name: Van Der Net, Anouk last_name: Van Der Net - first_name: Gerard full_name: Castro-Linares, Gerard last_name: Castro-Linares - first_name: Federico full_name: Caporaletti, Federico last_name: Caporaletti - first_name: Dimitra full_name: Micha, Dimitra last_name: Micha - first_name: Johannes full_name: Hunger, Johannes last_name: Hunger - first_name: Antoine full_name: Deblais, Antoine last_name: Deblais - first_name: Daniel full_name: Bonn, Daniel last_name: Bonn - first_name: Nico full_name: Sommerdijk, Nico last_name: Sommerdijk - first_name: Anđela full_name: Šarić, Anđela id: bf63d406-f056-11eb-b41d-f263a6566d8b last_name: Šarić orcid: 0000-0002-7854-2139 - first_name: Ioana M. full_name: Ilie, Ioana M. last_name: Ilie - first_name: Gijsje H. full_name: Koenderink, Gijsje H. last_name: Koenderink - first_name: Sander full_name: Woutersen, Sander last_name: Woutersen citation: ama: Giubertoni G, Feng L, Klein K, et al. Elucidating the role of water in collagen self-assembly by isotopically modulating collagen hydration. Proceedings of the National Academy of Sciences of the United States of America. 2024;121(11). doi:10.1073/pnas.2313162121 apa: Giubertoni, G., Feng, L., Klein, K., Giannetti, G., Rutten, L., Choi, Y., … Woutersen, S. (2024). Elucidating the role of water in collagen self-assembly by isotopically modulating collagen hydration. Proceedings of the National Academy of Sciences of the United States of America. Proceedings of the National Academy of Sciences. https://doi.org/10.1073/pnas.2313162121 chicago: Giubertoni, Giulia, Liru Feng, Kevin Klein, Guido Giannetti, Luco Rutten, Yeji Choi, Anouk Van Der Net, et al. “Elucidating the Role of Water in Collagen Self-Assembly by Isotopically Modulating Collagen Hydration.” Proceedings of the National Academy of Sciences of the United States of America. Proceedings of the National Academy of Sciences, 2024. https://doi.org/10.1073/pnas.2313162121. ieee: G. Giubertoni et al., “Elucidating the role of water in collagen self-assembly by isotopically modulating collagen hydration,” Proceedings of the National Academy of Sciences of the United States of America, vol. 121, no. 11. Proceedings of the National Academy of Sciences, 2024. ista: Giubertoni G, Feng L, Klein K, Giannetti G, Rutten L, Choi Y, Van Der Net A, Castro-Linares G, Caporaletti F, Micha D, Hunger J, Deblais A, Bonn D, Sommerdijk N, Šarić A, Ilie IM, Koenderink GH, Woutersen S. 2024. Elucidating the role of water in collagen self-assembly by isotopically modulating collagen hydration. Proceedings of the National Academy of Sciences of the United States of America. 121(11), e2313162121. mla: Giubertoni, Giulia, et al. “Elucidating the Role of Water in Collagen Self-Assembly by Isotopically Modulating Collagen Hydration.” Proceedings of the National Academy of Sciences of the United States of America, vol. 121, no. 11, e2313162121, Proceedings of the National Academy of Sciences, 2024, doi:10.1073/pnas.2313162121. short: G. Giubertoni, L. Feng, K. Klein, G. Giannetti, L. Rutten, Y. Choi, A. Van Der Net, G. Castro-Linares, F. Caporaletti, D. Micha, J. Hunger, A. Deblais, D. Bonn, N. Sommerdijk, A. Šarić, I.M. Ilie, G.H. Koenderink, S. Woutersen, Proceedings of the National Academy of Sciences of the United States of America 121 (2024). date_created: 2024-03-17T23:00:57Z date_published: 2024-03-12T00:00:00Z date_updated: 2024-03-19T11:41:32Z day: '12' ddc: - '550' department: - _id: AnSa doi: 10.1073/pnas.2313162121 external_id: pmid: - '38451946' file: - access_level: open_access checksum: a3f7fdc29dd9f0a38952ab4e322b3a05 content_type: application/pdf creator: dernst date_created: 2024-03-19T10:22:42Z date_updated: 2024-03-19T10:22:42Z file_id: '15125' file_name: 2024_PNAS_Giubertoni.pdf file_size: 12952586 relation: main_file success: 1 file_date_updated: 2024-03-19T10:22:42Z has_accepted_license: '1' intvolume: ' 121' issue: '11' language: - iso: eng month: '03' oa: 1 oa_version: Published Version pmid: 1 publication: Proceedings of the National Academy of Sciences of the United States of America publication_identifier: eissn: - 1091-6490 issn: - 0027-8424 publication_status: published publisher: Proceedings of the National Academy of Sciences quality_controlled: '1' related_material: record: - id: '15126' relation: research_data status: public scopus_import: '1' status: public title: Elucidating the role of water in collagen self-assembly by isotopically modulating collagen hydration 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: 121 year: '2024' ... --- _id: '15126' abstract: - lang: eng text: This zip file contains data, and analysis for the paper "Elucidating the role of water in collagen self-assembly by isotopically modulating collagen hydration". article_processing_charge: No author: - first_name: G. full_name: Giubertoni, G. last_name: Giubertoni - first_name: S. full_name: Woutersen, S. last_name: Woutersen citation: ama: Giubertoni G, Woutersen S. Dataset Collagen Self Assembly in H2O and D2O. 2024. doi:10.21942/UVA.24829896 apa: Giubertoni, G., & Woutersen, S. (2024). Dataset Collagen Self Assembly in H2O and D2O. Figshare. https://doi.org/10.21942/UVA.24829896 chicago: Giubertoni, G., and S. Woutersen. “Dataset Collagen Self Assembly in H2O and D2O.” Figshare, 2024. https://doi.org/10.21942/UVA.24829896. ieee: G. Giubertoni and S. Woutersen, “Dataset Collagen Self Assembly in H2O and D2O.” Figshare, 2024. ista: Giubertoni G, Woutersen S. 2024. Dataset Collagen Self Assembly in H2O and D2O, Figshare, 10.21942/UVA.24829896. mla: Giubertoni, G., and S. Woutersen. Dataset Collagen Self Assembly in H2O and D2O. Figshare, 2024, doi:10.21942/UVA.24829896. short: G. Giubertoni, S. Woutersen, (2024). date_created: 2024-03-19T10:47:16Z date_published: 2024-02-14T00:00:00Z date_updated: 2024-03-19T11:41:33Z day: '14' ddc: - '550' doi: 10.21942/UVA.24829896 extern: '1' has_accepted_license: '1' main_file_link: - open_access: '1' url: https://doi.org/10.21942/UVA.24829896 month: '02' oa: 1 oa_version: Published Version publisher: Figshare related_material: record: - id: '15116' relation: used_in_publication status: public status: public title: Dataset Collagen Self Assembly in H2O and D2O 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: research_data_reference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2024' ... --- _id: '15094' abstract: - lang: eng text: "Point sets, geometric networks, and arrangements of hyperplanes are fundamental objects in\r\ndiscrete geometry that have captivated mathematicians for centuries, if not millennia. This\r\nthesis seeks to cast new light on these structures by illustrating specific instances where a\r\ntopological perspective, specifically through discrete Morse theory and persistent homology,\r\nprovides valuable insights.\r\n\r\nAt first glance, the topology of these geometric objects might seem uneventful: point sets\r\nessentially lack of topology, arrangements of hyperplanes are a decomposition of Rd, which\r\nis a contractible space, and the topology of a network primarily involves the enumeration\r\nof connected components and cycles within the network. However, beneath this apparent\r\nsimplicity, there lies an array of intriguing structures, a small subset of which will be uncovered\r\nin this thesis.\r\n\r\nFocused on three case studies, each addressing one of the mentioned objects, this work\r\nwill showcase connections that intertwine topology with diverse fields such as combinatorial\r\ngeometry, algorithms and data structures, and emerging applications like spatial biology.\r\n\r\n" alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Sebastiano full_name: Cultrera di Montesano, Sebastiano id: 34D2A09C-F248-11E8-B48F-1D18A9856A87 last_name: Cultrera di Montesano orcid: 0000-0001-6249-0832 citation: ama: Cultrera di Montesano S. Persistence and Morse theory for discrete geometric structures. 2024. doi:10.15479/at:ista:15094 apa: Cultrera di Montesano, S. (2024). Persistence and Morse theory for discrete geometric structures. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:15094 chicago: Cultrera di Montesano, Sebastiano. “Persistence and Morse Theory for Discrete Geometric Structures.” Institute of Science and Technology Austria, 2024. https://doi.org/10.15479/at:ista:15094. ieee: S. Cultrera di Montesano, “Persistence and Morse theory for discrete geometric structures,” Institute of Science and Technology Austria, 2024. ista: Cultrera di Montesano S. 2024. Persistence and Morse theory for discrete geometric structures. Institute of Science and Technology Austria. mla: Cultrera di Montesano, Sebastiano. Persistence and Morse Theory for Discrete Geometric Structures. Institute of Science and Technology Austria, 2024, doi:10.15479/at:ista:15094. short: S. Cultrera di Montesano, Persistence and Morse Theory for Discrete Geometric Structures, Institute of Science and Technology Austria, 2024. date_created: 2024-03-08T15:28:10Z date_published: 2024-03-08T00:00:00Z date_updated: 2024-03-20T09:36:57Z day: '08' ddc: - '514' - '500' - '516' degree_awarded: PhD department: - _id: GradSch - _id: HeEd doi: 10.15479/at:ista:15094 ec_funded: 1 file: - access_level: open_access checksum: 1e468bfa42a7dcf04d89f4dadc621c87 content_type: application/pdf creator: scultrer date_created: 2024-03-14T08:55:07Z date_updated: 2024-03-14T08:55:07Z file_id: '15112' file_name: Thesis Sebastiano.pdf file_size: 4106872 relation: main_file success: 1 - access_level: closed checksum: bcbd213490f5a7e68855a092bbce93f1 content_type: application/zip creator: scultrer date_created: 2024-03-14T08:56:24Z date_updated: 2024-03-14T14:14:35Z file_id: '15113' file_name: Thesis (1).zip file_size: 4746234 relation: source_file file_date_updated: 2024-03-14T14:14:35Z has_accepted_license: '1' language: - iso: eng month: '03' oa: 1 oa_version: Published Version page: '108' project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: The Wittgenstein Prize - _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316 grant_number: I4887 name: Discretization in Geometry and Dynamics - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication_identifier: issn: - 2663 - 337X publication_status: published publisher: Institute of Science and Technology Austria related_material: record: - id: '11660' relation: part_of_dissertation status: public - id: '11658' relation: part_of_dissertation status: public - id: '13182' relation: part_of_dissertation status: public - id: '15090' relation: part_of_dissertation status: public - id: '15091' relation: part_of_dissertation status: public - id: '15093' relation: part_of_dissertation status: public status: public supervisor: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 title: Persistence and Morse theory for discrete geometric structures tmp: image: /images/cc_by_nc_sa.png legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) short: CC BY-NC-SA (4.0) type: dissertation user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9 year: '2024' ...