**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Publication# New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Résumé

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most sophisticated tasks involving decision making, can be reduced to solving certain optimization problems. These advances however, bring several new challenges to the field of algorithm design. The first of them is related to the ever-growing size of instances, these optimization problems need to be solved for. In practice, this forces the algorithms for these problems to run in time linear or nearly linear in their input size. The second challenge is related to the emergence of new, harder and harder problems which need to be dealt with. These problems are in most cases considered computationally intractable because of complexity barriers such as NP completeness, or because of non-convexity. Therefore, efficiently computable relaxations for these problems are typically desired.

The material of this thesis is divided into two parts. In the first part we attempt to address the first challenge. The recent tremendous progress in developing fast algorithm for such fundamental problems as maximum flow or linear programming, demonstrate the power of continuous techniques and tools such as electrical flows, fast Laplacian solvers and interior point methods. In this thesis we study new algorithms of this type based on continuous dynamical systems inspired by the study of a slime mold Physarum polycephalum. We perform a rigorous mathematical analysis of these dynamical systems and extract from them new, fast algorithms for problems such as minimum cost flow, linear programming and basis pursuit.

In the second part of the thesis we develop new tools to approach the second challenge. Towards this, we study a very general form of discrete optimization problems and its extension to sampling and counting, capturing a host of important problems such as counting matchings in graphs, computing permanents of matrices or sampling from constrained determinantal point processes. We present a very general framework, based on polynomials, for dealing with these problems computationally. It is based, roughly, on encoding the problem structure in a multivariate polynomial and then recovering the solution by means of certain continuous relaxations. This leads to several questions on how to reason about such relaxations and how to compute them. We resolve them by relating certain analytic properties of the arising polynomials, such as the location of their roots or convexity, to the combinatorial structure of the underlying problem.

We believe that the ideas and mathematical techniques developed in this thesis are only a beginning and they will inspire more work on the use of dynamical systems and polynomials in the design of fast algorithms.

Official source

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Concepts associés (32)

Publications associées (115)

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation).
Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de

Informatique

alt=Salle informatique de la bibliothèque d'Art et d'Archéologie de Genève|vignette|Salle informatique de la bibliothèque d'Art et d'Archéologie de Genève (2017).
L'informatique est un domaine d'acti

Optimisation linéaire

thumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble

Chargement

Chargement

Chargement

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also been numerous works that study combinatorial problems with submodular objective functions. This is motivated by their natural diminishing returns property which is useful in real-world applications. The thesis at hand is concerned with the study of streaming and matching problems with submodular functions.Firstly, motivated by developing robust algorithms, we propose a new adversarial injections model, in which the input is ordered randomly, but an adversary may inject misleading elements at arbitrary positions. We study the maximum matching problem and cardinality constrained monotone submodular maximization. We show that even under this seemingly powerful adversary, it is possible to break the barrier of 1/2 for both these problems in the streaming setting. Our main result is a novel streaming algorithm that computes a 0.55-approximation for cardinality constrained monotone submodular maximization.In the second part of the thesis, we study the problem of matroid intersection in the semi-streaming setting. Our main result is a (2 + e)-approximate semi-streaming algorithm for weighted matroid inter- section improving upon the previous best guarantee of 4 + e. While our algorithm is based on the local ratio technique, its analysis differs from the related problem of weighted maximum matching and uses the concept of matroid kernels. We are also able to generalize our results to work for submodular functions by adapting ideas from a recent result by Levin and Wajc (SODA'21) on submodular maximization subject to matching constraints.Finally, we study the submodular Santa Claus problem in the restricted assignment case. The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned problem n unsplittable resources have to be assigned to m players, each with a monotone submodular utility function fi. The goal is to maximize mini fi(Si) where S1, . . . , Sm is a partition of the resources. The result by Goemans et al. implies a polynomial time O(n1/2+e)-approximation algorithm. In the restricted assignment case, each player is given a set of desired resources Gi and the individual valuation functions are defined as fi(S)= f(SnGi). OurmainresultisaO(loglog(n))-approximation algorithm for the problem. Our proof is inspired by the approach of Bansal and Srividenko (STOC'06) to the Santa Claus problem. Com- pared to the more basic linear setting, the introduction of submodularity requires a much more involved analysis and several new ideas.

The common point between the different chapters of the present work is graph theory. We investigate some well known graph theory problems, and some which arise from more specific applications. In the first chapter, we deal with the maximum stable set problem, and provide some new graph classes, where it can be solved in polynomial time. Those classes are hereditary, i.e. characterized by a list of forbidden induced subgraphs. The algorithms proposed are purely combinatorial. The second chapter is devoted to the study of a problem linked to security purposes in mobile telecommunication networks. The particularity is that there is no central authority guaranteeing security, but it is actually managed by the users themselves. The network is modelled by an oriented graph, whose vertices represent the users, and whose arcs represent public key certificates. The problem is to associate to each vertex a subgraph with some requirements on the size of the subgraphs, the number of times a vertex is taken in a subgraph and the connectivity between any two users as they put their subgraphs together. Constructive heuristics are proposed, bounds on the optimal solution and a tabu search are described and tested. The third chapter is on the problem of reconstructing an image, given its projections in terms of the number of occurrences of each color in each row and each column. The case of two colors is known to be polynomially solvable, it is NP-complete with four or more colors, and the complexity status of the problem with three colors is open. An intermediate case between two and three colors is shown to be solvable in polynomial time. The last two chapters are about graph (vertex-)coloring. In the fourth, we prove a result which brings a large collection of NP-hard subcases, characterized by forbidden induced subgraphs. In the fifth chapter, we approach the problem with the use of linear programming. Links between different formulations are pointed out, and some families of facets are characterized. In the last section, we study a branch and bound algorithm, whose lower bounds are given by the optimal value of the linear relaxation of one of the exposed formulations. A preprocessing procedure is proposed and tested.

Combinatorial optimization problems have recently emerged in the design of controllers for OLED displays. The objective is to decompose an image into subframes minimizing the addressing time and thereby also the amplitude of the electrical current through the diodes, which has a direct impact on the lifetime of such a display. To this end, we model this problem as an integer linear program. Subsequently, we refine this formulation by exploiting the combinatorial structure of the problem. We propose a fully combinatorial separation routine for the LP-relaxation based on matching techniques. It can be used as an oracle in various frameworks to derive approximation algorithms or heuristics. We establish NP-hardness and hardness of approximation. Nevertheless, we are able to work around this issue by only focusing on a subsets of the variables and provide experimental evidence that they are sufficient to come up with near optimal solutions in practice. On this basis, one can derive custom-tailored solutions adapting to technical constraints such as memory requirements. By allowing the addressing of distributed doublelines, we improve the addressing time in cases where previous approaches fall short due to their restriction to consecutive doublelines.