[{"extern":"1","date_created":"2019-01-08T20:42:39Z","author":[{"first_name":"Eric","full_name":"Andres, Eric","last_name":"Andres"},{"last_name":"Biswas","full_name":"Biswas, Ranita","first_name":"Ranita","orcid":"0000-0002-5372-7890","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Bhowmick, Partha","last_name":"Bhowmick","first_name":"Partha"}],"date_published":"2017-08-22T00:00:00Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","status":"public","fulldoi":"https://doi.org/10.1007/978-3-319-66272-5_31","month":"08","article_processing_charge":"No","place":"Cham","quality_controlled":"1","oa_version":"None","publication_identifier":{"eissn":["1611-3349"],"isbn":["978-3-319-66271-8"],"eisbn":["978-3-319-66272-5"],"issn":["0302-9743"]},"abstract":[{"text":"This papers introduces a definition of digital primitives based on focal points and weighted distances (with positive weights). The proposed definition is applicable to general dimensions and covers in its gamut various regular curves and surfaces like circles, ellipses, digital spheres and hyperspheres, ellipsoids and k-ellipsoids, Cartesian k-ovals, etc. Several interesting properties are presented for this class of digital primitives such as space partitioning, topological separation, and connectivity properties. To demonstrate further the potential of this new way of defining digital primitives, we propose, as extension, another class of digital conics defined by focus-directrix combination.","lang":"eng"}],"citation":{"mla":"Andres, Eric, et al. “Digital Primitives Defined by Weighted Focal Set.” 20th IAPR International Conference, vol. 10502, Springer Nature, 2017, pp. 388–98, doi:10.1007/978-3-319-66272-5_31.","apa":"Andres, E., Biswas, R., & Bhowmick, P. (2017). Digital primitives defined by weighted focal set. In 20th IAPR International Conference (Vol. 10502, pp. 388–398). Cham: Springer Nature. https://doi.org/10.1007/978-3-319-66272-5_31","ama":"Andres E, Biswas R, Bhowmick P. Digital primitives defined by weighted focal set. In: 20th IAPR International Conference. Vol 10502. Cham: Springer Nature; 2017:388-398. doi:10.1007/978-3-319-66272-5_31","short":"E. Andres, R. Biswas, P. Bhowmick, in:, 20th IAPR International Conference, Springer Nature, Cham, 2017, pp. 388–398.","chicago":"Andres, Eric, Ranita Biswas, and Partha Bhowmick. “Digital Primitives Defined by Weighted Focal Set.” In 20th IAPR International Conference, 10502:388–98. Cham: Springer Nature, 2017. https://doi.org/10.1007/978-3-319-66272-5_31.","ieee":"E. Andres, R. Biswas, and P. Bhowmick, “Digital primitives defined by weighted focal set,” in 20th IAPR International Conference, Vienna, Austria, 2017, vol. 10502, pp. 388–398.","ista":"Andres E, Biswas R, Bhowmick P. 2017. Digital primitives defined by weighted focal set. 20th IAPR International Conference. DGCI: International Conference on Discrete Geometry for Computer Imagery, LNCS, vol. 10502, 388–398."},"intvolume":" 10502","date_updated":"2022-01-27T15:38:35Z","doi":"10.1007/978-3-319-66272-5_31","conference":{"start_date":"2017-09-19","end_date":"2017-09-21","name":"DGCI: International Conference on Discrete Geometry for Computer Imagery","location":"Vienna, Austria"},"publication":"20th IAPR International Conference","title":"Digital primitives defined by weighted focal set","year":"2017","_id":"5802","language":[{"iso":"eng"}],"page":"388-398","publisher":"Springer Nature","alternative_title":["LNCS"],"volume":10502,"type":"conference","publication_status":"published","day":"22"},{"status":"public","fulldoi":"https://doi.org/10.1007/978-3-319-59108-7_8","date_published":"2017-05-17T00:00:00Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","author":[{"full_name":"Biswas, Ranita","last_name":"Biswas","first_name":"Ranita","orcid":"0000-0002-5372-7890","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Partha","last_name":"Bhowmick","full_name":"Bhowmick, Partha"}],"date_created":"2019-01-08T20:42:56Z","extern":"1","oa_version":"None","department":[{"_id":"HeEd"}],"quality_controlled":"1","place":"Cham","article_processing_charge":"No","month":"05","doi":"10.1007/978-3-319-59108-7_8","conference":{"start_date":"2017-06-19","end_date":"2017-06-21","name":"IWCIA: International Workshop on Combinatorial Image Analysis","location":"Plovdiv, Bulgaria"},"date_updated":"2022-01-28T07:48:24Z","intvolume":" 10256","citation":{"ama":"Biswas R, Bhowmick P. Construction of persistent Voronoi diagram on 3D digital plane. In: Combinatorial Image Analysis. Vol 10256. Cham: Springer Nature; 2017:93-104. doi:10.1007/978-3-319-59108-7_8","short":"R. Biswas, P. Bhowmick, in:, Combinatorial Image Analysis, Springer Nature, Cham, 2017, pp. 93–104.","chicago":"Biswas, Ranita, and Partha Bhowmick. “Construction of Persistent Voronoi Diagram on 3D Digital Plane.” In Combinatorial Image Analysis, 10256:93–104. Cham: Springer Nature, 2017. https://doi.org/10.1007/978-3-319-59108-7_8.","ista":"Biswas R, Bhowmick P. 2017.Construction of persistent Voronoi diagram on 3D digital plane. In: Combinatorial image analysis. LNCS, vol. 10256, 93–104.","ieee":"R. Biswas and P. Bhowmick, “Construction of persistent Voronoi diagram on 3D digital plane,” in Combinatorial image analysis, vol. 10256, Cham: Springer Nature, 2017, pp. 93–104.","mla":"Biswas, Ranita, and Partha Bhowmick. “Construction of Persistent Voronoi Diagram on 3D Digital Plane.” Combinatorial Image Analysis, vol. 10256, Springer Nature, 2017, pp. 93–104, doi:10.1007/978-3-319-59108-7_8.","apa":"Biswas, R., & Bhowmick, P. (2017). Construction of persistent Voronoi diagram on 3D digital plane. In Combinatorial image analysis (Vol. 10256, pp. 93–104). Cham: Springer Nature. https://doi.org/10.1007/978-3-319-59108-7_8"},"abstract":[{"text":"Different distance metrics produce Voronoi diagrams with different properties. It is a well-known that on the (real) 2D plane or even on any 3D plane, a Voronoi diagram (VD) based on the Euclidean distance metric produces convex Voronoi regions. In this paper, we first show that this metric produces a persistent VD on the 2D digital plane, as it comprises digitally convex Voronoi regions and hence correctly approximates the corresponding VD on the 2D real plane. Next, we show that on a 3D digital plane D, the Euclidean metric spanning over its voxel set does not guarantee a digital VD which is persistent with the real-space VD. As a solution, we introduce a novel concept of functional-plane-convexity, which is ensured by the Euclidean metric spanning over the pedal set of D. Necessary proofs and some visual result have been provided to adjudge the merit and usefulness of the proposed concept.","lang":"eng"}],"publication_identifier":{"issn":["0302-9743","1611-3349"],"isbn":["978-3-319-59107-0","978-3-319-59108-7"]},"day":"17","publication_status":"published","type":"book_chapter","volume":10256,"alternative_title":["LNCS"],"publisher":"Springer Nature","language":[{"iso":"eng"}],"page":"93-104","_id":"5803","year":"2017","title":"Construction of persistent Voronoi diagram on 3D digital plane","publication":"Combinatorial image analysis"},{"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"oa_version":"Submitted Version","quality_controlled":"1","article_processing_charge":"No","has_accepted_license":"1","month":"07","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2017-07-25T00:00:00Z","status":"public","fulldoi":"https://doi.org/10.1007/978-3-319-63121-9_18","series_title":"Theoretical Computer Science and General Issues","acknowledgement":"This research was supported in part by the Austrian Science Fund (FWF) under grants S11402-N23 and S11407-N23 (RiSE/SHiNE), and Z211-N23 (Wittgenstein Award), ERC Start grant (279307: Graph Games), Vienna Science and Technology Fund (WWTF) through project ICT15-003.","scopus_import":"1","project":[{"name":"Moderne Concurrency Paradigms","call_identifier":"FWF","grant_number":"S11402-N23","_id":"25F5A88A-B435-11E9-9278-68D0E5697425"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"}],"author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"},{"last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"date_created":"2018-12-11T11:47:34Z","editor":[{"last_name":"Aceto","full_name":"Aceto, Luca","first_name":"Luca"},{"last_name":"Bacci","full_name":"Bacci, Giorgio","first_name":"Giorgio"},{"first_name":"Anna","last_name":"Ingólfsdóttir","full_name":"Ingólfsdóttir, Anna"},{"first_name":"Axel","last_name":"Legay","full_name":"Legay, Axel"},{"last_name":"Mardare","full_name":"Mardare, Radu","first_name":"Radu"}],"file":[{"file_id":"7048","file_name":"2017_ModelsAlgorithms_Chatterjee.pdf","relation":"main_file","checksum":"b2402766ec02c79801aac634bd8f9f6c","date_created":"2019-11-19T08:06:50Z","access_level":"open_access","file_size":192826,"date_updated":"2020-07-14T12:47:25Z","content_type":"application/pdf","creator":"dernst"}],"oa":1,"publication_status":"published","day":"25","type":"book_chapter","ddc":["000"],"publisher":"Springer","alternative_title":["LNCS"],"ec_funded":1,"volume":10460,"title":"The cost of exactness in quantitative reachability","publication":"Models, Algorithms, Logics and Tools","page":"367 - 381","language":[{"iso":"eng"}],"_id":"625","file_date_updated":"2020-07-14T12:47:25Z","year":"2017","date_updated":"2025-04-15T06:26:15Z","doi":"10.1007/978-3-319-63121-9_18","intvolume":" 10460","citation":{"ieee":"K. Chatterjee, L. Doyen, and T. A. Henzinger, “The cost of exactness in quantitative reachability,” in Models, Algorithms, Logics and Tools, vol. 10460, L. Aceto, G. Bacci, A. Ingólfsdóttir, A. Legay, and R. Mardare, Eds. Springer, 2017, pp. 367–381.","ista":"Chatterjee K, Doyen L, Henzinger TA. 2017.The cost of exactness in quantitative reachability. In: Models, Algorithms, Logics and Tools. LNCS, vol. 10460, 367–381.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “The Cost of Exactness in Quantitative Reachability.” In Models, Algorithms, Logics and Tools, edited by Luca Aceto, Giorgio Bacci, Anna Ingólfsdóttir, Axel Legay, and Radu Mardare, 10460:367–81. Theoretical Computer Science and General Issues. Springer, 2017. https://doi.org/10.1007/978-3-319-63121-9_18.","ama":"Chatterjee K, Doyen L, Henzinger TA. The cost of exactness in quantitative reachability. In: Aceto L, Bacci G, Ingólfsdóttir A, Legay A, Mardare R, eds. Models, Algorithms, Logics and Tools. Vol 10460. Theoretical Computer Science and General Issues. Springer; 2017:367-381. doi:10.1007/978-3-319-63121-9_18","short":"K. Chatterjee, L. Doyen, T.A. Henzinger, in:, L. Aceto, G. Bacci, A. Ingólfsdóttir, A. Legay, R. Mardare (Eds.), Models, Algorithms, Logics and Tools, Springer, 2017, pp. 367–381.","apa":"Chatterjee, K., Doyen, L., & Henzinger, T. A. (2017). The cost of exactness in quantitative reachability. In L. Aceto, G. Bacci, A. Ingólfsdóttir, A. Legay, & R. Mardare (Eds.), Models, Algorithms, Logics and Tools (Vol. 10460, pp. 367–381). Springer. https://doi.org/10.1007/978-3-319-63121-9_18","mla":"Chatterjee, Krishnendu, et al. “The Cost of Exactness in Quantitative Reachability.” Models, Algorithms, Logics and Tools, edited by Luca Aceto et al., vol. 10460, Springer, 2017, pp. 367–81, doi:10.1007/978-3-319-63121-9_18."},"publist_id":"7170","abstract":[{"lang":"eng","text":"In the analysis of reactive systems a quantitative objective assigns a real value to every trace of the system. The value decision problem for a quantitative objective requires a trace whose value is at least a given threshold, and the exact value decision problem requires a trace whose value is exactly the threshold. We compare the computational complexity of the value and exact value decision problems for classical quantitative objectives, such as sum, discounted sum, energy, and mean-payoff for two standard models of reactive systems, namely, graphs and graph games."}],"publication_identifier":{"issn":["0302-9743"],"isbn":["978-3-319-63120-2"]}},{"department":[{"_id":"ToHe"}],"oa_version":"None","day":"01","quality_controlled":"1","publication_status":"published","article_processing_charge":"No","type":"conference_editor","volume":10152,"publisher":"Springer","alternative_title":["LNCS"],"language":[{"iso":"eng"}],"year":"2017","_id":"638","title":"Numerical Software Verification","month":"01","status":"public","fulldoi":"https://doi.org/10.1007/978-3-319-54292-8","conference":{"name":"NSV: Numerical Software Verification","location":"Toronto, ON, Canada","start_date":"2016-07-17","end_date":"2016-07-18"},"doi":"10.1007/978-3-319-54292-8","date_updated":"2026-03-31T12:28:01Z","date_published":"2017-01-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 10152","citation":{"apa":"Bogomolov, S., Martel, M., & Prabhakar, P. (Eds.). (2017). Numerical Software Verification (Vol. 10152). Presented at the NSV: Numerical Software Verification, Toronto, ON, Canada: Springer. https://doi.org/10.1007/978-3-319-54292-8","mla":"Bogomolov, Sergiy, et al., editors. Numerical Software Verification. Vol. 10152, Springer, 2017, doi:10.1007/978-3-319-54292-8.","ieee":"S. Bogomolov, M. Martel, and P. Prabhakar, Eds., Numerical Software Verification, vol. 10152. Springer, 2017.","ista":"Bogomolov S, Martel M, Prabhakar P eds. 2017. Numerical Software Verification, Springer,p.","chicago":"Bogomolov, Sergiy, Matthieu Martel, and Pavithra Prabhakar, eds. Numerical Software Verification. Vol. 10152. Springer, 2017. https://doi.org/10.1007/978-3-319-54292-8.","ama":"Bogomolov S, Martel M, Prabhakar P, eds. Numerical Software Verification. Vol 10152. Springer; 2017. doi:10.1007/978-3-319-54292-8","short":"S. Bogomolov, M. Martel, P. Prabhakar, eds., Numerical Software Verification, Springer, 2017."},"abstract":[{"lang":"eng","text":"This book constitutes the refereed proceedings of the 9th InternationalWorkshop on Numerical Software Verification, NSV 2016, held in Toronto, ON, Canada in July 2011 - colocated with CAV 2016, the 28th International Conference on Computer Aided Verification.\r\nThe NSV workshop is dedicated to the development of logical and mathematical techniques for the reasoning about programmability and reliability."}],"publist_id":"7150","publication_identifier":{"issn":["0302-9743"],"eisbn":["978-3-319-54292-8"]},"date_created":"2018-12-11T11:47:38Z","editor":[{"last_name":"Bogomolov","full_name":"Bogomolov, Sergiy","first_name":"Sergiy","orcid":"0000-0002-0686-0365","id":"369D9A44-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Martel, Matthieu","last_name":"Martel","first_name":"Matthieu"},{"full_name":"Prabhakar, Pavithra","last_name":"Prabhakar","first_name":"Pavithra"}]},{"editor":[{"last_name":"Yang","full_name":"Yang, Hongseok","first_name":"Hongseok"}],"date_created":"2018-12-11T11:49:41Z","oa":1,"date_published":"2017-03-19T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.1007/978-3-662-54434-1_11","status":"public","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"id":"320FC952-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-7745-9117","first_name":"Bernhard","last_name":"Kragl","full_name":"Kragl, Bernhard"},{"full_name":"Mishra, Samarth","last_name":"Mishra","first_name":"Samarth"},{"orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas","first_name":"Andreas"}],"scopus_import":"1","project":[{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23","call_identifier":"FWF","name":"Moderne Concurrency Paradigms"},{"call_identifier":"FWF","name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"Formal methods for the design and analysis of complex systems","call_identifier":"FWF"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"}],"main_file_link":[{"url":"https://arxiv.org/abs/1701.04914","open_access":"1"}],"month":"03","quality_controlled":"1","arxiv":1,"oa_version":"Submitted Version","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"isi":1,"article_processing_charge":"No","publist_id":"6384","abstract":[{"lang":"eng","text":"Pushdown systems (PDSs) and recursive state machines (RSMs), which are linearly equivalent, are standard models for interprocedural analysis. Yet RSMs are more convenient as they (a) explicitly model function calls and returns, and (b) specify many natural parameters for algorithmic analysis, e.g., the number of entries and exits. We consider a general framework where RSM transitions are labeled from a semiring and path properties are algebraic with semiring operations, which can model, e.g., interprocedural reachability and dataflow analysis problems. Our main contributions are new algorithms for several fundamental problems. As compared to a direct translation of RSMs to PDSs and the best-known existing bounds of PDSs, our analysis algorithm improves the complexity for finite-height semirings (that subsumes reachability and standard dataflow properties). We further consider the problem of extracting distance values from the representation structures computed by our algorithm, and give efficient algorithms that distinguish the complexity of a one-time preprocessing from the complexity of each individual query. Another advantage of our algorithm is that our improvements carry over to the concurrent setting, where we improve the bestknown complexity for the context-bounded analysis of concurrent RSMs. Finally, we provide a prototype implementation that gives a significant speed-up on several benchmarks from the SLAM/SDV project."}],"publication_identifier":{"issn":["0302-9743"]},"date_updated":"2025-06-04T08:09:18Z","conference":{"end_date":"2017-04-29","start_date":"2017-04-22","location":"Uppsala, Sweden","name":"ESOP: European Symposium on Programming"},"doi":"10.1007/978-3-662-54434-1_11","citation":{"mla":"Chatterjee, Krishnendu, et al. Faster Algorithms for Weighted Recursive State Machines. Edited by Hongseok Yang, vol. 10201, Springer, 2017, pp. 287–313, doi:10.1007/978-3-662-54434-1_11.","apa":"Chatterjee, K., Kragl, B., Mishra, S., & Pavlogiannis, A. (2017). Faster algorithms for weighted recursive state machines. In H. Yang (Ed.) (Vol. 10201, pp. 287–313). Presented at the ESOP: European Symposium on Programming, Uppsala, Sweden: Springer. https://doi.org/10.1007/978-3-662-54434-1_11","ama":"Chatterjee K, Kragl B, Mishra S, Pavlogiannis A. Faster algorithms for weighted recursive state machines. In: Yang H, ed. Vol 10201. Springer; 2017:287-313. doi:10.1007/978-3-662-54434-1_11","short":"K. Chatterjee, B. Kragl, S. Mishra, A. Pavlogiannis, in:, H. Yang (Ed.), Springer, 2017, pp. 287–313.","ieee":"K. Chatterjee, B. Kragl, S. Mishra, and A. Pavlogiannis, “Faster algorithms for weighted recursive state machines,” presented at the ESOP: European Symposium on Programming, Uppsala, Sweden, 2017, vol. 10201, pp. 287–313.","ista":"Chatterjee K, Kragl B, Mishra S, Pavlogiannis A. 2017. Faster algorithms for weighted recursive state machines. ESOP: European Symposium on Programming, LNCS, vol. 10201, 287–313.","chicago":"Chatterjee, Krishnendu, Bernhard Kragl, Samarth Mishra, and Andreas Pavlogiannis. “Faster Algorithms for Weighted Recursive State Machines.” edited by Hongseok Yang, 10201:287–313. Springer, 2017. https://doi.org/10.1007/978-3-662-54434-1_11."},"intvolume":" 10201","publisher":"Springer","alternative_title":["LNCS"],"external_id":{"arxiv":["1701.04914"],"isi":["000681702400011"]},"ec_funded":1,"volume":10201,"title":"Faster algorithms for weighted recursive state machines","year":"2017","_id":"1011","page":"287 - 313","language":[{"iso":"eng"}],"publication_status":"published","day":"19","type":"conference"},{"fulldoi":"https://doi.org/10.1007/978-3-319-64689-3_32","status":"public","date_published":"2017-07-28T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","author":[{"full_name":"Heiss, Teresa","last_name":"Heiss","first_name":"Teresa","orcid":"0000-0002-1780-2689","id":"4879BB4E-F248-11E8-B48F-1D18A9856A87"},{"id":"379CA8B8-F248-11E8-B48F-1D18A9856A87","first_name":"Hubert","last_name":"Wagner","full_name":"Wagner, Hubert"}],"oa":1,"date_created":"2018-12-11T11:48:45Z","editor":[{"first_name":"Michael","last_name":"Felsberg","full_name":"Felsberg, Michael"},{"first_name":"Anders","full_name":"Heyden, Anders","last_name":"Heyden"},{"last_name":"Krüger","full_name":"Krüger, Norbert","first_name":"Norbert"}],"department":[{"_id":"HeEd"}],"oa_version":"Submitted Version","arxiv":1,"quality_controlled":"1","article_processing_charge":"No","isi":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1705.02045"}],"month":"07","conference":{"start_date":"2017-08-22","end_date":"2017-08-24","name":"CAIP: Computer Analysis of Images and Patterns","location":"Ystad, Sweden"},"doi":"10.1007/978-3-319-64689-3_32","date_updated":"2025-06-04T09:54:22Z","intvolume":" 10424","citation":{"ama":"Heiss T, Wagner H. Streaming algorithm for Euler characteristic curves of multidimensional images. In: Felsberg M, Heyden A, Krüger N, eds. Vol 10424. Springer; 2017:397-409. doi:10.1007/978-3-319-64689-3_32","short":"T. Heiss, H. Wagner, in:, M. Felsberg, A. Heyden, N. Krüger (Eds.), Springer, 2017, pp. 397–409.","ista":"Heiss T, Wagner H. 2017. Streaming algorithm for Euler characteristic curves of multidimensional images. CAIP: Computer Analysis of Images and Patterns, LNCS, vol. 10424, 397–409.","chicago":"Heiss, Teresa, and Hubert Wagner. “Streaming Algorithm for Euler Characteristic Curves of Multidimensional Images.” edited by Michael Felsberg, Anders Heyden, and Norbert Krüger, 10424:397–409. Springer, 2017. https://doi.org/10.1007/978-3-319-64689-3_32.","ieee":"T. Heiss and H. Wagner, “Streaming algorithm for Euler characteristic curves of multidimensional images,” presented at the CAIP: Computer Analysis of Images and Patterns, Ystad, Sweden, 2017, vol. 10424, pp. 397–409.","mla":"Heiss, Teresa, and Hubert Wagner. Streaming Algorithm for Euler Characteristic Curves of Multidimensional Images. Edited by Michael Felsberg et al., vol. 10424, Springer, 2017, pp. 397–409, doi:10.1007/978-3-319-64689-3_32.","apa":"Heiss, T., & Wagner, H. (2017). Streaming algorithm for Euler characteristic curves of multidimensional images. In M. Felsberg, A. Heyden, & N. Krüger (Eds.) (Vol. 10424, pp. 397–409). Presented at the CAIP: Computer Analysis of Images and Patterns, Ystad, Sweden: Springer. https://doi.org/10.1007/978-3-319-64689-3_32"},"abstract":[{"text":"We present an efficient algorithm to compute Euler characteristic curves of gray scale images of arbitrary dimension. In various applications the Euler characteristic curve is used as a descriptor of an image. Our algorithm is the first streaming algorithm for Euler characteristic curves. The usage of streaming removes the necessity to store the entire image in RAM. Experiments show that our implementation handles terabyte scale images on commodity hardware. Due to lock-free parallelism, it scales well with the number of processor cores. Additionally, we put the concept of the Euler characteristic curve in the wider context of computational topology. In particular, we explain the connection with persistence diagrams.","lang":"eng"}],"publist_id":"6815","publication_identifier":{"issn":["0302-9743"]},"day":"28","publication_status":"published","type":"conference","volume":10424,"external_id":{"arxiv":["1705.02045"],"isi":["000432085900032"]},"publisher":"Springer","alternative_title":["LNCS"],"language":[{"iso":"eng"}],"page":"397 - 409","year":"2017","_id":"833","corr_author":"1","title":"Streaming algorithm for Euler characteristic curves of multidimensional images"},{"abstract":[{"text":"We present a new algorithm for model counting of a class of string constraints. In addition to the classic operation of concatenation, our class includes some recursively defined operations such as Kleene closure, and replacement of substrings. Additionally, our class also includes length constraints on the string expressions, which means, by requiring reasoning about numbers, that we face a multi-sorted logic. In the end, our string constraints are motivated by their use in programming for web applications. Our algorithm comprises two novel features: the ability to use a technique of (1) partial derivatives for constraints that are already in a solved form, i.e. a form where its (string) satisfiability is clearly displayed, and (2) non-progression, where cyclic reasoning in the reduction process may be terminated (thus allowing for the algorithm to look elsewhere). Finally, we experimentally compare our model counter with two recent works on model counting of similar constraints, SMC [18] and ABC [5], to demonstrate its superior performance.","lang":"eng"}],"publist_id":"6443","publication_identifier":{"issn":["0302-9743"]},"conference":{"end_date":"2017-07-28","start_date":"2017-07-24","location":"Heidelberg, Germany","name":"CAV: Computer Aided Verification"},"doi":"10.1007/978-3-319-63390-9_21","date_updated":"2026-04-16T09:58:05Z","citation":{"ieee":"M. Trinh, D. H. Chu, and J. Jaffar, “Model counting for recursively-defined strings,” presented at the CAV: Computer Aided Verification, Heidelberg, Germany, 2017, vol. 10427, pp. 399–418.","chicago":"Trinh, Minh, Duc Hiep Chu, and Joxan Jaffar. “Model Counting for Recursively-Defined Strings.” edited by Rupak Majumdar and Viktor Kunčak, 10427:399–418. Springer, 2017. https://doi.org/10.1007/978-3-319-63390-9_21.","ista":"Trinh M, Chu DH, Jaffar J. 2017. Model counting for recursively-defined strings. CAV: Computer Aided Verification, LNCS, vol. 10427, 399–418.","ama":"Trinh M, Chu DH, Jaffar J. Model counting for recursively-defined strings. In: Majumdar R, Kunčak V, eds. Vol 10427. Springer; 2017:399-418. doi:10.1007/978-3-319-63390-9_21","short":"M. Trinh, D.H. Chu, J. Jaffar, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 399–418.","apa":"Trinh, M., Chu, D. H., & Jaffar, J. (2017). Model counting for recursively-defined strings. In R. Majumdar & V. Kunčak (Eds.) (Vol. 10427, pp. 399–418). Presented at the CAV: Computer Aided Verification, Heidelberg, Germany: Springer. https://doi.org/10.1007/978-3-319-63390-9_21","mla":"Trinh, Minh, et al. Model Counting for Recursively-Defined Strings. Edited by Rupak Majumdar and Viktor Kunčak, vol. 10427, Springer, 2017, pp. 399–418, doi:10.1007/978-3-319-63390-9_21."},"intvolume":" 10427","external_id":{"isi":["000431900900021"]},"volume":10427,"publisher":"Springer","alternative_title":["LNCS"],"_id":"962","year":"2017","language":[{"iso":"eng"}],"page":"399 - 418","title":"Model counting for recursively-defined strings","day":"01","publication_status":"published","type":"conference","editor":[{"first_name":"Rupak","full_name":"Majumdar, Rupak","last_name":"Majumdar"},{"last_name":"Kunčak","full_name":"Kunčak, Viktor","first_name":"Viktor"}],"date_created":"2018-12-11T11:49:26Z","fulldoi":"https://doi.org/10.1007/978-3-319-63390-9_21","status":"public","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","date_published":"2017-01-01T00:00:00Z","author":[{"first_name":"Minh","full_name":"Trinh, Minh","last_name":"Trinh"},{"id":"3598E630-F248-11E8-B48F-1D18A9856A87","last_name":"Chu","full_name":"Chu, Duc Hiep","first_name":"Duc Hiep"},{"last_name":"Jaffar","full_name":"Jaffar, Joxan","first_name":"Joxan"}],"scopus_import":"1","project":[{"call_identifier":"FWF","name":"Moderne Concurrency Paradigms","_id":"25F5A88A-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23"},{"name":"Formal methods for the design and analysis of complex systems","call_identifier":"FWF","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425"}],"month":"01","quality_controlled":"1","department":[{"_id":"ToHe"}],"oa_version":"None","article_processing_charge":"No","isi":1},{"intvolume":" 10185","citation":{"ista":"Skórski M. 2017. A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. TAMC: Theory and Applications of Models of Computation, LNCS, vol. 10185, 586–599.","chicago":"Skórski, Maciej. “A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds.” edited by Gerhard Jäger and Silvia Steila, 10185:586–99. Springer, 2017. https://doi.org/10.1007/978-3-319-55911-7_42.","ieee":"M. Skórski, “A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds,” presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland, 2017, vol. 10185, pp. 586–599.","short":"M. Skórski, in:, G. Jäger, S. Steila (Eds.), Springer, 2017, pp. 586–599.","ama":"Skórski M. A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. In: Jäger G, Steila S, eds. Vol 10185. Springer; 2017:586-599. doi:10.1007/978-3-319-55911-7_42","apa":"Skórski, M. (2017). A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. In G. Jäger & S. Steila (Eds.) (Vol. 10185, pp. 586–599). Presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland: Springer. https://doi.org/10.1007/978-3-319-55911-7_42","mla":"Skórski, Maciej. A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds. Edited by Gerhard Jäger and Silvia Steila, vol. 10185, Springer, 2017, pp. 586–99, doi:10.1007/978-3-319-55911-7_42."},"date_updated":"2026-04-16T09:59:38Z","doi":"10.1007/978-3-319-55911-7_42","conference":{"start_date":"2017-04-20","end_date":"2017-04-22","name":"TAMC: Theory and Applications of Models of Computation","location":"Bern, Switzerland"},"publication_identifier":{"issn":["0302-9743"]},"publist_id":"7119","abstract":[{"lang":"eng","text":"In this work we present a short and unified proof for the Strong and Weak Regularity Lemma, based on the cryptographic tech-nique called low-complexity approximations. In short, both problems reduce to a task of finding constructively an approximation for a certain target function under a class of distinguishers (test functions), where dis-tinguishers are combinations of simple rectangle-indicators. In our case these approximations can be learned by a simple iterative procedure, which yields a unified and simple proof, achieving for any graph with density d and any approximation parameter the partition size. The novelty in our proof is: (a) a simple approach which yields both strong and weaker variant, and (b) improvements when d = o(1). At an abstract level, our proof can be seen a refinement and simplification of the “analytic” proof given by Lovasz and Szegedy."}],"type":"conference","publication_status":"published","day":"01","corr_author":"1","title":"A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds","language":[{"iso":"eng"}],"page":"586 - 599","year":"2017","_id":"650","alternative_title":["LNCS"],"publisher":"Springer","volume":10185,"external_id":{"isi":["000425175500042"]},"scopus_import":"1","author":[{"id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","full_name":"Skórski, Maciej","last_name":"Skórski","first_name":"Maciej"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","date_published":"2017-01-01T00:00:00Z","status":"public","fulldoi":"https://doi.org/10.1007/978-3-319-55911-7_42","date_created":"2018-12-11T11:47:42Z","editor":[{"first_name":"Gerhard","last_name":"Jäger","full_name":"Jäger, Gerhard"},{"first_name":"Silvia","last_name":"Steila","full_name":"Steila, Silvia"}],"oa":1,"isi":1,"article_processing_charge":"No","department":[{"_id":"KrPi"}],"oa_version":"Submitted Version","quality_controlled":"1","month":"01","main_file_link":[{"url":"https://eprint.iacr.org/2016/965.pdf","open_access":"1"}]},{"author":[{"id":"4C5696CE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0845-1338","first_name":"Jan","full_name":"Maas, Jan","last_name":"Maas"},{"first_name":"Martin","last_name":"Rumpf","full_name":"Rumpf, Martin"},{"last_name":"Simon","full_name":"Simon, Stefan","first_name":"Stefan"}],"scopus_import":"1","date_published":"2017-05-18T00:00:00Z","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","status":"public","fulldoi":"https://doi.org/10.1007/978-3-319-58771-4_45","editor":[{"first_name":"François","last_name":"Lauze","full_name":"Lauze, François"},{"last_name":"Dong","full_name":"Dong, Yiqiu","first_name":"Yiqiu"},{"last_name":"Bjorholm Dahl","full_name":"Bjorholm Dahl, Anders","first_name":"Anders"}],"date_created":"2018-12-11T11:49:34Z","isi":1,"article_processing_charge":"No","quality_controlled":"1","oa_version":"None","department":[{"_id":"JaMa"}],"month":"05","citation":{"chicago":"Maas, Jan, Martin Rumpf, and Stefan Simon. “Transport Based Image Morphing with Intensity Modulation.” edited by François Lauze, Yiqiu Dong, and Anders Bjorholm Dahl, 10302:563–77. Springer, 2017. https://doi.org/10.1007/978-3-319-58771-4_45.","ista":"Maas J, Rumpf M, Simon S. 2017. Transport based image morphing with intensity modulation. SSVM: Scale Space and Variational Methods in Computer Vision, LNCS, vol. 10302, 563–577.","ieee":"J. Maas, M. Rumpf, and S. Simon, “Transport based image morphing with intensity modulation,” presented at the SSVM: Scale Space and Variational Methods in Computer Vision, Kolding, Denmark, 2017, vol. 10302, pp. 563–577.","ama":"Maas J, Rumpf M, Simon S. Transport based image morphing with intensity modulation. In: Lauze F, Dong Y, Bjorholm Dahl A, eds. Vol 10302. Springer; 2017:563-577. doi:10.1007/978-3-319-58771-4_45","short":"J. Maas, M. Rumpf, S. Simon, in:, F. Lauze, Y. Dong, A. Bjorholm Dahl (Eds.), Springer, 2017, pp. 563–577.","apa":"Maas, J., Rumpf, M., & Simon, S. (2017). Transport based image morphing with intensity modulation. In F. Lauze, Y. Dong, & A. Bjorholm Dahl (Eds.) (Vol. 10302, pp. 563–577). Presented at the SSVM: Scale Space and Variational Methods in Computer Vision, Kolding, Denmark: Springer. https://doi.org/10.1007/978-3-319-58771-4_45","mla":"Maas, Jan, et al. Transport Based Image Morphing with Intensity Modulation. Edited by François Lauze et al., vol. 10302, Springer, 2017, pp. 563–77, doi:10.1007/978-3-319-58771-4_45."},"intvolume":" 10302","date_updated":"2026-04-16T10:05:10Z","doi":"10.1007/978-3-319-58771-4_45","conference":{"start_date":"2017-06-04","end_date":"2017-06-08","name":"SSVM: Scale Space and Variational Methods in Computer Vision","location":"Kolding, Denmark"},"publication_identifier":{"issn":["0302-9743"]},"publist_id":"6410","abstract":[{"text":"We present a generalized optimal transport model in which the mass-preserving constraint for the L2-Wasserstein distance is relaxed by introducing a source term in the continuity equation. The source term is also incorporated in the path energy by means of its squared L2-norm in time of a functional with linear growth in space. This extension of the original transport model enables local density modulations, which is a desirable feature in applications such as image warping and blending. A key advantage of the use of a functional with linear growth in space is that it allows for singular sources and sinks, which can be supported on points or lines. On a technical level, the L2-norm in time ensures a disintegration of the source in time, which we use to obtain the well-posedness of the model and the existence of geodesic paths. The numerical discretization is based on the proximal splitting approach [18] and selected numerical test cases show the potential of the proposed approach. Furthermore, the approach is applied to the warping and blending of textures.","lang":"eng"}],"type":"conference","publication_status":"published","day":"18","title":"Transport based image morphing with intensity modulation","year":"2017","_id":"989","language":[{"iso":"eng"}],"page":"563 - 577","alternative_title":["LNCS"],"publisher":"Springer","external_id":{"isi":["000432210900045"]},"volume":10302},{"month":"05","quality_controlled":"1","oa_version":"None","article_processing_charge":"No","extern":"1","date_created":"2024-10-15T11:20:54Z","date_published":"2017-05-18T00:00:00Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","fulldoi":"https://doi.org/10.1007/978-3-319-58771-4_54","author":[{"last_name":"Boyarski","full_name":"Boyarski, Amit","first_name":"Amit"},{"first_name":"Alexander","last_name":"Bronstein","full_name":"Bronstein, Alexander","id":"58f3726e-7cba-11ef-ad8b-e6e8cb3904e6","orcid":"0000-0001-9699-8730"},{"last_name":"Bronstein","full_name":"Bronstein, Michael M.","first_name":"Michael M."}],"scopus_import":"1","publisher":"Springer Nature","alternative_title":["LNCS"],"volume":10302,"publication":"International Conference on Scale Space and Variational Methods in Computer Vision","title":"Subspace least squares multidimensional scaling","_id":"18329","year":"2017","page":"681-693","language":[{"iso":"eng"}],"publication_status":"published","day":"18","type":"conference","abstract":[{"text":"Multidimensional Scaling (MDS) is one of the most popular methods for dimensionality reduction and visualization of high dimensional data. Apart from these tasks, it also found applications in the field of geometry processing for the analysis and reconstruction of non-rigid shapes. In this regard, MDS can be thought of as a shape from metric algorithm, consisting of finding a configuration of points in the Euclidean space that realize, as isometrically as possible, some given distance structure. In the present work we cast the least squares variant of MDS (LS-MDS) in the spectral domain. This uncovers a multiresolution property of distance scaling which speeds up the optimization by a significant amount, while producing comparable, and sometimes even better, embeddings.","lang":"eng"}],"publication_identifier":{"eisbn":["9783319587714"],"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783319587707"]},"date_updated":"2025-01-23T08:42:25Z","conference":{"name":"SSVM: Scale Space and Variational Methods in Computer Vision","location":"Kolding, Denmark","start_date":"2017-06-04","end_date":"2017-06-08"},"doi":"10.1007/978-3-319-58771-4_54","citation":{"short":"A. Boyarski, A.M. Bronstein, M.M. Bronstein, in:, International Conference on Scale Space and Variational Methods in Computer Vision, Springer Nature, 2017, pp. 681–693.","ama":"Boyarski A, Bronstein AM, Bronstein MM. Subspace least squares multidimensional scaling. In: International Conference on Scale Space and Variational Methods in Computer Vision. Vol 10302. Springer Nature; 2017:681-693. doi:10.1007/978-3-319-58771-4_54","ieee":"A. Boyarski, A. M. Bronstein, and M. M. Bronstein, “Subspace least squares multidimensional scaling,” in International Conference on Scale Space and Variational Methods in Computer Vision, Kolding, Denmark, 2017, vol. 10302, pp. 681–693.","chicago":"Boyarski, Amit, Alex M. Bronstein, and Michael M. Bronstein. “Subspace Least Squares Multidimensional Scaling.” In International Conference on Scale Space and Variational Methods in Computer Vision, 10302:681–93. Springer Nature, 2017. https://doi.org/10.1007/978-3-319-58771-4_54.","ista":"Boyarski A, Bronstein AM, Bronstein MM. 2017. Subspace least squares multidimensional scaling. International Conference on Scale Space and Variational Methods in Computer Vision. SSVM: Scale Space and Variational Methods in Computer Vision, LNCS, vol. 10302, 681–693.","mla":"Boyarski, Amit, et al. “Subspace Least Squares Multidimensional Scaling.” International Conference on Scale Space and Variational Methods in Computer Vision, vol. 10302, Springer Nature, 2017, pp. 681–93, doi:10.1007/978-3-319-58771-4_54.","apa":"Boyarski, A., Bronstein, A. M., & Bronstein, M. M. (2017). Subspace least squares multidimensional scaling. In International Conference on Scale Space and Variational Methods in Computer Vision (Vol. 10302, pp. 681–693). Kolding, Denmark: Springer Nature. https://doi.org/10.1007/978-3-319-58771-4_54"},"intvolume":" 10302"},{"quality_controlled":"1","oa_version":"None","article_processing_charge":"No","month":"09","fulldoi":"https://doi.org/10.1007/978-3-319-66182-7_65","status":"public","date_published":"2017-09-04T00:00:00Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Guy","full_name":"Alexandroni, Guy","last_name":"Alexandroni"},{"last_name":"Podolsky","full_name":"Podolsky, Yana","first_name":"Yana"},{"full_name":"Greenspan, Hayit","last_name":"Greenspan","first_name":"Hayit"},{"first_name":"Tal","full_name":"Remez, Tal","last_name":"Remez"},{"first_name":"Or","full_name":"Litany, Or","last_name":"Litany"},{"first_name":"Alexander","last_name":"Bronstein","full_name":"Bronstein, Alexander","id":"58f3726e-7cba-11ef-ad8b-e6e8cb3904e6","orcid":"0000-0001-9699-8730"},{"last_name":"Giryes","full_name":"Giryes, Raja","first_name":"Raja"}],"scopus_import":"1","extern":"1","date_created":"2024-10-15T11:20:54Z","day":"04","publication_status":"published","type":"conference","volume":10433,"publisher":"Springer Nature","alternative_title":["LNCS"],"_id":"18330","year":"2017","page":"566 - 574","language":[{"iso":"eng"}],"publication":"20th International Conference on Medical Image Computing and Computer-Assisted Intervention","title":"White matter fiber representation using continuous dictionary learning","conference":{"location":"Quebec City, QC, Canada","name":"MICCAI: Medical Image Computing and Computer-Assisted Intervention","end_date":"2017-09-13","start_date":"2017-09-11"},"doi":"10.1007/978-3-319-66182-7_65","date_updated":"2025-01-16T16:04:30Z","issue":"Part 1","citation":{"mla":"Alexandroni, Guy, et al. “White Matter Fiber Representation Using Continuous Dictionary Learning.” 20th International Conference on Medical Image Computing and Computer-Assisted Intervention, vol. 10433, no. Part 1, Springer Nature, 2017, pp. 566–74, doi:10.1007/978-3-319-66182-7_65.","apa":"Alexandroni, G., Podolsky, Y., Greenspan, H., Remez, T., Litany, O., Bronstein, A. M., & Giryes, R. (2017). White matter fiber representation using continuous dictionary learning. In 20th International Conference on Medical Image Computing and Computer-Assisted Intervention (Vol. 10433, pp. 566–574). Quebec City, QC, Canada: Springer Nature. https://doi.org/10.1007/978-3-319-66182-7_65","short":"G. Alexandroni, Y. Podolsky, H. Greenspan, T. Remez, O. Litany, A.M. Bronstein, R. Giryes, in:, 20th International Conference on Medical Image Computing and Computer-Assisted Intervention, Springer Nature, 2017, pp. 566–574.","ama":"Alexandroni G, Podolsky Y, Greenspan H, et al. White matter fiber representation using continuous dictionary learning. In: 20th International Conference on Medical Image Computing and Computer-Assisted Intervention. Vol 10433. Springer Nature; 2017:566-574. doi:10.1007/978-3-319-66182-7_65","ieee":"G. Alexandroni et al., “White matter fiber representation using continuous dictionary learning,” in 20th International Conference on Medical Image Computing and Computer-Assisted Intervention, Quebec City, QC, Canada, 2017, vol. 10433, no. Part 1, pp. 566–574.","chicago":"Alexandroni, Guy, Yana Podolsky, Hayit Greenspan, Tal Remez, Or Litany, Alex M. Bronstein, and Raja Giryes. “White Matter Fiber Representation Using Continuous Dictionary Learning.” In 20th International Conference on Medical Image Computing and Computer-Assisted Intervention, 10433:566–74. Springer Nature, 2017. https://doi.org/10.1007/978-3-319-66182-7_65.","ista":"Alexandroni G, Podolsky Y, Greenspan H, Remez T, Litany O, Bronstein AM, Giryes R. 2017. White matter fiber representation using continuous dictionary learning. 20th International Conference on Medical Image Computing and Computer-Assisted Intervention. MICCAI: Medical Image Computing and Computer-Assisted Intervention, LNCS, vol. 10433, 566–574."},"intvolume":" 10433","abstract":[{"lang":"eng","text":"With increasingly sophisticated Diffusion Weighted MRI acquisition methods and modeling techniques, very large sets of streamlines (fibers) are presently generated per imaged brain. These reconstructions of white matter architecture, which are important for human brain research and pre-surgical planning, require a large amount of storage and are often unwieldy and difficult to manipulate and analyze. This work proposes a novel continuous parsimonious framework in which signals are sparsely represented in a dictionary with continuous atoms. The significant innovation in our new methodology is the ability to train such continuous dictionaries, unlike previous approaches that either used pre-fixed continuous transforms or training with finite atoms. This leads to an innovative fiber representation method, which uses Continuous Dictionary Learning to sparsely code each fiber with high accuracy. This method is tested on numerous tractograms produced from the Human Connectome Project data and achieves state-of-the-art performances in compression ratio and reconstruction error."}],"publication_identifier":{"isbn":["9783319661810"],"eissn":["1611-3349","9783319661827"],"issn":["0302-9743"]}},{"publication_status":"published","day":"01","type":"conference","ddc":["005"],"alternative_title":["LNCS"],"publisher":"Springer","ec_funded":1,"volume":10482,"external_id":{"isi":["000723567800004"]},"corr_author":"1","title":"JTDec: A tool for tree decompositions in soot","language":[{"iso":"eng"}],"page":"59 - 66","_id":"949","year":"2017","file_date_updated":"2020-07-14T12:48:16Z","date_updated":"2026-09-22T22:31:02Z","conference":{"end_date":"2017-10-06","start_date":"2017-10-03","location":"Pune, India","name":"ATVA: Automated Technology for Verification and Analysis"},"doi":"10.1007/978-3-319-68167-2_4","intvolume":" 10482","citation":{"short":"K. Chatterjee, A.K. Goharshady, A. Pavlogiannis, in:, D. D’Souza (Ed.), Springer, 2017, pp. 59–66.","ama":"Chatterjee K, Goharshady AK, Pavlogiannis A. JTDec: A tool for tree decompositions in soot. In: D’Souza D, ed. Vol 10482. Springer; 2017:59-66. doi:10.1007/978-3-319-68167-2_4","chicago":"Chatterjee, Krishnendu, Amir Kafshdar Goharshady, and Andreas Pavlogiannis. “JTDec: A Tool for Tree Decompositions in Soot.” edited by Deepak D’Souza, 10482:59–66. Springer, 2017. https://doi.org/10.1007/978-3-319-68167-2_4.","ieee":"K. Chatterjee, A. K. Goharshady, and A. Pavlogiannis, “JTDec: A tool for tree decompositions in soot,” presented at the ATVA: Automated Technology for Verification and Analysis, Pune, India, 2017, vol. 10482, pp. 59–66.","ista":"Chatterjee K, Goharshady AK, Pavlogiannis A. 2017. JTDec: A tool for tree decompositions in soot. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 10482, 59–66.","mla":"Chatterjee, Krishnendu, et al. JTDec: A Tool for Tree Decompositions in Soot. Edited by Deepak D’Souza, vol. 10482, Springer, 2017, pp. 59–66, doi:10.1007/978-3-319-68167-2_4.","apa":"Chatterjee, K., Goharshady, A. K., & Pavlogiannis, A. (2017). JTDec: A tool for tree decompositions in soot. In D. D’Souza (Ed.) (Vol. 10482, pp. 59–66). Presented at the ATVA: Automated Technology for Verification and Analysis, Pune, India: Springer. https://doi.org/10.1007/978-3-319-68167-2_4"},"publist_id":"6468","abstract":[{"text":"The notion of treewidth of graphs has been exploited for faster algorithms for several problems arising in verification and program analysis. Moreover, various notions of balanced tree decompositions have been used for improved algorithms supporting dynamic updates and analysis of concurrent programs. In this work, we present a tool for constructing tree-decompositions of CFGs obtained from Java methods, which is implemented as an extension to the widely used Soot framework. The experimental results show that our implementation on real-world Java benchmarks is very efficient. Our tool also provides the first implementation for balancing tree-decompositions. In summary, we present the first tool support for exploiting treewidth in the static analysis problems on Java programs.","lang":"eng"}],"publication_identifier":{"issn":["0302-9743"]},"department":[{"_id":"KrCh"}],"oa_version":"Submitted Version","quality_controlled":"1","isi":1,"article_processing_charge":"No","has_accepted_license":"1","month":"01","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","date_published":"2017-01-01T00:00:00Z","status":"public","fulldoi":"https://doi.org/10.1007/978-3-319-68167-2_4","scopus_import":"1","project":[{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"}],"pubrep_id":"845","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"first_name":"Amir","full_name":"Goharshady, Amir","last_name":"Goharshady","id":"391365CE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-1702-6584"},{"first_name":"Andreas","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722"}],"date_created":"2018-12-11T11:49:22Z","editor":[{"first_name":"Deepak","full_name":"D'Souza, Deepak","last_name":"D'Souza"}],"oa":1,"file":[{"content_type":"application/pdf","creator":"system","file_size":948514,"date_updated":"2020-07-14T12:48:16Z","relation":"main_file","checksum":"a0d9f5f94dc594c4e71e78525c9942f1","date_created":"2018-12-12T10:10:45Z","access_level":"open_access","file_id":"4835","file_name":"IST-2017-845-v1+1_2017_Chatterjee_JTDec.pdf"}],"related_material":{"record":[{"id":"8934","status":"public","relation":"dissertation_contains"}]}},{"page":"203 - 216","language":[{"iso":"eng"}],"_id":"1094","year":"2016","title":"Immunogold protein localization on grid-glued freeze-fracture replicas","publication":"High-Resolution Imaging of Cellular Proteins","ec_funded":1,"volume":1474,"publisher":"Springer","alternative_title":["Methods in Molecular Biology"],"type":"book_chapter","day":"12","publication_status":"published","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"]},"abstract":[{"lang":"eng","text":"Immunogold labeling of freeze-fracture replicas has recently been used for high-resolution visualization of protein localization in electron microscopy. This method has higher labeling efficiency than conventional immunogold methods for membrane molecules allowing precise quantitative measurements. However, one of the limitations of freeze-fracture replica immunolabeling is difficulty in keeping structural orientation and identifying labeled profiles in complex tissues like brain. The difficulty is partly due to fragmentation of freeze-fracture replica preparations during labeling procedures and limited morphological clues on the replica surface. To overcome these issues, we introduce here a grid-glued replica method combined with SEM observation. This method allows histological staining before dissolving the tissue and easy handling of replicas during immunogold labeling, and keeps the whole replica surface intact without fragmentation. The procedure described here is also useful for matched double-replica analysis allowing further identification of labeled profiles in corresponding P-face and E-face."}],"publist_id":"6281","intvolume":" 1474","citation":{"apa":"Harada, H., & Shigemoto, R. (2016). Immunogold protein localization on grid-glued freeze-fracture replicas. In High-Resolution Imaging of Cellular Proteins (Vol. 1474, pp. 203–216). Springer. https://doi.org/10.1007/978-1-4939-6352-2_12","mla":"Harada, Harumi, and Ryuichi Shigemoto. “Immunogold Protein Localization on Grid-Glued Freeze-Fracture Replicas.” High-Resolution Imaging of Cellular Proteins, vol. 1474, Springer, 2016, pp. 203–16, doi:10.1007/978-1-4939-6352-2_12.","chicago":"Harada, Harumi, and Ryuichi Shigemoto. “Immunogold Protein Localization on Grid-Glued Freeze-Fracture Replicas.” In High-Resolution Imaging of Cellular Proteins, 1474:203–16. Springer, 2016. https://doi.org/10.1007/978-1-4939-6352-2_12.","ieee":"H. Harada and R. Shigemoto, “Immunogold protein localization on grid-glued freeze-fracture replicas,” in High-Resolution Imaging of Cellular Proteins, vol. 1474, Springer, 2016, pp. 203–216.","ista":"Harada H, Shigemoto R. 2016.Immunogold protein localization on grid-glued freeze-fracture replicas. In: High-Resolution Imaging of Cellular Proteins. Methods in Molecular Biology, vol. 1474, 203–216.","short":"H. Harada, R. Shigemoto, in:, High-Resolution Imaging of Cellular Proteins, Springer, 2016, pp. 203–216.","ama":"Harada H, Shigemoto R. Immunogold protein localization on grid-glued freeze-fracture replicas. In: High-Resolution Imaging of Cellular Proteins. Vol 1474. Springer; 2016:203-216. doi:10.1007/978-1-4939-6352-2_12"},"doi":"10.1007/978-1-4939-6352-2_12","date_updated":"2025-04-15T07:12:21Z","month":"08","article_processing_charge":"No","department":[{"_id":"RySh"}],"oa_version":"None","quality_controlled":"1","date_created":"2018-12-11T11:50:06Z","acknowledged_ssus":[{"_id":"EM-Fac"}],"project":[{"_id":"25CD3DD2-B435-11E9-9278-68D0E5697425","grant_number":"604102","call_identifier":"FP7","name":"Localization of ion channels and receptors by two and three-dimensional immunoelectron microscopic approaches"}],"author":[{"orcid":"0000-0001-7429-7896","id":"2E55CDF2-F248-11E8-B48F-1D18A9856A87","last_name":"Harada","full_name":"Harada, Harumi","first_name":"Harumi"},{"orcid":"0000-0001-8761-9444","id":"499F3ABC-F248-11E8-B48F-1D18A9856A87","last_name":"Shigemoto","full_name":"Shigemoto, Ryuichi","first_name":"Ryuichi"}],"acknowledgement":"We thank Prof. Elek Molnár for providing us a pan-AMPAR anti-body used in Fig.2 and Dr. Ludek Lovicar for technical assistance in scanning electron microscope imaging. This work was supported by the European Union (HBP—Project Ref. 604102). ","fulldoi":"https://doi.org/10.1007/978-1-4939-6352-2_12","status":"public","date_published":"2016-08-12T00:00:00Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1"},{"volume":9667,"alternative_title":["LNCS"],"publisher":"Springer Nature","page":"253-264","language":[{"iso":"eng"}],"_id":"5805","year":"2016","title":"On some local topological properties of naive discrete sphere","publication":"Computational Topology in Image Context","day":"02","publication_status":"published","type":"book_chapter","abstract":[{"lang":"eng","text":"Discretization of sphere in the integer space follows a particular discretization scheme, which, in principle, conforms to some topological model. This eventually gives rise to interesting topological properties of a discrete spherical surface, which need to be investigated for its analytical characterization. This paper presents some novel results on the local topological properties of the naive model of discrete sphere. They follow from the bijection of each quadraginta octant of naive sphere with its projection map called f -map on the corresponding functional plane and from the characterization of certain jumps in the f-map. As an application, we have shown how these properties can be used in designing an efficient reconstruction algorithm for a naive spherical surface from an input voxel set when it is sparse or noisy."}],"publication_identifier":{"issn":["0302-9743"],"eisbn":["978-3-319-39441-1"],"isbn":["978-3-319-39440-4"],"eissn":["1611-3349"]},"doi":"10.1007/978-3-319-39441-1_23","conference":{"end_date":"2016-06-17","start_date":"2016-06-15","location":"Marseille, France","name":"CTIC: Computational Topology in Image Context"},"date_updated":"2022-01-28T08:01:22Z","intvolume":" 9667","citation":{"short":"N. Sen, R. Biswas, P. Bhowmick, in:, Computational Topology in Image Context, Springer Nature, Cham, 2016, pp. 253–264.","ama":"Sen N, Biswas R, Bhowmick P. On some local topological properties of naive discrete sphere. In: Computational Topology in Image Context. Vol 9667. Cham: Springer Nature; 2016:253-264. doi:10.1007/978-3-319-39441-1_23","chicago":"Sen, Nabhasmita, Ranita Biswas, and Partha Bhowmick. “On Some Local Topological Properties of Naive Discrete Sphere.” In Computational Topology in Image Context, 9667:253–64. Cham: Springer Nature, 2016. https://doi.org/10.1007/978-3-319-39441-1_23.","ieee":"N. Sen, R. Biswas, and P. Bhowmick, “On some local topological properties of naive discrete sphere,” in Computational Topology in Image Context, vol. 9667, Cham: Springer Nature, 2016, pp. 253–264.","ista":"Sen N, Biswas R, Bhowmick P. 2016.On some local topological properties of naive discrete sphere. In: Computational Topology in Image Context. LNCS, vol. 9667, 253–264.","mla":"Sen, Nabhasmita, et al. “On Some Local Topological Properties of Naive Discrete Sphere.” Computational Topology in Image Context, vol. 9667, Springer Nature, 2016, pp. 253–64, doi:10.1007/978-3-319-39441-1_23.","apa":"Sen, N., Biswas, R., & Bhowmick, P. (2016). On some local topological properties of naive discrete sphere. In Computational Topology in Image Context (Vol. 9667, pp. 253–264). Cham: Springer Nature. https://doi.org/10.1007/978-3-319-39441-1_23"},"month":"06","oa_version":"None","department":[{"_id":"HeEd"}],"quality_controlled":"1","place":"Cham","article_processing_charge":"No","date_created":"2019-01-08T20:44:24Z","extern":"1","status":"public","fulldoi":"https://doi.org/10.1007/978-3-319-39441-1_23","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","date_published":"2016-06-02T00:00:00Z","author":[{"first_name":"Nabhasmita","last_name":"Sen","full_name":"Sen, Nabhasmita"},{"orcid":"0000-0002-5372-7890","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","last_name":"Biswas","full_name":"Biswas, Ranita","first_name":"Ranita"},{"full_name":"Bhowmick, Partha","last_name":"Bhowmick","first_name":"Partha"}]},{"abstract":[{"text":"Although the concept of functional plane for naive plane is studied and reported in the literature in great detail, no similar study is yet found for naive sphere. This article exposes the first study in this line, opening up further prospects of analyzing the topological properties of sphere in the discrete space. We show that each quadraginta octant Q of a naive sphere forms a bijection with its projected pixel set on a unique coordinate plane, which thereby serves as the functional plane of Q, and hence gives rise to merely mono-jumps during back projection. The other two coordinate planes serve as para-functional and dia-functional planes for Q, as the former is ‘mono-jumping’ but not bijective, whereas the latter holds neither of the two. Owing to this, the quadraginta octants form symmetry groups and subgroups with equivalent jump conditions. We also show a potential application in generating a special class of discrete 3D circles based on back projection and jump bridging by Steiner voxels. A circle in this class possesses 4-symmetry, uniqueness, and bounded distance from the underlying real sphere and real plane.","lang":"eng"}],"publication_identifier":{"isbn":["978-3-319-32359-6"],"eisbn":["978-3-319-32360-2"],"issn":["0302-9743","1611-3349"]},"doi":"10.1007/978-3-319-32360-2_20","conference":{"location":"Nantes, France","name":"DGCI: International Conference on Discrete Geometry for Computer Imagery","end_date":"2016-04-20","start_date":"2016-04-18"},"date_updated":"2022-01-28T08:10:11Z","intvolume":" 9647","citation":{"apa":"Biswas, R., & Bhowmick, P. (2016). On functionality of quadraginta octants of naive sphere with application to circle drawing. In Discrete Geometry for Computer Imagery (Vol. 9647, pp. 256–267). Cham: Springer Nature. https://doi.org/10.1007/978-3-319-32360-2_20","mla":"Biswas, Ranita, and Partha Bhowmick. “On Functionality of Quadraginta Octants of Naive Sphere with Application to Circle Drawing.” Discrete Geometry for Computer Imagery, vol. 9647, Springer Nature, 2016, pp. 256–67, doi:10.1007/978-3-319-32360-2_20.","ieee":"R. Biswas and P. Bhowmick, “On functionality of quadraginta octants of naive sphere with application to circle drawing,” in Discrete Geometry for Computer Imagery, Nantes, France, 2016, vol. 9647, pp. 256–267.","chicago":"Biswas, Ranita, and Partha Bhowmick. “On Functionality of Quadraginta Octants of Naive Sphere with Application to Circle Drawing.” In Discrete Geometry for Computer Imagery, 9647:256–67. Cham: Springer Nature, 2016. https://doi.org/10.1007/978-3-319-32360-2_20.","ista":"Biswas R, Bhowmick P. 2016. On functionality of quadraginta octants of naive sphere with application to circle drawing. Discrete Geometry for Computer Imagery. DGCI: International Conference on Discrete Geometry for Computer Imagery, LNCS, vol. 9647, 256–267.","short":"R. Biswas, P. Bhowmick, in:, Discrete Geometry for Computer Imagery, Springer Nature, Cham, 2016, pp. 256–267.","ama":"Biswas R, Bhowmick P. On functionality of quadraginta octants of naive sphere with application to circle drawing. In: Discrete Geometry for Computer Imagery. Vol 9647. Cham: Springer Nature; 2016:256-267. doi:10.1007/978-3-319-32360-2_20"},"volume":9647,"publisher":"Springer Nature","alternative_title":["LNCS"],"language":[{"iso":"eng"}],"page":"256-267","_id":"5806","year":"2016","title":"On functionality of quadraginta octants of naive sphere with application to circle drawing","publication":"Discrete Geometry for Computer Imagery","day":"09","publication_status":"published","type":"conference","date_created":"2019-01-08T20:44:37Z","extern":"1","status":"public","fulldoi":"https://doi.org/10.1007/978-3-319-32360-2_20","date_published":"2016-04-09T00:00:00Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","author":[{"id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5372-7890","first_name":"Ranita","last_name":"Biswas","full_name":"Biswas, Ranita"},{"full_name":"Bhowmick, Partha","last_name":"Bhowmick","first_name":"Partha"}],"month":"04","oa_version":"None","department":[{"_id":"HeEd"}],"quality_controlled":"1","place":"Cham","article_processing_charge":"No"},{"title":"On the connectivity and smoothness of discrete spherical circles","publication":"Combinatorial image analysis","page":"86-100","language":[{"iso":"eng"}],"_id":"5809","year":"2016","publisher":"Springer Nature","volume":9448,"type":"book_chapter","publication_status":"published","day":"06","publication_identifier":{"issn":["0302-9743"],"eisbn":["978-3-319-26145-4"],"isbn":["978-3-319-26144-7"],"eissn":["1611-3349"]},"abstract":[{"text":"A discrete spherical circle is a topologically well-connected 3D circle in the integer space, which belongs to a discrete sphere as well as a discrete plane. It is one of the most important 3D geometric primitives, but has not possibly yet been studied up to its merit. This paper is a maiden exposition of some of its elementary properties, which indicates a sense of its profound theoretical prospects in the framework of digital geometry. We have shown how different types of discretization can lead to forbidden and admissible classes, when one attempts to define the discretization of a spherical circle in terms of intersection between a discrete sphere and a discrete plane. Several fundamental theoretical results have been presented, the algorithm for construction of discrete spherical circles has been discussed, and some test results have been furnished to demonstrate its practicality and usefulness.","lang":"eng"}],"intvolume":" 9448","citation":{"mla":"Biswas, Ranita, et al. “On the Connectivity and Smoothness of Discrete Spherical Circles.” Combinatorial Image Analysis, vol. 9448, Springer Nature, 2016, pp. 86–100, doi:10.1007/978-3-319-26145-4_7.","apa":"Biswas, R., Bhowmick, P., & Brimkov, V. E. (2016). On the connectivity and smoothness of discrete spherical circles. In Combinatorial image analysis (Vol. 9448, pp. 86–100). Cham: Springer Nature. https://doi.org/10.1007/978-3-319-26145-4_7","ama":"Biswas R, Bhowmick P, Brimkov VE. On the connectivity and smoothness of discrete spherical circles. In: Combinatorial Image Analysis. Vol 9448. Cham: Springer Nature; 2016:86-100. doi:10.1007/978-3-319-26145-4_7","short":"R. Biswas, P. Bhowmick, V.E. Brimkov, in:, Combinatorial Image Analysis, Springer Nature, Cham, 2016, pp. 86–100.","ieee":"R. Biswas, P. Bhowmick, and V. E. Brimkov, “On the connectivity and smoothness of discrete spherical circles,” in Combinatorial image analysis, vol. 9448, Cham: Springer Nature, 2016, pp. 86–100.","ista":"Biswas R, Bhowmick P, Brimkov VE. 2016.On the connectivity and smoothness of discrete spherical circles. In: Combinatorial image analysis. vol. 9448, 86–100.","chicago":"Biswas, Ranita, Partha Bhowmick, and Valentin E. Brimkov. “On the Connectivity and Smoothness of Discrete Spherical Circles.” In Combinatorial Image Analysis, 9448:86–100. Cham: Springer Nature, 2016. https://doi.org/10.1007/978-3-319-26145-4_7."},"date_updated":"2022-01-28T08:13:03Z","conference":{"location":"Kolkata, India","name":"IWCIA: International Workshop on Combinatorial Image Analysis","end_date":"2015-11-27","start_date":"2015-11-24"},"doi":"10.1007/978-3-319-26145-4_7","month":"01","article_processing_charge":"No","place":"Cham","oa_version":"None","department":[{"_id":"HeEd"}],"quality_controlled":"1","date_created":"2019-01-08T20:45:19Z","extern":"1","author":[{"id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5372-7890","first_name":"Ranita","last_name":"Biswas","full_name":"Biswas, Ranita"},{"last_name":"Bhowmick","full_name":"Bhowmick, Partha","first_name":"Partha"},{"last_name":"Brimkov","full_name":"Brimkov, Valentin E.","first_name":"Valentin E."}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","date_published":"2016-01-06T00:00:00Z","status":"public","fulldoi":"https://doi.org/10.1007/978-3-319-26145-4_7"},{"date_created":"2022-08-08T13:33:56Z","extern":"1","oa":1,"scopus_import":"1","author":[{"first_name":"Oren","last_name":"Ben-Zwi","full_name":"Ben-Zwi, Oren"},{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","last_name":"Henzinger","first_name":"Monika H"},{"first_name":"Veronika","last_name":"Loitzenbauer","full_name":"Loitzenbauer, Veronika"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2015-12-09T00:00:00Z","fulldoi":"https://doi.org/10.1007/978-3-662-48995-6_8","status":"public","month":"12","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1604.05562"}],"article_processing_charge":"No","arxiv":1,"oa_version":"Preprint","quality_controlled":"1","publication_identifier":{"issn":["0302-9743"],"eisbn":["9783662489956"],"isbn":["9783662489949"]},"abstract":[{"text":"Ad exchanges are an emerging platform for trading advertisement slots on the web with billions of dollars revenue per year. Every time a user visits a web page, the publisher of that web page can ask an ad exchange to auction off the ad slots on this page to determine which advertisements are shown at which price. Due to the high volume of traffic, ad networks typically act as mediators for individual advertisers at ad exchanges. If multiple advertisers in an ad network are interested in the ad slots of the same auction, the ad network might use a “local” auction to resell the obtained ad slots among its advertisers.\r\n\r\nIn this work we want to deepen the theoretical understanding of these new markets by analyzing them from the viewpoint of combinatorial auctions. Prior work studied mostly single-item auctions, while we allow the advertisers to express richer preferences over multiple items. We develop a game-theoretic model for the entanglement of the central auction at the ad exchange with the local auctions at the ad networks. We consider the incentives of all three involved parties and suggest a three-party competitive equilibrium, an extension of the Walrasian equilibrium that ensures envy-freeness for all participants. We show the existence of a three-party competitive equilibrium and a polynomial-time algorithm to find one for gross-substitute bidder valuations.","lang":"eng"}],"intvolume":" 9470","citation":{"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","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.","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.","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.","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.","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","short":"O. Ben-Zwi, M. Henzinger, V. Loitzenbauer, in:, 11th International Conference on Web and Internet Economics, Springer Nature, 2015, pp. 104–117."},"date_updated":"2024-11-06T12:10:25Z","doi":"10.1007/978-3-662-48995-6_8","conference":{"location":"Amsterdam, Netherlands","name":"WINE: International Conference on Web and Internet Economics","end_date":"2015-09-12","start_date":"2015-09-09"},"title":"Ad exchange: Envy-free auctions with mediators","publication":"11th International Conference on Web and Internet Economics","language":[{"iso":"eng"}],"page":"104–117","year":"2015","_id":"11773","alternative_title":["LNCS"],"publisher":"Springer Nature","volume":9470,"external_id":{"arxiv":["1604.05562"]},"type":"conference","publication_status":"published","day":"09"},{"month":"12","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1509.09147","open_access":"1"}],"article_processing_charge":"No","quality_controlled":"1","oa_version":"Preprint","arxiv":1,"extern":"1","date_created":"2022-08-08T13:54:32Z","oa":1,"author":[{"first_name":"Yun Kuen","full_name":"Cheung, Yun Kuen","last_name":"Cheung"},{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","first_name":"Monika H"},{"full_name":"Hoefer, Martin","last_name":"Hoefer","first_name":"Martin"},{"full_name":"Starnberger, Martin","last_name":"Starnberger","first_name":"Martin"}],"scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2015-12-09T00:00:00Z","status":"public","fulldoi":"https://doi.org/10.1007/978-3-662-48995-6_17","publication":"11th International Conference on Web and Internet Economics","title":"Combinatorial auctions with conflict-based externalities","_id":"11774","year":"2015","language":[{"iso":"eng"}],"page":"230–243","publisher":"Springer Nature","alternative_title":["LNCS"],"external_id":{"arxiv":["1509.09147"]},"volume":9470,"type":"conference","publication_status":"published","day":"09","publication_identifier":{"isbn":["9783662489949"],"issn":["0302-9743"],"eisbn":["9783662489956"]},"abstract":[{"text":"Combinatorial auctions (CA) are a well-studied area in algorithmic mechanism design. However, contrary to the standard model, empirical studies suggest that a bidder’s valuation often does not depend solely on the goods assigned to him. For instance, in adwords auctions an advertiser might not want his ads to be displayed next to his competitors’ ads. In this paper, we propose and analyze several natural graph-theoretic models that incorporate such negative externalities, in which bidders form a directed conflict graph with maximum out-degree Δ. We design algorithms and truthful mechanisms for social welfare maximization that attain approximation ratios depending on Δ.\r\n\r\nFor CA, our results are twofold: (1) A lottery that eliminates conflicts by discarding bidders/items independent of the bids. It allows to apply any truthful 𝛼-approximation mechanism for conflict-free valuations and yields an 𝒪(𝛼Δ)-approximation mechanism. (2) For fractionally sub-additive valuations, we design a rounding algorithm via a novel combination of a semi-definite program and a linear program, resulting in a cone program; the approximation ratio is 𝒪((ΔloglogΔ)/logΔ). The ratios are almost optimal given existing hardness results.\r\n\r\nFor adwords auctions, we present several algorithms for the most relevant scenario when the number of items is small. In particular, we design a truthful mechanism with approximation ratio 𝑜(Δ) when the number of items is only logarithmic in the number of bidders.","lang":"eng"}],"citation":{"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","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.","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.","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.","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.","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","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."},"intvolume":" 9470","date_updated":"2024-11-06T12:10:38Z","doi":"10.1007/978-3-662-48995-6_17","conference":{"end_date":"2015-12-12","start_date":"2015-12-09","location":"Amsterdam, Netherlands","name":"WINE: International Conference on Web and Internet Economics"}},{"date_updated":"2024-11-06T12:10:50Z","conference":{"start_date":"2015-07-06","end_date":"2015-07-10","name":"ICALP: International Colloquium on Automata, Languages, and Programming","location":"Kyoto, Japan"},"doi":"10.1007/978-3-662-47672-7_59","intvolume":" 9134","citation":{"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","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.","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.","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","short":"M. Henzinger, S. Krinninger, D. Nanongkai, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 725–736."},"abstract":[{"text":"Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with 𝑜(𝑚𝑛) total update time, where 𝑚 is the number of edges and 𝑛 is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different 𝑚 vs. 𝑛 trade-off. For the case of 𝑚=Θ(𝑛1.5) the running time is 𝑂(𝑛2.47), just barely below 𝑚𝑛=Θ(𝑛2.5). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of 𝑂̃ (min(𝑚7/6𝑛2/3,𝑚3/4𝑛5/4+𝑜(1),𝑚2/3𝑛4/3+𝑜(1)+𝑚3/7𝑛12/7+𝑜(1))). This gives, e.g., 𝑂(𝑛2.36) for the notorious case 𝑚=Θ(𝑛1.5). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.","lang":"eng"}],"publication_identifier":{"isbn":["9783662476710"],"issn":["0302-9743"]},"publication_status":"published","day":"01","type":"conference","publisher":"Springer Nature","alternative_title":["LNCS"],"volume":9134,"external_id":{"arxiv":["1612.03856"]},"title":"Improved algorithms for decremental single-source reachability on directed graphs","publication":"42nd International Colloquium on Automata, Languages and Programming","language":[{"iso":"eng"}],"page":"725 - 736","_id":"11785","year":"2015","date_published":"2015-01-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.1007/978-3-662-47672-7_59","status":"public","scopus_import":"1","author":[{"first_name":"Monika H","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"full_name":"Krinninger, Sebastian","last_name":"Krinninger","first_name":"Sebastian"},{"last_name":"Nanongkai","full_name":"Nanongkai, Danupon","first_name":"Danupon"}],"date_created":"2022-08-11T08:51:32Z","extern":"1","oa":1,"oa_version":"Preprint","arxiv":1,"quality_controlled":"1","article_processing_charge":"No","main_file_link":[{"url":"https://arxiv.org/abs/1612.03856","open_access":"1"}],"month":"01"},{"volume":9134,"external_id":{"arxiv":["1604.05337"]},"alternative_title":["LNCS"],"publisher":"Springer Nature","page":"206 - 218","language":[{"iso":"eng"}],"_id":"11786","year":"2015","title":"Design of dynamic algorithms via primal-dual method","publication":"42nd International Colloquium on Automata, Languages and Programming","day":"01","publication_status":"published","type":"conference","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 𝑂(𝑓2)-approximately optimal solution in 𝑂(𝑓⋅log(𝑚+𝑛)) amortized update time, where 𝑓 is the maximum “frequency” of an element, 𝑛 is the number of sets, and 𝑚 is the maximum number of elements in the universe at any point in time. (2) For the dynamic 𝑏-matching problem, we maintain an 𝑂(1)-approximately optimal solution in 𝑂(log3𝑛) amortized update time, where 𝑛 is the number of nodes in the graph."}],"publication_identifier":{"isbn":["9783662476710"],"issn":["0302-9743"]},"conference":{"name":"ICALP: International Colloquium on Automata, Languages, and Programming","location":"Kyoto, Japan","start_date":"2015-07-06","end_date":"2015-07-10"},"doi":"10.1007/978-3-662-47672-7_17","date_updated":"2024-11-06T12:11:02Z","intvolume":" 9134","citation":{"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","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.","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.","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.","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.","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","short":"S. Bhattacharya, M. Henzinger, G.F. Italiano, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 206–218."},"main_file_link":[{"url":"https://arxiv.org/abs/1604.05337","open_access":"1"}],"month":"01","oa_version":"Preprint","arxiv":1,"quality_controlled":"1","article_processing_charge":"No","oa":1,"date_created":"2022-08-11T09:28:49Z","extern":"1","status":"public","fulldoi":"https://doi.org/10.1007/978-3-662-47672-7_17","date_published":"2015-01-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","author":[{"first_name":"Sayan","last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H","last_name":"Henzinger"},{"last_name":"Italiano","full_name":"Italiano, Giuseppe F.","first_name":"Giuseppe F."}]}]