**Ê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# The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Moran Feldman, Ashkan Norouzi Fard, Ola Nils Anders Svensson, Rico Zenklusen

*ASSOC COMPUTING MACHINERY, *2020

Article de conférence

Article de conférence

Résumé

We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model that lies between the offline and streaming model, and study it under the aspect of one-way communication complexity. Our model captures the streaming setting (by considering a large number of players), and, in addition, two player approximation results for it translate into the robust setting. We present tight one-way communication complexity results for our model, which, due to the above-mentioned connections, have multiple implications in the data stream and robust setting. Even for just two players, a prior information-theoretic hardness result implies that no approximation factor above 1/2 can be achieved in our model, if only queries to feasible sets, i.e., sets respecting the cardinality constraint, are allowed. We show that the possibility of querying infeasible sets can actually be exploited to beat this bound, by presenting a tight 2/3-approximation taking exponential time, and an efficient 0.514-approximation. To the best of our knowledge, this is the first example where querying a submodular function on infeasible sets leads to provably better results. Through the above-mentioned link to the robust setting, both of these algorithms improve on the current state-of-the-art for robust submodular maximization, showing that approximation factors beyond 1/2 are possible. Moreover, exploiting the link of our model to streaming, we settle the approximability for streaming algorithms by presenting a tight 1/2 + epsilon hardness result, based on the construction of a new family of coverage functions. This improves on a prior 1 - 1/e + epsilon hardness and matches, up to an arbitrarily small margin, the best known approximation algorithm.

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

Publications associées (10)

Chargement

Chargement

Chargement

Concepts associés (25)

Algorithme d'approximation

En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristiq

Fonction sous-modulaire

En optimisation combinatoire, les fonctions sous-modulaires sont des fonctions d'ensemble particulières.
Soient E un ensemble et f une fonction qui à tout sous-ensemble X de E associe un réel f(X), o

Approximation

Une approximation est une représentation imprécise ayant toutefois un lien étroit avec la quantité ou l’objet qu’elle reflète : approximation d’un nombre (de π par 3,14, de la vitesse instantanée d’un

One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job j requires time p(ij) if processed on machine i. More than two decades after its introduction it is still the algorithm of choice even in the restricted model where processing times are of the form p(ij) is an element of {p(j), infinity}. This problem, also known as the restricted assignment problem, is NP-hard to approximate within a factor less than 1.5, which is also the best known lower bound for the general version. Our main result is a polynomial time algorithm that estimates the optimal makespan of the restricted assignment problem within a factor 33/17 + epsilon approximate to 1.9412 + epsilon, where epsilon > 0 is an arbitrarily small constant. The result is obtained by upper bounding the integrality gap of a certain strong linear program, known as the configuration LP, that was previously successfully used for the related Santa Claus problem. Similar to the strongest analysis for that problem our proof is based on a local search algorithm that will eventually find a schedule of the mentioned approximation guarantee but is not known to converge in polynomial time.

Abbas Bazzi, Ilija Bogunovic, Volkan Cevher, Marwa El Halabi, Ya-Ping Hsieh, Ashkan Norouzi Fard

We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream will fail to provide any non-trivial approximation guarantees for SSC. Hence, we consider a relaxed version of SSC, where we only seek to find a partial cover. We design the first Efficient bicriteria Submodular Cover Streaming (ESC-Streaming) algorithm for this problem, and provide theoretical guarantees for its performance supported by numerical evidence. Our algorithm finds solutions that are competitive with the near-optimal offline greedy algorithm despite requiring only a single pass over the data stream. In our numerical experiments, we evaluate the performance of ESC-Streaming on active set selection and large- scale graph cover problems.

2016In periodic scheduling jobs arrive regularly and have to be executed on one or several machines or processors. An enormous amount of literature has been published on this topic, e.g. the founding work of Liu & Layland [LL73] is among the top cited computer science papers, according to Citeseer database. The majority of these papers is mainly concerned about practical applications and several important theoretical questions remained unsolved. Let S be a set of periodic tasks, where each task τ ∈ S releases a job of running time c(τ) and relative deadline d(τ) at each integer multiple of its period p(τ). In the single-processor scheduling one considers rules like Earliest-Deadline-First (EDF) or Rate-monotonic (RM) scheduling, that determine the order, in which the jobs have to be processed. The principal question here is to predict, whether such a schedule is feasible, i.e. whether all jobs are finished before their individual deadlines. It was well-known that to validate the feasibility of an EDF-schedule, one has to evaluate the condition But the complexity status of this test remained unknown, despite of many heuristic approaches in the literature. We prove that testing this condition is coNP-hard even in special cases, answering an open question of Baruah & Pruhs [BP09]. For a static-priority schedule of implicit-deadline tasks, i.e. d(τ) = p(τ), it is known that the jobs of a task τ will meet their deadlines if and only if there exists a fix-point r ∈ [0,p(τ)] of the equation where the sum ranges over all tasks with priority higher than τ . We settle the complexity status of this problem by proving its NP-hardness, even if one asks for modest approximations. Both results are achieved by bridging the more practically oriented area of Real-time scheduling and the field of algorithmic number theory. In fact, the intractability follows by a chain of reductions to simultaneous Diophantine approximation (SDA), which is a classical problem in the geometry of numbers and deals with finding a small denominator Q ∈ {1,…,N}, that yields a good approximation to a given vector of rational numbers α ∈ Qn, i.e. maxi=1,…,n |Qαi - ⎡Qαi⎦| ≤ ε. We strengthen existing hardness results for SDA such that they admit intractability results also for a directed version, where the goal is to find a Q ∈ {1,…,N} with maxi=1,…,n(⎡Qαi⎤ - Qαi) ≤ ε. We show that this problem remains NP-hard if one asks for an approximation that may exceed the bound N by a factor of nO(1/loglogn) and the error bound ε by 2nO(1). As an application we are able to answer an open question of Conforti et al. [CSW08] negatively by obtaining NP-hardness for the problem of optimizing a linear function over a mixing set {(s,y ∈ R≥0 × Zn | s + aiyi ≥ bi ∀i = 1,…, n}. Furthermore we obtain that, regardless to the used ‖ · ‖p-norm, the problem of finding a shortest positive vector in a lattice is not approximable within a factor of nO(1/loglogn), unless NP = P. For scheduling constrained-deadline tasks (i.e. d(τ) ≤ p(τ)) with a static-priority policy one possibly needs machines, which are a factor f > 1 faster than it is needed for the EDF policy. Baruah & Burns [BB08] sandwiched this factor between 1.5 and 2. We pinpoint this value to f = 1/Ω ≈ 1.76 by characterizing the properties of task systems, which attain this value. Here, Ω ≈ 0.56 is a well known constant from complex calculus, defined as real root of x · ex = 1. We further consider a multiprocessor setting, where a given set of tasks has to be assigned to machines, such that each partition is RM-schedulable and the number of occupied processors is minimized. For the popular case that the tasks are equipped with implicit-deadlines, i.e. d(τ) = p(τ), we develop new algorithms as well as intractability results: We state an asymptotic PTAS under resource augmentation. This is achieved by two concepts: First we derive that using a merging and clustering procedure, the instance can be modified, such that the utilization of tasks is lowerbounded by a constant, without excluding near-optimal solutions. Secondly, we introduce a relaxed notion of feasibility, which yields a drastic reduction of complexity and admits to compute solutions via dynamic programming. We introduce a simple First-Fit-like heuristic and obtain that this algorithm behaves nearly optimal on average, by proving that the expected waste is upperbounded by O(n3/4(log n)3/8), if the instance of n tasks is generated randomly. Here, we assume that the utilization values c(τ)/p(τ) of the tasks are drawn uniformly at random from [0, 1]. We state a new approximation algorithm with a running time of O(n3), which can be sketched as follows: Create a graph with the tasks being the nodes and insert edges, if both incident tasks can be scheduled together on a processor. Then define suitable vertex costs and compute a min-cost matching, where the costs are the sum of edge costs plus the vertex costs of not covered nodes. From such a matching solution we can then extract a feasible multiprocessor schedule. The approximation ratio of this algorithm can be proven to tend to 3/2, improving over the previously best known ratio of 7/4 [BLOS95]. We consider a column-based linear programming relaxation for this multiprocessor scheduling problem and derive that the asymptotic integrality gap is located between 4/3 ≈ 1.33 and 1 + ln(2) ≈ 1.69. We disprove the existence of an asymptotic FPTAS, which yields that the problem is strictly harder to approximate than its special case of Bin Packing.