On the Complexity of Local Graph Transformations - Scheideler, Christian; Setzer, Alexander (Proceedings of the 46th International Colloquium on Automata, Languages, and Programming)
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.
Keywords: Graphs transformations; NP-hardness; approximation algorithms

Zeiteffiziente messtechnische Analyse glatt-nichtlinearen Schwingverhaltens dynamischer Strukturen - Sprock, Christian
Die Bestimmung des Frequenzübertragungsverhaltens von Strukturen mit nichtlinearer Charakteristik ist eine im technischen Bereich vielfach auftretende Aufgabe, z.B. für die genaue Bestimmung dynamischer Eigenschaften in der Entwurfsphase oder bei der Parametrierung von Modellen. Die typisch angewandten Verfahren zur Schwingungsmessung solcher Strukturen legen in der Regel ein lineares Strukturverhalten zu Grunde, oder sie erfordern einen hohen Zeit- und Messaufwand für die Abbildung des nichtlinearen Verhaltens; häufig in Verbindung mit einer starken Belastung der zu testenden Struktur. Die Bestimmung nichtlinearen Strukturverhaltens ist somit oft nicht effizient realisierbar. In der vorliegenden Arbeit wird ein neuer Ansatz zur Schwingungsanalyse nichtlinearer Strukturen mit von der Anregungsamplitude abhängigem Übertragungsverhalten vorgestellt. Dabei liegt ein Schwerpunkt auf der messtechnischen Bestimmung des nichtlinearen Verhaltens bei deutlich reduziertem Zeit- bzw. Messaufwand. Das Verfahren basiert auf einer Messmethode, die eine effiziente Bestimmung des nichtlinearen Kennfeldes der analysierten Struktur mit speziellen multiharmonischen Anregungssignalen ermöglicht. In Kombination mit einem fortschrittlichen Auswertealgorithmus kann eine vollständige Beschreibung des dynamischen Verhaltens in Form eines charakteristischen Diagramms generiert werden. Das Messverfahren wird durch eine Identifikationsroutine ergänzt, die die erforderliche Anzahl an Messungen nochmals reduzieren kann. Es ist als Mess-System auf Hard- und Software implementiert; der Funktionsnachweis erfolgt an verschiedenen Beispielen.
Keywords: Schwingungsanalyse; nichtlineare Strukturdynamik; Multisinus; Duffing-Schwinger; amplitudenabhängige Nichtlinearität; Peakbending; Backbone Curve; Schwingungsmessung; Frequenzverstimmung; Autoregression; Best Linear Approximation

Removing Undesirable Flows by Edge Deletion - Polevoy, Gleb; Trajanovski, Stojan; Grosso, Paola; de Laat, Cees (Combinatorial Optimization and Applications)
Consider mitigating the effects of denial of service or of malicious traffic in networks by deleting edges. Edge deletion reduces the DoS or the number of the malicious flows, but it also inadvertently removes some of the desired flows. To model this important problem, we formulate two problems: (1) remove all the undesirable flows while minimizing the damage to the desirable ones and (2) balance removing the undesirable flows and not removing too many of the desirable flows. We prove these problems are equivalent to important theoretical problems, thereby being important not only practically but also theoretically, and very hard to approximate in a general network. We employ reductions to nonetheless approximate the problem and also provide a greedy approximation. When the network is a tree, the problems are still MAX SNP-hard, but we provide a greedy-based 2l-approximation algorithm, where l is the longest desirable flow. We also provide an algorithm, approximating the first and the second problem within {\$}{\$}2 {\backslash}sqrt{\{} 2{\backslash}left| E {\backslash}right| {\}}{\$}{\$}and {\$}{\$}2 {\backslash}sqrt{\{}2 ({\backslash}left| E {\backslash}right| + {\backslash}left| {\backslash}text {\{}undesirable flows{\}} {\backslash}right| ){\}}{\$}{\$}, respectively, where E is the set of the edges of the network. We also provide a fixed-parameter tractable (FPT) algorithm. Finally, if the tree has a root such that every flow in the tree flows on the path from the root to a leaf, we solve the problem exactly using dynamic programming.
Keywords: flow; Red-Blue Set Cover; Positive-Negative Partial Set Cover; approximation; tree; MAX SNP-hard; root; leaf; dynamic programming; FPT

Filtering Undesirable Flows in Networks - Polevoy, Gleb; Trajanovski, Stojan; Grosso, Paola; de Laat, Cees (Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I)
Keywords: flow; filter; MMSA; set cover; approximation; local ratio algorithm

A Theoretical Analysis of the Fuzzy K-Means Problem - Blömer, Johannes; Brauer, Sascha; Bujna, Kathrin (2016 IEEE 16th International Conference on Data Mining (ICDM))
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.
Keywords: unsolvability by radicals; clustering; fuzzy k-means; probabilistic method; approximation algorithms; randomized algorithms

Inter-Datacenter Scheduling of Large Data Flows - Cohen, R.; Polevoy, Gleb (Cloud Computing, IEEE Transactions on)
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.
Keywords: Approximation algorithms; Approximation methods; Bandwidth; Cloud computing; Routing; Schedules; Scheduling

Hardness of approximation for quantum problems - Gharibian, Sevag; Kempe, Julia (Quantum Information & Computation)
The polynomial hierarchy plays a central role in classical complexity theory. Here, we define a quantum generalization of the polynomial hierarchy, and initiate its study. We show that not only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact hard to approximate. Using the same techniques, we also obtain hardness of approximation for the class QCMA. Our approach is based on the use of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomial hierarchy [Umans, FOCS 1999]. The problems for which we prove hardness of approximation for include, among others, a quantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian problem with hybrid classical-quantum ground states.
Keywords: Hardness of approximation; polynomial time hierarchy; succinct set cover; quantum complexity

On the Admission of Dependent Flows in Powerful Sensor Networks - Cohen, R.; Nudelman, I.; Polevoy, Gleb (Networking, IEEE/ACM Transactions on)
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.
Keywords: Approximation algorithms; Approximation methods; Bandwidth; Logic gates; Radar; Vectors; Wireless sensor networks; Dependent flow scheduling; sensor networks

A Feature-Based Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson Problem - Nallaperuma, Samadhi; Wagner, Markus; Neumann, Frank; Bischl, Bernd; Mersmann, Olaf; Trautmann, Heike (Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII)
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.
Keywords: approximation algorithms; local search; traveling salesperson problem; feature selection; prediction; classification

Clustering for Metric and Nonmetric Distance Measures - Ackermann, Marcel R.; Blömer, Johannes; Sohler, Christian (ACM Trans. Algorithms)
Keywords: k-means clustering; k-median clustering; Approximation algorithm; Bregman divergences; Itakura-Saito divergence; Kullback-Leibler divergence; Mahalanobis distance; random sampling