[{"series_title":"LIPIcs","language":[{"iso":"eng"}],"date_updated":"2022-01-06T06:50:45Z","doi":"10.4230/LIPICS.ICALP.2019.150","department":[{"_id":"79"}],"publication_status":"published","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subproject A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}],"title":"On the Complexity of Local Graph Transformations","page":"150:1--150:14","citation":{"short":"C. Scheideler, A. Setzer, in: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Dagstuhl Publishing, 2019, pp. 150:1--150:14.","ieee":"C. Scheideler and A. Setzer, “On the Complexity of Local Graph Transformations,” in Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Patras, Greece, 2019, vol. 132, pp. 150:1--150:14.","ama":"Scheideler C, Setzer A. On the Complexity of Local Graph Transformations. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming. Vol 132. LIPIcs. Dagstuhl Publishing; 2019:150:1--150:14. doi:10.4230/LIPICS.ICALP.2019.150","apa":"Scheideler, C., & Setzer, A. (2019). On the Complexity of Local Graph Transformations. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (Vol. 132, pp. 150:1--150:14). Patras, Greece: Dagstuhl Publishing. https://doi.org/10.4230/LIPICS.ICALP.2019.150","chicago":"Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local Graph Transformations.” In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 132:150:1--150:14. LIPIcs. Dagstuhl Publishing, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.150.","bibtex":"@inproceedings{Scheideler_Setzer_2019, series={LIPIcs}, title={On the Complexity of Local Graph Transformations}, volume={132}, DOI={10.4230/LIPICS.ICALP.2019.150}, booktitle={Proceedings of the 46th International Colloquium on Automata, Languages, and Programming}, publisher={Dagstuhl Publishing}, author={Scheideler, Christian and Setzer, Alexander}, year={2019}, pages={150:1--150:14}, collection={LIPIcs} }","mla":"Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local Graph Transformations.” Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, vol. 132, Dagstuhl Publishing, 2019, pp. 150:1--150:14, doi:10.4230/LIPICS.ICALP.2019.150."},"year":"2019","type":"conference","conference":{"end_date":"2019-07-12","name":"ICALP 2019","start_date":"2019-07-09","location":"Patras, Greece"},"intvolume":" 132","_id":"10586","file_date_updated":"2019-08-26T09:21:27Z","publication":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming","keyword":["Graphs transformations","NP-hardness","approximation algorithms"],"author":[{"id":"20792","last_name":"Scheideler","full_name":"Scheideler, Christian","first_name":"Christian"},{"first_name":"Alexander","full_name":"Setzer, Alexander","last_name":"Setzer","id":"11108"}],"publisher":"Dagstuhl Publishing","file":[{"date_created":"2019-08-26T09:21:27Z","file_name":"LIPIcs-ICALP-2019-150.pdf","access_level":"closed","file_size":537649,"creator":"ups","file_id":"12955","date_updated":"2019-08-26T09:21:27Z","content_type":"application/pdf","relation":"main_file","success":1}],"volume":132,"date_created":"2019-07-08T17:19:01Z","has_accepted_license":"1","status":"public","abstract":[{"text":"We consider the problem of transforming a given graph G_s into a desired graph G_t by applying a minimum number of primitives from a particular set of local graph transformation primitives. These primitives are local in the sense that each node can apply them based on local knowledge and by affecting only its 1-neighborhood. Although the specific set of primitives we consider makes it possible to transform any (weakly) connected graph into any other (weakly) connected graph consisting of the same nodes, they cannot disconnect the graph or introduce new nodes into the graph, making them ideal in the context of supervised overlay network transformations. We prove that computing a minimum sequence of primitive applications (even centralized) for arbitrary G_s and G_t is NP-hard, which we conjecture to hold for any set of local graph transformation primitives satisfying the aforementioned properties. On the other hand, we show that this problem admits a polynomial time algorithm with a constant approximation ratio.","lang":"eng"}],"ddc":["004"],"user_id":"477"},{"language":[{"iso":"eng"}],"doi":"10.1109/icdm.2016.0094","date_updated":"2022-01-06T06:55:58Z","publication_identifier":{"isbn":["9781509054732"]},"publication_status":"published","department":[{"_id":"64"}],"title":"A Theoretical Analysis of the Fuzzy K-Means Problem","year":"2016","citation":{"ieee":"J. Blömer, S. Brauer, and K. Bujna, “A Theoretical Analysis of the Fuzzy K-Means Problem,” in 2016 IEEE 16th International Conference on Data Mining (ICDM), Barcelona, Spain, 2016, pp. 805–810.","short":"J. Blömer, S. Brauer, K. Bujna, in: 2016 IEEE 16th International Conference on Data Mining (ICDM), IEEE, 2016, pp. 805–810.","bibtex":"@inproceedings{Blömer_Brauer_Bujna_2016, title={A Theoretical Analysis of the Fuzzy K-Means Problem}, DOI={10.1109/icdm.2016.0094}, booktitle={2016 IEEE 16th International Conference on Data Mining (ICDM)}, publisher={IEEE}, author={Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}, year={2016}, pages={805–810} }","mla":"Blömer, Johannes, et al. “A Theoretical Analysis of the Fuzzy K-Means Problem.” 2016 IEEE 16th International Conference on Data Mining (ICDM), IEEE, 2016, pp. 805–10, doi:10.1109/icdm.2016.0094.","apa":"Blömer, J., Brauer, S., & Bujna, K. (2016). A Theoretical Analysis of the Fuzzy K-Means Problem. In 2016 IEEE 16th International Conference on Data Mining (ICDM) (pp. 805–810). Barcelona, Spain: IEEE. https://doi.org/10.1109/icdm.2016.0094","ama":"Blömer J, Brauer S, Bujna K. A Theoretical Analysis of the Fuzzy K-Means Problem. In: 2016 IEEE 16th International Conference on Data Mining (ICDM). IEEE; 2016:805-810. doi:10.1109/icdm.2016.0094","chicago":"Blömer, Johannes, Sascha Brauer, and Kathrin Bujna. “A Theoretical Analysis of the Fuzzy K-Means Problem.” In 2016 IEEE 16th International Conference on Data Mining (ICDM), 805–10. IEEE, 2016. https://doi.org/10.1109/icdm.2016.0094."},"type":"conference","page":"805-810","_id":"2367","conference":{"end_date":"2016-12-15","start_date":"2016-12-12","name":"IEEE 16th International Conference on Data Mining (ICDM)","location":"Barcelona, Spain"},"status":"public","date_created":"2018-04-17T11:46:07Z","author":[{"full_name":"Blömer, Johannes","first_name":"Johannes","id":"23","last_name":"Blömer"},{"last_name":"Brauer","id":"13291","first_name":"Sascha","full_name":"Brauer, Sascha"},{"last_name":"Bujna","full_name":"Bujna, Kathrin","first_name":"Kathrin"}],"publisher":"IEEE","publication":"2016 IEEE 16th International Conference on Data Mining (ICDM)","keyword":["unsolvability by radicals","clustering","fuzzy k-means","probabilistic method","approximation algorithms","randomized algorithms"],"user_id":"25078","abstract":[{"text":"One of the most popular fuzzy clustering techniques is the fuzzy K-means algorithm (also known as fuzzy-c-means or FCM algorithm). In contrast to the K-means and K-median problem, the underlying fuzzy K-means problem has not been studied from a theoretical point of view. In particular, there are no algorithms with approximation guarantees similar to the famous K-means++ algorithm known for the fuzzy K-means problem. This work initiates the study of the fuzzy K-means problem from an algorithmic and complexity theoretic perspective. We show that optimal solutions for the fuzzy K-means problem cannot, in general, be expressed by radicals over the input points. Surprisingly, this already holds for simple inputs in one-dimensional space. Hence, one cannot expect to compute optimal solutions exactly. We give the first (1+eps)-approximation algorithms for the fuzzy K-means problem. First, we present a deterministic approximation algorithm whose runtime is polynomial in N and linear in the dimension D of the input set, given that K is constant, i.e. a polynomial time approximation scheme (PTAS) for fixed K. We achieve this result by showing that for each soft clustering there exists a hard clustering with similar properties. Second, by using techniques known from coreset constructions for the K-means problem, we develop a deterministic approximation algorithm that runs in time almost linear in N but exponential in the dimension D. We complement these results with a randomized algorithm which imposes some natural restrictions on the sought solution and whose runtime is comparable to some of the most efficient approximation algorithms for K-means, i.e. linear in the number of points and the dimension, but exponential in the number of clusters.","lang":"eng"}]},{"language":[{"iso":"eng"}],"doi":"10.1109/TCC.2015.2487964","date_updated":"2022-01-06T06:53:16Z","publication_identifier":{"issn":["2168-7161"]},"department":[{"_id":"63"},{"_id":"541"}],"title":"Inter-Datacenter Scheduling of Large Data Flows","page":"1-1","citation":{"ieee":"R. Cohen and G. Polevoy, “Inter-Datacenter Scheduling of Large Data Flows,” Cloud Computing, IEEE Transactions on, vol. PP, no. 99, pp. 1–1, 2015.","short":"R. Cohen, G. Polevoy, Cloud Computing, IEEE Transactions On PP (2015) 1–1.","bibtex":"@article{Cohen_Polevoy_2015, title={Inter-Datacenter Scheduling of Large Data Flows}, volume={PP}, DOI={10.1109/TCC.2015.2487964}, number={99}, journal={Cloud Computing, IEEE Transactions on}, author={Cohen, R. and Polevoy, Gleb}, year={2015}, pages={1–1} }","mla":"Cohen, R., and Gleb Polevoy. “Inter-Datacenter Scheduling of Large Data Flows.” Cloud Computing, IEEE Transactions On, vol. PP, no. 99, 2015, pp. 1–1, doi:10.1109/TCC.2015.2487964.","chicago":"Cohen, R., and Gleb Polevoy. “Inter-Datacenter Scheduling of Large Data Flows.” Cloud Computing, IEEE Transactions On PP, no. 99 (2015): 1–1. https://doi.org/10.1109/TCC.2015.2487964.","ama":"Cohen R, Polevoy G. Inter-Datacenter Scheduling of Large Data Flows. Cloud Computing, IEEE Transactions on. 2015;PP(99):1-1. doi:10.1109/TCC.2015.2487964","apa":"Cohen, R., & Polevoy, G. (2015). Inter-Datacenter Scheduling of Large Data Flows. Cloud Computing, IEEE Transactions On, PP(99), 1–1. https://doi.org/10.1109/TCC.2015.2487964"},"type":"journal_article","year":"2015","issue":"99","_id":"17657","date_created":"2020-08-06T15:20:58Z","status":"public","volume":"PP","publication":"Cloud Computing, IEEE Transactions on","keyword":["Approximation algorithms","Approximation methods","Bandwidth","Cloud computing","Routing","Schedules","Scheduling"],"author":[{"first_name":"R.","full_name":"Cohen, R.","last_name":"Cohen"},{"id":"83983","last_name":"Polevoy","full_name":"Polevoy, Gleb","first_name":"Gleb"}],"user_id":"83983","abstract":[{"text":"Inter-datacenter transfers of non-interactive but timely large flows over a private (managed) network is an important problem faced by many cloud service providers. The considered flows are non-interactive because they do not explicitly target the end users. However, most of them must be performed on a timely basis and are associated with a deadline. We propose to schedule these flows by a centralized controller, which determines when to transmit each flow and which path to use. Two scheduling models are presented in this paper. In the first, the controller also determines the rate of each flow, while in the second bandwidth is assigned by the network according to the TCP rules. We develop scheduling algorithms for both models and compare their complexity and performance.","lang":"eng"}],"extern":"1"},{"department":[{"_id":"63"},{"_id":"541"}],"publication_identifier":{"issn":["1063-6692"]},"title":"On the Admission of Dependent Flows in Powerful Sensor Networks","language":[{"iso":"eng"}],"date_updated":"2022-01-06T06:53:16Z","doi":"10.1109/TNET.2012.2227792","author":[{"last_name":"Cohen","first_name":"R.","full_name":"Cohen, R."},{"full_name":"Nudelman, I.","first_name":"I.","last_name":"Nudelman"},{"full_name":"Polevoy, Gleb","first_name":"Gleb","id":"83983","last_name":"Polevoy"}],"publication":"Networking, IEEE/ACM Transactions on","keyword":["Approximation algorithms","Approximation methods","Bandwidth","Logic gates","Radar","Vectors","Wireless sensor networks","Dependent flow scheduling","sensor networks"],"status":"public","date_created":"2020-08-06T15:22:05Z","volume":21,"abstract":[{"text":"In this paper, we define and study a new problem, referred to as the Dependent Unsplittable Flow Problem (D-UFP). We present and discuss this problem in the context of large-scale powerful (radar/camera) sensor networks, but we believe it has important applications on the admission of large flows in other networks as well. In order to optimize the selection of flows transmitted to the gateway, D-UFP takes into account possible dependencies between flows. We show that D-UFP is more difficult than NP-hard problems for which no good approximation is known. Then, we address two special cases of this problem: the case where all the sensors have a shared channel and the case where the sensors form a mesh and route to the gateway over a spanning tree.","lang":"eng"}],"extern":"1","user_id":"83983","citation":{"ieee":"R. Cohen, I. Nudelman, and G. Polevoy, “On the Admission of Dependent Flows in Powerful Sensor Networks,” Networking, IEEE/ACM Transactions on, vol. 21, no. 5, pp. 1461–1471, 2013.","short":"R. Cohen, I. Nudelman, G. Polevoy, Networking, IEEE/ACM Transactions On 21 (2013) 1461–1471.","bibtex":"@article{Cohen_Nudelman_Polevoy_2013, title={On the Admission of Dependent Flows in Powerful Sensor Networks}, volume={21}, DOI={10.1109/TNET.2012.2227792}, number={5}, journal={Networking, IEEE/ACM Transactions on}, author={Cohen, R. and Nudelman, I. and Polevoy, Gleb}, year={2013}, pages={1461–1471} }","mla":"Cohen, R., et al. “On the Admission of Dependent Flows in Powerful Sensor Networks.” Networking, IEEE/ACM Transactions On, vol. 21, no. 5, 2013, pp. 1461–71, doi:10.1109/TNET.2012.2227792.","chicago":"Cohen, R., I. Nudelman, and Gleb Polevoy. “On the Admission of Dependent Flows in Powerful Sensor Networks.” Networking, IEEE/ACM Transactions On 21, no. 5 (2013): 1461–71. https://doi.org/10.1109/TNET.2012.2227792.","apa":"Cohen, R., Nudelman, I., & Polevoy, G. (2013). On the Admission of Dependent Flows in Powerful Sensor Networks. Networking, IEEE/ACM Transactions On, 21(5), 1461–1471. https://doi.org/10.1109/TNET.2012.2227792","ama":"Cohen R, Nudelman I, Polevoy G. On the Admission of Dependent Flows in Powerful Sensor Networks. Networking, IEEE/ACM Transactions on. 2013;21(5):1461-1471. doi:10.1109/TNET.2012.2227792"},"year":"2013","type":"journal_article","page":"1461-1471","_id":"17663","intvolume":" 21","issue":"5"},{"_id":"46388","citation":{"mla":"Nallaperuma, Samadhi, et al. “A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem.” Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII, Association for Computing Machinery, 2013, pp. 147–160, doi:10.1145/2460239.2460253.","bibtex":"@inproceedings{Nallaperuma_Wagner_Neumann_Bischl_Mersmann_Trautmann_2013, place={New York, NY, USA}, series={FOGA XII ’13}, title={A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem}, DOI={10.1145/2460239.2460253}, booktitle={Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII}, publisher={Association for Computing Machinery}, author={Nallaperuma, Samadhi and Wagner, Markus and Neumann, Frank and Bischl, Bernd and Mersmann, Olaf and Trautmann, Heike}, year={2013}, pages={147–160}, collection={FOGA XII ’13} }","chicago":"Nallaperuma, Samadhi, Markus Wagner, Frank Neumann, Bernd Bischl, Olaf Mersmann, and Heike Trautmann. “A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem.” In Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII, 147–160. FOGA XII ’13. New York, NY, USA: Association for Computing Machinery, 2013. https://doi.org/10.1145/2460239.2460253.","ama":"Nallaperuma S, Wagner M, Neumann F, Bischl B, Mersmann O, Trautmann H. A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem. In: Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII. FOGA XII ’13. Association for Computing Machinery; 2013:147–160. doi:10.1145/2460239.2460253","apa":"Nallaperuma, S., Wagner, M., Neumann, F., Bischl, B., Mersmann, O., & Trautmann, H. (2013). A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem. Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII, 147–160. https://doi.org/10.1145/2460239.2460253","ieee":"S. Nallaperuma, M. Wagner, F. Neumann, B. Bischl, O. Mersmann, and H. Trautmann, “A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem,” in Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII, 2013, pp. 147–160, doi: 10.1145/2460239.2460253.","short":"S. Nallaperuma, M. Wagner, F. Neumann, B. Bischl, O. Mersmann, H. Trautmann, in: Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII, Association for Computing Machinery, New York, NY, USA, 2013, pp. 147–160."},"type":"conference","year":"2013","page":"147–160","abstract":[{"lang":"eng","text":"Understanding the behaviour of well-known algorithms for classical NP-hard optimisation problems is still a difficult task. With this paper, we contribute to this research direction and carry out a feature based comparison of local search and the well-known Christofides approximation algorithm for the Traveling Salesperson Problem. We use an evolutionary algorithm approach to construct easy and hard instances for the Christofides algorithm, where we measure hardness in terms of approximation ratio. Our results point out important features and lead to hard and easy instances for this famous algorithm. Furthermore, our cross-comparison gives new insights on the complementary benefits of the different approaches."}],"user_id":"15504","publisher":"Association for Computing Machinery","author":[{"first_name":"Samadhi","full_name":"Nallaperuma, Samadhi","last_name":"Nallaperuma"},{"full_name":"Wagner, Markus","first_name":"Markus","last_name":"Wagner"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"},{"full_name":"Bischl, Bernd","first_name":"Bernd","last_name":"Bischl"},{"last_name":"Mersmann","full_name":"Mersmann, Olaf","first_name":"Olaf"},{"orcid":"0000-0002-9788-8282","full_name":"Trautmann, Heike","first_name":"Heike","id":"100740","last_name":"Trautmann"}],"keyword":["approximation algorithms","local search","traveling salesperson problem","feature selection","prediction","classification"],"publication":"Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII","status":"public","date_created":"2023-08-04T15:42:03Z","date_updated":"2023-10-16T13:45:53Z","doi":"10.1145/2460239.2460253","series_title":"FOGA XII ’13","language":[{"iso":"eng"}],"place":"New York, NY, USA","title":"A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem","department":[{"_id":"34"},{"_id":"819"}],"publication_identifier":{"isbn":["9781450319904"]}}]