[{"publication":"Annales Fennici Mathematici","month":"04","status":"public","oa":1,"corr_author":"1","quality_controlled":"1","ddc":["510"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)","image":"/images/cc_by_nc.png"},"OA_place":"publisher","_id":"21766","scopus_import":"1","page":"237-260","date_created":"2026-04-26T22:01:47Z","keyword":["Lipschitz","bilipschitz","extension","separated net."],"publisher":"Finnish Mathematical Society","article_type":"original","acknowledgement":"The present work developed from a research visit of M.D. to V.K. at IST Austria, funded by\r\na London Mathematical Society Research in Pairs grant. This work was done while V.K. was fully funded by the Austria Science Fund (FWF) [M 3100-N].","abstract":[{"text":"We provide a new characterisation of the decades old open problem of extending bilipschitz mappings given on a Euclidean separated net. In particular, this allows for the complete positive solution of the open problem in dimension two. Along the way, we develop a set of tools for bilipschitz extensions of mappings between subsets of Euclidean spaces.","lang":"eng"}],"article_processing_charge":"Yes (in subscription journal)","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"hybrid","title":"Extending bilipschitz mappings between separated nets","citation":{"ista":"Dymond M, Kaluza V. 2026. Extending bilipschitz mappings between separated nets. Annales Fennici Mathematici. 51(1), 237–260.","mla":"Dymond, Michael, and Vojtech Kaluza. “Extending Bilipschitz Mappings between Separated Nets.” <i>Annales Fennici Mathematici</i>, vol. 51, no. 1, Finnish Mathematical Society, 2026, pp. 237–60, doi:<a href=\"https://doi.org/10.54330/afm.181562\">10.54330/afm.181562</a>.","short":"M. Dymond, V. Kaluza, Annales Fennici Mathematici 51 (2026) 237–260.","chicago":"Dymond, Michael, and Vojtech Kaluza. “Extending Bilipschitz Mappings between Separated Nets.” <i>Annales Fennici Mathematici</i>. Finnish Mathematical Society, 2026. <a href=\"https://doi.org/10.54330/afm.181562\">https://doi.org/10.54330/afm.181562</a>.","apa":"Dymond, M., &#38; Kaluza, V. (2026). Extending bilipschitz mappings between separated nets. <i>Annales Fennici Mathematici</i>. Finnish Mathematical Society. <a href=\"https://doi.org/10.54330/afm.181562\">https://doi.org/10.54330/afm.181562</a>","ama":"Dymond M, Kaluza V. Extending bilipschitz mappings between separated nets. <i>Annales Fennici Mathematici</i>. 2026;51(1):237-260. doi:<a href=\"https://doi.org/10.54330/afm.181562\">10.54330/afm.181562</a>","ieee":"M. Dymond and V. Kaluza, “Extending bilipschitz mappings between separated nets,” <i>Annales Fennici Mathematici</i>, vol. 51, no. 1. Finnish Mathematical Society, pp. 237–260, 2026."},"project":[{"_id":"fc35eaa2-9c52-11eb-aca3-88501ab155e9","name":"Spectra and topology of graphs and of simplicial complexes","grant_number":"M03100"}],"volume":51,"file_date_updated":"2026-04-28T12:03:13Z","day":"17","date_updated":"2026-04-28T12:06:00Z","type":"journal_article","publication_identifier":{"eissn":["2737-114X"],"issn":["2737-0690"]},"year":"2026","date_published":"2026-04-17T00:00:00Z","language":[{"iso":"eng"}],"department":[{"_id":"UlWa"}],"has_accepted_license":"1","issue":"1","publication_status":"published","intvolume":"        51","arxiv":1,"external_id":{"arxiv":["2507.22007"]},"author":[{"first_name":"Michael","last_name":"Dymond","full_name":"Dymond, Michael"},{"full_name":"Kaluza, Vojtech","orcid":"0000-0002-2512-8698","last_name":"Kaluza","id":"21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E","first_name":"Vojtech"}],"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_size":342082,"file_id":"21772","checksum":"442023926a3803d5d6ca8db8dbc4af1c","file_name":"2026_AnnalesFenniciMath_Dymond.pdf","creator":"dernst","date_updated":"2026-04-28T12:03:13Z","date_created":"2026-04-28T12:03:13Z","success":1}],"doi":"10.54330/afm.181562","oa_version":"Published Version"},{"volume":209,"citation":{"short":"M. Dvorak, V. Kolmogorov, Mathematical Programming 209 (2025) 279–322.","ista":"Dvorak M, Kolmogorov V. 2025. Generalized minimum 0-extension problem and discrete convexity. Mathematical Programming. 209, 279–322.","mla":"Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” <i>Mathematical Programming</i>, vol. 209, Springer Nature, 2025, pp. 279–322, doi:<a href=\"https://doi.org/10.1007/s10107-024-02064-5\">10.1007/s10107-024-02064-5</a>.","ieee":"M. Dvorak and V. Kolmogorov, “Generalized minimum 0-extension problem and discrete convexity,” <i>Mathematical Programming</i>, vol. 209. Springer Nature, pp. 279–322, 2025.","apa":"Dvorak, M., &#38; Kolmogorov, V. (2025). Generalized minimum 0-extension problem and discrete convexity. <i>Mathematical Programming</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10107-024-02064-5\">https://doi.org/10.1007/s10107-024-02064-5</a>","ama":"Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete convexity. <i>Mathematical Programming</i>. 2025;209:279-322. doi:<a href=\"https://doi.org/10.1007/s10107-024-02064-5\">10.1007/s10107-024-02064-5</a>","chicago":"Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” <i>Mathematical Programming</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s10107-024-02064-5\">https://doi.org/10.1007/s10107-024-02064-5</a>."},"title":"Generalized minimum 0-extension problem and discrete convexity","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"hybrid","article_processing_charge":"Yes (via OA deal)","department":[{"_id":"GradSch"},{"_id":"VlKo"}],"has_accepted_license":"1","date_published":"2025-01-01T00:00:00Z","language":[{"iso":"eng"}],"year":"2025","type":"journal_article","publication_identifier":{"eissn":["1436-4646"],"issn":["0025-5610"]},"date_updated":"2025-05-19T13:52:10Z","day":"01","file_date_updated":"2025-04-16T09:36:08Z","ddc":["004"],"quality_controlled":"1","isi":1,"corr_author":"1","oa":1,"status":"public","publication":"Mathematical Programming","month":"01","article_type":"original","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).","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"}],"publisher":"Springer Nature","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"],"page":"279-322","date_created":"2021-09-27T10:48:23Z","scopus_import":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"_id":"10045","OA_place":"publisher","external_id":{"isi":["001176563300001"],"arxiv":["2109.10203"]},"oa_version":"Published Version","doi":"10.1007/s10107-024-02064-5","file":[{"file_name":"2025_MathProgramming_Dvorak.pdf","creator":"dernst","success":1,"date_updated":"2025-04-16T09:36:08Z","date_created":"2025-04-16T09:36:08Z","checksum":"25d9bd490719b45eca84f4d93a06c69f","access_level":"open_access","relation":"main_file","file_id":"19578","file_size":839510,"content_type":"application/pdf"}],"author":[{"id":"40ED02A8-C8B4-11E9-A9C0-453BE6697425","first_name":"Martin","full_name":"Dvorak, Martin","last_name":"Dvorak","orcid":"0000-0001-5293-214X"},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"}],"intvolume":"       209","publication_status":"published","arxiv":1}]