@inproceedings{10586, abstract = {{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.}}, author = {{Scheideler, Christian and Setzer, Alexander}}, booktitle = {{Proceedings of the 46th International Colloquium on Automata, Languages, and Programming}}, keywords = {{Graphs transformations, NP-hardness, approximation algorithms}}, location = {{Patras, Greece}}, pages = {{150:1----150:14}}, publisher = {{Dagstuhl Publishing}}, title = {{{On the Complexity of Local Graph Transformations}}}, doi = {{10.4230/LIPICS.ICALP.2019.150}}, volume = {{132}}, year = {{2019}}, } @inproceedings{2367, abstract = {{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.}}, author = {{Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}}, booktitle = {{2016 IEEE 16th International Conference on Data Mining (ICDM)}}, isbn = {{9781509054732}}, keywords = {{unsolvability by radicals, clustering, fuzzy k-means, probabilistic method, approximation algorithms, randomized algorithms}}, location = {{Barcelona, Spain}}, pages = {{805--810}}, publisher = {{IEEE}}, title = {{{A Theoretical Analysis of the Fuzzy K-Means Problem}}}, doi = {{10.1109/icdm.2016.0094}}, year = {{2016}}, } @article{17657, abstract = {{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.}}, author = {{Cohen, R. and Polevoy, Gleb}}, issn = {{2168-7161}}, journal = {{Cloud Computing, IEEE Transactions on}}, keywords = {{Approximation algorithms, Approximation methods, Bandwidth, Cloud computing, Routing, Schedules, Scheduling}}, number = {{99}}, pages = {{1--1}}, title = {{{Inter-Datacenter Scheduling of Large Data Flows}}}, doi = {{10.1109/TCC.2015.2487964}}, volume = {{PP}}, year = {{2015}}, } @article{17663, abstract = {{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.}}, author = {{Cohen, R. and Nudelman, I. and Polevoy, Gleb}}, issn = {{1063-6692}}, journal = {{Networking, IEEE/ACM Transactions on}}, keywords = {{Approximation algorithms, Approximation methods, Bandwidth, Logic gates, Radar, Vectors, Wireless sensor networks, Dependent flow scheduling, sensor networks}}, number = {{5}}, pages = {{1461--1471}}, title = {{{On the Admission of Dependent Flows in Powerful Sensor Networks}}}, doi = {{10.1109/TNET.2012.2227792}}, volume = {{21}}, year = {{2013}}, } @inproceedings{46388, abstract = {{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.}}, author = {{Nallaperuma, Samadhi and Wagner, Markus and Neumann, Frank and Bischl, Bernd and Mersmann, Olaf and Trautmann, Heike}}, booktitle = {{Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII}}, isbn = {{9781450319904}}, keywords = {{approximation algorithms, local search, traveling salesperson problem, feature selection, prediction, classification}}, pages = {{147–160}}, publisher = {{Association for Computing Machinery}}, title = {{{A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem}}}, doi = {{10.1145/2460239.2460253}}, year = {{2013}}, }