In this thesis, we develop tractable relaxations and efficient algorithms for large-scale optimization. Our developments are motivated by a recent paradigm, Compressed Sensing (CS), which consists of acquiring directly low-dimensional linear projections of signals, possibly corrupted with noise, and then using sophisticated recovery procedures for signal reconstruction. We start by analyzing how to utilize a priori information given in the form of sign restrictions on part of the entries. We propose necessary and sufficient on the sensing matrix for exact recovery of sparse signals, utilize them in deriving error bounds under imperfect conditions, suggest verifiable sufficient conditions and establish their limits of performance. In the second part of this thesis, we study the CS synthesis problem -selecting the minimum number of rows from a given matrix, so that the resulting submatrix possesses certifiably good recovery properties. We express the synthesis problem as the problem of approximating a given matrix by a matrix of specified low rank in the uniform norm and develop a randomized algorithm for this problem. The third part is dedicated to efficient First-Order Methods (FOMs) for large-scale, well-structured convex optimization problems. We propose FOMs with stochastic oracles that come with exact guarantees on solution quality, achieve sublinear time behavior, and through extensive simulations, show considerable improvement over the state-of-the-art deterministic FOMs. In the last part, we examine a general sparse estimation problem -estimating a block sparse linear transform of a signal from the undersampled observations of the signal corrupted with nuisance and stochastic noise. We show that an extension of the earlier results to this more general framework is possible. In particular, we suggest estimators that have efficiently verifiable guaranties of performance and provide connections to well-known results in CS theory.

L’importance des problèmes CSP, WCSP et #CSP est reflétée par la part considérable des travaux, théoriques et pratiques, dont ils font l’objet en intelligence artificielle et bien au-delà. Leur difficulté est telle qu’ils appartiennent respectivement aux classes NP-complet, NP-difficile et #P-complet. Aussi, les méthodes qui permettent de résoudre efficacement leurs instances ont une complexité en temps exponentielle. Les travaux de recherche de cette thèse se focalisent sur les méthodes de résolution exploitant la notion de décomposition arborescente. Ces méthodes ont suscité un vif intérêt de la part de la communauté scientifique du fait qu’elles soient capables de résoudre en temps polynomial certaines classes d’instances. Cependant, en pratique, elles n’ont pas encore montré toute leur efficacité vu la qualité de la décomposition employée ne prenant en compte qu’un critère purement structurel, sa largeur. Premièrement, nous proposons un nouveau cadre général de calcul de décompositions qui a la vertu de calculer des décompositions qui capturent des paramètres plus pertinents à l’égard de la résolution que la seule largeur de la décomposition. Ensuite, nous proposons une exploitation dynamique de la décomposition pendant la résolution pour les problèmes (W)CSP. Le changement de la décomposition pendant la résolution vise à adapter la décomposition selon la nature de l’instance. Finalement, nous proposons un nouvel algorithme de comptage qui exploite la décomposition d’une façon différente de celle des méthodes standards afin d’éviter des calculs inutiles.L’ensemble des contributions ont été évaluées et validées expérimentalement. / The importance of CSP, WCSP and #CSP problems is reflected by the considerableamount of theoretical and practical work of which they are subject in artificial intelligenceand far beyond. Their difficulty is such that they belong respectively to the NP-complete,NP-hard and #P-complete classes. Hence, the methods that are able to solve efficientlytheir instances have a complexity in exponential time. The research works of this thesisfocus on the solving methods exploiting the notion of tree-decomposition. These methodshave aroused a keen interest from the scientific community because they are able to solvesome classes of instances in polynomial time. Nevertheless, in practice, they have notshown yet their full efficiency given the quality of the used decomposition that takes onlyinto account a purely structural criterion, its width. First, we propose a new generic framework for computing decompositions which has the virtue of computing decompositionsthat capture more relevant parameters in the context of solving than the width. Then,we propose a dynamic exploitation of the decomposition during the solving for (W)CSPproblems. The modification of the decomposition during the solving aims to adapt the decomposition to the nature of the instance. Finally, we propose a new counting algorithmthat exploits the decomposition in a different way than standard methods in order toavoid unnecessary computations. All the contributions have been evaluated and validatedexperimentally.

Le problème de satisfaction de contraintes (CSP) est un problème NP-complet classique en intelligence artificielle qui a suscité un engouement important de la communauté scientifique grâce à la richesse de ses aspects pratiques et théoriques. Cependant, au fil des années un gouffre s'est creusé entre les praticiens, qui développent des méthodes exponentielles mais efficaces pour résoudre des instances industrielles, et les théoriciens qui conçoivent des algorithmes sophistiqués pour résoudre en temps polynomial certaines restrictions de CSP dont l'intérêt pratique n'est pas avéré. Dans cette thèse nous tentons de réconcilier les deux communautés en fournissant des méthodes polynomiales pour tester automatiquement l'appartenance d'une instance de CSP à une sélection de classes traitables majeures. Anticipant la possibilité que les instances réelles ne tombent que rarement dans ces classes traitables, nous analysons également de manière systématique la possibilité de décomposer efficacement une instance en sous-problèmes traitables en utilisant des méthodes de complexité paramétrée. Finalement, nous introduisons un cadre général pour exploiter dans les CSP les idées développées pour la kernelization, un concept fondamental de complexité paramétrée jusqu'ici peu utilisé en pratique. Ce dernier point est appuyé par des expérimentations prometteuses. / The Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the past decades due to its practical usefulness and the deep theoretical questions it relates to. However, there is a wide gap between practitioners, who develop solving techniques that are efficient for industrial instances but exponential in the worst case, and theorists who design sophisticated polynomial-time algorithms for restrictions of CSP defined by certain algebraic properties. In this thesis we attempt to bridge this gap by providing polynomial-time algorithms to test for membership in a selection of major tractable classes. Even if the instance does not belong to one of these classes, we investigate the possibility of decomposing efficiently a CSP instance into tractable subproblems through the lens of parameterized complexity. Finally, we propose a general framework to adapt the concept of kernelization, central to parameterized complexity but hitherto rarely used in practice, to the context of constraint reasoning. Preliminary experiments on this last contribution show promising results.

The classical graph edge coloring problem deals in coloring the edges of a given graph with minimum number of colors such that no two adjacent edges in the graph, get the same color in the proposed coloring. In the following work, we look at the other end of the spectrum where in our goal is to maximize the number of colors used for coloring the edges of the graph under some vertex specific constraints. We deal with the MAXIMUM EDGE COLORING problem which is defined as the following –For an integer q ≥2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. The question is very well motivated by the problem of channel assignment in wireless networks. This problem is NP-hard for q ≥ 2, and has been well-studied from the point of view of approximation. This problem has not been studied in the parameterized context before. Hence as a next step, this thesis investigates the parameterized complexity of this problem where the standard parameter is the solution size. The main focus of the work is the special case of q=2 ,i.e. MAXIMUM EDGE 2-COLORING which is theoretically intricate and practically relevant in the wireless networks setting. We first show an exponential kernel for the MAXIMUM EDGE q-COLORING problem where q is a fixed constant and q ≥ 2.We do a more specific analysis for the kernel of the MAXIMUM EDGE 2-COLORING problem. The kernel obtained here is still exponential in size but is better than the kernel obtained for MAXIMUM EDGE q-COLORING problem in case of q=2. We then show a fixed parameter tractable algorithm for the MAXIMUM EDGE 2-COLORING problem with a running time of O*∗(kO(k)).We also show a fixed parameter tractable algorithm for the MAXIMUM EDGE q-COLORING problem with a running time of O∗(kO(qk) qO(k)). The fixed parameter tractability of the dual parametrization of the MAXIMUM EDGE 2-COLORING problem is established by arguing a linear vertex kernel for the problem. We also show that the MAXIMUM EDGE 2-COLORING problem remains hard on graphs where the maximum degree is a constant and also on graphs without cycles of length four. In both these cases, we obtain quadratic kernels. A closely related variant of the problem is the question of MAX EDGE{1,2-}COLORING. For this problem, the vertices in the input graph may have different qε,{1.2} values and the goal is to use at least k colors for the edge coloring of the graph such that every vertex sees at most q colors, where q is either one or two. We show that the MAX EDGE{1,2}-COLORING problem is W[1]-hard on graphs that have no cycles of length four.

Aus der Einleitung: 'Conceptual graphs (CGs) are an expressive formalism for representing knowledge about an application domain in a graphical way. Since CGs can express all of first-order predicate logic (FO), they can also be seen as a graphical notation for FO formulae. In knowledge representation, one is usually not only interested in representing knowledge, one also wants to reason about the represented knowledge. For CGs, one is, for example, interested in validity of a given graph, and in the question whether one graph subsumes another one. Because of the expressiveness of the CG formalism, these reasoning problems are undecidable for general CGs. In the literature [Sow84, Wer95, KS97] one can find complete calculi for validity of CGs, but implementations of these calculi have the same problems as theorem provers for FO: they may not terminate for formulae that are not valid, and they are very ineficient. To overcome this problem, one can either employ incomplete reasoners, or try to find decidable (or even tractable) fragments of the formalism. This paper investigates the second alternative. The most prominent decidable fragment of CGs is the class of simple conceptual graphs (SGs), which corresponds to the conjunctive, positive, and existential fragment of FO (i.e., existentially quantified conjunctions of atoms). Even for this simple fragment, however, subsumption is still an NP-complete problem [CM92]. SGs that are trees provide for a tractable fragment of SGs, i.e., a class of simple conceptual graphs for which subsumption can be decided in polynomial time [MC93]. In this report, we will identify a tractable fragment of SGs that is larger than the class of trees. Instead of trying to prove new decidability or tractability results for CGs from scratch, our idea was to transfer decidability results from description logics [DLNN97, DLNS96] to CGs. The goal was to obtain a \natural' sub-class of the class of all CGs in the sense that, on the one hand, this sub-class is defined directly by syntactic restrictions on the graphs, and not by conditions on the first-order formulae obtained by translating CGs into FO, and, on the other hand, is in some sense equivalent to a more or less expressive description logic. Although description logics (DLs) and CGs are employed in very similar applications (e.g., for representing the semantics of natural language sentences), it turned out that these two formalisms are quite different for several reasons: (1) conceptual graphs are interpreted as closed FO formulae, whereas DL concept descriptions are interpreted by formulae with one free variable; (2) DLs do not allow for relations of arity > 2 ; (3) SGs are interpreted by existential sentences, whereas almost all DLs considered in the literature allow for universal quantification; (4) because DLs use a variable-free syntax, certain identifications of variables expressed by cycles in SGs and by co-reference links in CGs cannot be expressed in DLs. As a consequence of these differences, we could not identify a natural fragment of CGs corresponding to an expressive DL whose decidability was already shown in the literature. We could, however, obtain a new tractability result for a DL corresponding to SGs that are trees. This correspondence result strictly extends the one in [CF98]. In addition, we have extended the tractability result from SGs that are trees to SGs that can be transformed into trees using a certain \cycle-cutting' operation. The report is structured as follows. We first introduce the description logic for which we will identify a subclass of equivalent SGs. In Section 3, we recall basic definitions and results on SGs. Thereafter, we introduce a syntactical variant of SGs which allows for directly encoding the support into the graphs (Section 4.1). In order to formalize the equivalence between DLs and SGs, we have to consider SGs with one distinguished node called root (Section 4.2). In Section 5, we finally identify a class of SGs corresponding to a DL that is a strict extension of the DL considered in [CF98].

Description Logics (DLs) belong to a successful family of knowledge representation formalisms with two key assets: formally well-defined semantics which allows to represent knowledge in an unambiguous way and automated reasoning which allows to infer implicit knowledge from the one given explicitly. This thesis investigates various reasoning techniques for tractable DLs in the EL family which have been implemented in the CEL system. It suggests that the use of the lightweight DLs, in which reasoning is tractable, is beneficial for ontology design and maintenance both in terms of expressivity and scalability. The claim is supported by a case study on the renown medical ontology SNOMED CT and extensive empirical evaluation on several large-scale biomedical ontologies.

Given a set of n points P ⊂ R2, the Delaunay graph of P for a family of geometric objects C is a graph defined as follows: the vertex set is P and two points p, p' ∈ P are connected by an edge if and only if there exists some C ∈ C containing p, p' but no other point of P. Delaunay graph of circle is often called as Delaunay triangulation as each of its inner face is a triangle if no three points are co-linear and no four points are co-circular. The dual of the Delaunay triangulation is the Voronoi diagram, which is a well studied structure. The study of graph theoretic properties on Delaunay graphs was motivated by its application to wireless sensor networks, meshing, computer vision, computer graphics, computational geometry, height interpolation, etc. The problem of finding an optimal vertex cover on a graph is a classical NP-hard problem. In this thesis we focus on the vertex cover problem on Delaunay graphs for geometric objects like axis-parallel slabs and circles(Delaunay triangulation). 1. We consider the vertex cover problem on Delaunay graph of axis-parallel slabs. It turns out that the Delaunay graph of axis-parallel slabs has a very special property — its edge set is the union of two Hamiltonian paths. Thus, our problem reduces to solving vertex cover on the class of graphs whose edge set is simply the union of two Hamiltonian Paths. We refer to such a graph as a braid graph. Despite the appealing structure, we show that deciding k-vertex cover on braid graphs is NP-complete. This involves a rather intricate reduction from the problem of finding a vertex cover on 2-connected cubic planar graphs. 2. Having established the NP-hardness of the vertex cover problem on braid graphs, we pursue the question of improved fixed parameter algorithms on braid graphs. The best-known algorithm for vertex cover on general graphs has a running time of O(1.2738k + kn) [CKX10]. We propose a branching based fixed parameter tractable algorithm with running time O⋆(1.2637k) for graphs with maximum degree bounded by four. This improves the best known algorithm for this class, which surprisingly has been no better than the algorithm for general graphs. Note that this implies faster algorithms for the class of braid graphs (since they have maximum degree at most four). 3. A triangulation is a 2-connected plane graph in which all the faces except possibly the outer face are triangles, we often refer to such graphs as triangulated graphs. A chordless-NST is a triangulation that does not have chords or separating triangles (non-facial triangles). We focus on the computational problem of optimal vertex covers on triangulations, specifically chordless-NST. We call a triangulation Delaunay realizable if it is combinatorially equivalent to some Delaunay triangulation. Characterizations of Delaunay triangulations have been well studied in graph theory. Dillencourt and Smith [DS96] showed that chordless-NSTs are Delaunay realizable. We show that for chordless-NST, deciding the vertex cover problem is NP-complete. We prove this by giving a reduction from vertex cover on 3-connected, triangle free planar graph to an instance of vertex cover on a chordless-NST. 4. If the outer face of a triangulation is also a triangle, then it is called a maximal planar graph. We prove that the vertex cover problem is NP-complete on maximal planar graphs by reducing an instance of vertex cover on a triangulated graph to an instance of vertex cover on a maximal planar graph.

Description Logics (DLs) belong to a successful family of knowledge representation formalisms with two key assets: formally well-defined semantics which allows to represent knowledge in an unambiguous way and automated reasoning which allows to infer implicit knowledge from the one given explicitly. This thesis investigates various reasoning techniques for tractable DLs in the EL family which have been implemented in the CEL system. It suggests that the use of the lightweight DLs, in which reasoning is tractable, is beneficial for ontology design and maintenance both in terms of expressivity and scalability. The claim is supported by a case study on the renown medical ontology SNOMED CT and extensive empirical evaluation on several large-scale biomedical ontologies.