No description available.

De nombreux problèmes de la vie réelle sont NP-Difficiles et ne peuvent pas être résolus en temps polynomial. Deux paradigmes notables pour les résoudre quand même sont: l'approximation et la complexité paramétrée. Dans cette thèse, on présente une nouvelle technique appelée "gloutonnerie-Pour-La-Paramétrisation". On l'utilise pour établir ou améliorer la complexité paramétrée de nombreux problèmes et également pour obtenir des algorithmes paramétrés pour des problèmes à cardinalité contrainte sur les graphes bipartis. En vue d'établir des résultats négatifs sur l'approximabilité en temps sous-Exponentiel et en temps paramétré, on introduit différentes méthodes de sparsification d'instances préservant l'approximation. On combine ces "sparsifieurs" à des réductions nouvelles ou déjà connues pour parvenir à nos fins. En guise de digestif, on présente des résultats de complexité de jeux comme le Bridge et Havannah. / Several real-Life problems are NP-Hard and cannot be solved in polynomial time.The two main options to overcome this issue are: approximation and parameterized complexity. In this thesis, we present a new technique called greediness-For-Parameterization and we use it to improve the parameterized complexity of many problems. We also use this notion to obtain parameterized algorithms for some problems in bipartite graphs. Aiming at establishing negative results on the approximability in subexponential time and in parameterized time, we introduce new methods of sparsification that preserves approximation. We combine those "sparsifiers" with known or new reductions to achieve our goal. Finally, we present some hardness results of games such as Bridge and Havannah.

Analysis of large network datasets has become increasingly important. Algorithms have been designed to find many kinds of structure, with numerous applications across the social and biological sciences. However, a tradeoff is always present between accuracy and scalability; otherwise promising techniques can be computationally infeasible when applied to networks with huge numbers of nodes and edges. One way of extending the reach of network analysis is to sparsify the graph by retaining only a subset of its edges. The reduced network could prove much more tractable. For this thesis, I propose a new sparsification algorithm that preserves the properties of a random walk on the network. Specifically, the algorithm finds a subset of edges that best preserves the stationary distribution of a random walk by minimizing the Kullback-Leibler divergence between a walk on the original and sparsified graphs. A highly efficient greedy search strategy is developed to optimize this objective. Experimental results are presented that test the performance of the algorithm on the influence maximization task. These results demonstrate that sparsification allows near-optimal solutions to be found in a small fraction of the runtime that would required using the full network. Two cases are shown where sparsification allows an influence maximization algorithm to be applied to a dataset that previous work had considered intractable.

Recently dominant sets, a generalization of the notion of the maximal clique to edge-weighted graphs, have proven to be an effective tool for unsupervised learning and have found applications in different domains. Although, they were initially established using optimization and graph theory concepts, recent work has shown fascinating connections with evolutionary game theory, that leads to the clustering game framework. However, considering size of today's data sets, existing methods need to be modified in order to handle massive data. Hence, in this research work, first we address the limitations of the clustering game framework for large data sets theoretically. We propose a new important question for the clustering community ``How can a cluster of a subset of a dataset be a cluster of the entire dataset?''. We show that, this problem is a coNP-hard problem in a clustering game framework. Thus, we modify the definition of a cluster from a stable concept to a non-stable but optimal one (Nash equilibrium). By experiments we show that this relaxation does not change the qualities of the clusters practically. Following this alteration and the fact that equilibriums are generally compact subsets of vertices, we design an effective strategy to find equilibriums representing well distributed clusters. After finding such equilibriums, a linear game theoretic relation is proposed to assign vertices to the clusters and partition the graph. However, the method inherits a space complexity issue, that is the similarities between every pair of objects are required which proves practically intractable for large data sets. To overcome this limitation, after establishing necessary theoretical tools for a special type of graphs that we call vertex-repeated graphs, we propose the scalable clustering game framework. This approach divides a data set into disjoint tractable size chunks. Then, the exact clusters of the entire data are approximated by the clusters of the chunks. In fact, the exact equilibriums of the entire graph is approximated by the equilibriums of the subsets of the graph. We show theorems that enable significantly improved time complexity for the model. The applications include, but are not limited to, the maximum weight clique problem, large data clustering and image segmentation. Experiments have been done on random graphs and the DIMACS benchmark for the maximum weight clique problem and on magnetic resonance images (MRI) of the human brain consisting of about 4 million examples for large data clustering. Also, on the Berkeley Segmentation Dataset, the proposed method achieves results comparable to the state of the art, providing a parallel framework for image segmentation and without any training phase. The results show the effectiveness and efficiency of our approach. In another part of this research work, we generalize the clustering game method to cluster uncertain data where the similarities between the data points are not exactly known, that leads to the uncertain clustering game framework. Here, contrary to the ensemble clustering approaches, where the results of different similarity matrices are combined, we focus on the average utilities of an uncertain game. We show that the game theoretical solutions provide stable clusters even in the presence of severe uncertainties. In addition, based on this framework, we propose a novel concept in uncertain data clustering so that every subset of objects can have a ''cluster degree''. Extensive experiments on real world data sets, as well as on the Berkeley image segmentation dataset, confirm the performance of the proposed method. And finally, instead of dividing a graph into chunks to make the clustering scalable, we study the effect of the spectral sparsification method based on sampling by effective resistance on the clustering outputs. Through experimental and theoretical observations, we show that the clustering results obtained from sparsified graphs are very similar to the results of the original non-sparsified graphs. The rand index is always at about 0.9 to 0.99 in our experiments even when lots of sparsification is done.

No description available.

Background: RNA secondary structure prediction by energy minimization is the central computational tool for the analysis of structural non-coding RNAs and their interactions. Sparsification has been successfully applied to improve the time efficiency of various structure prediction algorithms while guaranteeing the same result; however, for many such folding problems, space efficiency is of even greater concern, particularly for long RNA sequences. So far, spaceefficient sparsified RNA folding with fold reconstruction was solved only for simple base-pair-based pseudo-energy models. Results: Here, we revisit the problem of space-efficient free energy minimization. Whereas the space-efficient minimization of the free energy has been sketched before, the reconstruction of the optimum structure has not even been discussed. We show that this reconstruction is not possible in trivial extension of the method for simple energy models. Then, we present the time- and space-efficient sparsified free energy minimization algorithm SparseMFEFold that guarantees MFE structure prediction. In particular, this novel algorithm provides efficient fold reconstruction based on dynamically garbage-collected trace arrows. The complexity of our algorithm depends on two parameters, the number of candidates Z and the number of trace arrows T; both are bounded by n2, but are typically much smaller. The time complexity of RNA folding is reduced from O(n3) to O(n2 + nZ); the space complexity, from O(n2) to O(n + T + Z). Our empirical results show more than 80 % space savings over RNAfold [Vienna RNA package] on the long RNAs from the RNA STRAND database (≥2500 bases). Conclusions: The presented technique is intentionally generalizable to complex prediction algorithms; due to their high space demands, algorithms like pseudoknot prediction and RNA–RNA-interaction prediction are expected to profit even stronger than \"standard\" MFE folding. SparseMFEFold is free software, available at http://www.bioinf.unileipzig. de/~will/Software/SparseMFEFold.

Graph algorithms are concerned with the algorithmic aspects of solving graph problems. The problems are motivated from and have application to diverse areas of computer science, engineering and other disciplines. Problems arising from these areas of application are good candidates for parallelization since they often have both intense computational needs and stringent response time requirements. Motivated by these concerns, this thesis investigates parallel algorithms for these kinds of graph problems that have at least one of the following properties: the problems involve some type of dynamic updates; the sparsification technique is applicable; or the problems are closely related to communications network issues. The models of parallel computation used in our studies are the Parallel Random Access Machine (PRAM) model and the practical interconnection network models such as meshes and hypercubes. ¶ Consider a communications network which can be represented by a graph G = (V;E), where V is a set of sites (processors), and E is a set of links which are used to connect the sites (processors). In some cases, we also assign weights and/or directions to the edges in E. Associated with this network, there are many problems such as (i) whether the network is k-edge (k-vertex) connected withfixed k; (ii) whether there are k-edge (k-vertex) disjoint paths between u and v for a pair of given vertices u and v after the network is dynamically updated by adding and/or deleting an edge etc; (iii) whether the sites in the network can communicate with each other when some sites and links fail; (iv) identifying the first k edges in the network whose deletion will result in the maximum increase in the routing cost in the resulting network for fixed k; (v) how to augment the network at optimal cost with a given feasible set of weighted edges such that the augmented network is k-edge (k-vertex) connected; (vi) how to route messages through the network efficiently. In this thesis we answer the problems mentioned above by presenting efficient parallel algorithms to solve them. As far as we know, most of the proposed algorithms are the first ones in the parallel setting. ¶ Even though most of the problems concerned in this thesis are related to communications networks, we also study the classic edge-coloring problem. The outstanding difficulty to solve this problem in parallel is that we do not yet know whether or not it is in NC. In this thesis we present an improved parallel algorithm for the problem which needs [bigcircle]([bigtriangleup][superscript 4.5]log [superscript 3] [bigtriangleup] log n + [bigtriangleup][superscript 4] log [superscript 4] n) time using [bigcircle](n[superscript 2][bigtriangleup] + n[bigtriangleup][superscript 3]) processors, where n is the number of vertices and [bigtriangleup] is the maximum vertex degree. Compared with a previously known result on the same model, we improved by an [bigcircle]([bigtriangleup][superscript 1.5]) factor in time. The non-trivial part is to reduce this problem to the edge-coloring update problem. We also generalize this problem to the approximate edge-coloring problem by giving a faster parallel algorithm for the latter case. ¶ Throughout the design and analysis of parallel graph algorithms, we also find a technique called the sparsification technique is very powerful in the design of efficient sequential and parallel algorithms on dense undirected graphs. We believe that this technique may be useful in its own right for guiding the design of efficient sequential and parallel algorithms for problems in other areas as well as in graph theory.

No description available.

Diese Arbeit nutzt und verfeinert Methoden der Komplexitätstheorie, um mit diesen die Komplexität dünner Instanzen zu untersuchen. Dazu gehören etwa Graphen mit wenigen Kanten oder Formeln mit wenigen Bedingungen beschränkter Weite. Dabei ergeben sich zwei natürliche Fragestellungen: (a) Gibt es einen effizienten Algorithmus, der beliebige Instanzen eines NP-schweren Problems auf äquivalente, dünne Instanzen reduziert? (b) Gibt es einen Algorithmus, der dünne Instanzen NP-schwerer Probleme bedeutend schneller löst als allgemeine Instanzen gelöst werden können? Wir formalisieren diese Fragen für verschiedene Probleme und zeigen, dass positive Antworten jeweils zu komplexitätstheoretischen Konsequenzen führen, die als unwahrscheinlich gelten. Frage (a) wird als Kommunikation modelliert, in der zwei Akteure kooperativ eine NP-schwere Sprache entscheiden möchten und dabei möglichst wenig kommunizieren. Unter der komplexitätstheoretischen Annahme, dass coNP keine Teilmenge von NP/poly ist, erhalten wir aus unseren Ergebnissen erstaunlich scharfe untere Schranken für interessante Parameter aus verschiedenen Teilgebieten der theoretischen Informatik. Im Speziellen betrifft das die Ausdünnung von Formeln, die Kernelisierung aus der parameterisierten Komplexitätstheorie, die verlustbehaftete Kompression von Entscheidungsproblemen, und die Theorie der probabilistisch verifizierbaren Beweise. Wir untersuchen Fragestellung (b) anhand der Exponentialzeitkomplexität von Zählproblemen. Unter (Varianten) der bekannten Exponentialzeithypothese (ETH) erhalten wir exponentielle untere Schranken für wichtige #P-schwere Probleme: das Berechnen der Zahl der erfüllenden Belegungen einer 2-KNF Formel, das Berechnen der Zahl aller unabhängigen Mengen in einem Graphen, das Berechnen der Permanente einer Matrix mit Einträgen 0 und 1, das Auswerten des Tuttepolynoms an festen Punkten. / In this thesis, we use and refine methods of computational complexity theory to analyze the complexity of sparse instances, such as graphs with few edges or formulas with few constraints of bounded width. Two natural questions arise in this context: (a) Is there an efficient algorithm that reduces arbitrary instances of an NP-hard problem to equivalent, sparse instances? (b) Is there an algorithm that solves sparse instances of an NP-hard problem significantly faster than general instances can be solved? We formalize these questions for different problems and show that positive answers for these formalizations would lead to consequences in complexity theory that are considered unlikely. Question (a) is modeled by a communication process, in which two players want to cooperatively decide an NP-hard language and at the same time communicate as few as possible. Under the complexity-theoretic hypothesis that coNP is not in NP/poly, our results imply surprisingly tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. We study the question (b) for counting problems in the exponential time setting. Assuming (variants of) the exponential time hypothesis (ETH), we obtain asymptotically tight, exponential lower bounds for well-studied #P-hard problems: Computing the number of satisfying assignments of a 2-CNF formula, computing the number of all independent sets in a graph, computing the permanent of a matrix with entries 0 and 1, evaluating the Tutte polynomial at fixed evaluation points.

[pt] Nesta dissertação, diversos algoritmos adaptativos para processamento de sinais com seleção de dados são desenvolvidos e estudados, com o objetivo de resolver dois problemas diferentes. O primeiro problema envolve ambientes com sistemas esparsos, onde uma função penalidade é incorporada na função de custo para aproveitar a esparsidade do modelo. Nesta perspectiva, são propostos três algoritmos com função penalidade ajustável, o primeiro baseado na função penalidade l1 é denominado SM-NLMS com atração para zero e função penalidade ajustável (ZA-SM-NLMS-ADP). O segundo algoritmo está baseado na função penalidade log-sum e o terceiro na função penalidade l0 , denominados SM-NLMS com atração ponderada para zero e função de penalidade ajustável (RZA-SM-NLMS-ADP) e SM-NLMS com atração para zero exponencial e função de penalidade ajustável (EZA-SM-NLMSADP), respectivamente. Além disso, foi desenvolvida uma análise estatística do algoritmo SM-NLMS com uma função penalidade genérica, obtendo expressões matemáticas para o erro médio quadrático em estado estacionário. O segundo problema abordado, considera algoritmos adaptativos não lineares baseados em funções de kernels. Neste contexto, são desenvolvidos dois algoritmos com seleção de dados, o algoritmo SM-NKLMS e o algoritmo SM-KAP, os quais possuem a capacidade de limitar o crescimento da estrutura criada pelas funções de kernels, tratando um dos maiores problemas que surge quando se utilizam algoritmos baseados em kernels. Os algoritmos baseados em kernels foram testados para predição de séries temporais. Também é realizada uma análise estatística do algoritmo SM-NKLMS. As simulações mostram que os algoritmos desenvolvidos superam os algoritmos lineares e não lineares convencionais tanto na velocidade de convergência quanto no erro médio quadrático atingido. / [en] In this dissertation, several data-selective adaptive signal processing algorithms are derived and investigated for solving two different problems. The first one involves scenarios handling sparse systems, where we introduce a framework in which a general penalty function is incorporated into the cost function for exploiting the sparsity of the model. Under this scope, we propose three algorithms with an adjustable penalty function, the first one based on the l1 - norm, which we term zero-attracting SM-NLMS with adjustable penalty function (ZA-SM-NLMS-ADP). The second algorithm is based on the log-sum penalty function and the third one on the l0 - norm, named reweighted ZASM- NLMS (RZA-SM-NLMS-ADP) and the exponential ZA-SM-NLMS (EZASM- NLMS-ADP), respectively. We also carry out a statistical analysis of the sparsity-aware SM-NLMS algorithms with a general penalty function, arriving at mathematical expressions for the mean-square error at steady state. The second problem addressed considers nonlinear adaptive algorithms based on kernel functions. In this context, we develop two data selective algorithms, the Set-Membership Normalized Kernel Least Mean Squares (SM-NKLMS) algorithm and the Set-Membership Kernel Affine Projection (SM-KAP) algorithm, which have the capability of naturally limiting the growing structure created by the kernels, dealing with one of the major problems presented when working with kernel algorithms. The kernel algorithms developed have been tested for a time series prediction task. A statistical analysis of the proposed SM-NKLMS algorithm is also developed. Simulation results show that the proposed algorithms, outperform standard linear and nonlinear adaptive algorithms in both convergence rate and steady state performance.