Publication
Local Approximation of the Maximum Cut in Regular Graphs
Publications associées (61)
A Dichotomy for Real Weighted Holant Problems
Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks can ...
Springer Basel Ag2016A New Framework for Distributed Submodular Maximization
A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algo ...
Ieee2016MATHICSE Technical Report : Accelerated filtering on graphs using Lanczos method
Pierre Vandergheynst, Daniel Kressner, Nathanaël Perraudin, Ana Susnjara
Sinal-processing on graphs has developed into a very active field of research during the last decade. In particular, the number of applications using frames con-structed from graphs, like wavelets on graphs, has substantially increased. To attain scalabili ...
MATHICSE2015On multiscale methods in Petrov-Galerkin formulation
In this work we investigate the advantages of multiscale methods in Petrov-Galerkin (PG) formulation in a general framework. The framework is based on a localized orthogonal decomposition of a high dimensional solution space into a low dimensional multisca ...
Springer Heidelberg2015Towards Tight Lower Bounds for Scheduling Problems
Ashkan Norouzi Fard, Abbas Bazzi
We show a close connection between structural hardness for k-partite graphs and tight inapproximability results for scheduling problems with precedence constraints. Assuming a natural but nontrivial generalisation of the bipartite structural hardness resul ...
Springer Int Publishing Ag2015Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures
Rachid Guerraoui, Vasileios Trigonakis, Tudor Alexandru David
We introduce "asynchronized concurrency (ASCY),'' a paradigm consisting of four complementary programming patterns. ASCY calls for the design of concurrent search data structures (CSDSs) to resemble that of their sequential counterparts. We argue that ASCY ...
2015Multi-Objective Quality-Driven Service Selection-A Fully Polynomial Time Approximation Scheme
Boi Faltings, Immanuel Trummer
The goal of multi-objective quality-driven service selection (QDSS) is to find service selections for a workflow whose quality-of-service (QoS) values are Pareto-optimal. We consider multiple QoS attributes such as response time, cost, and reliability. A s ...
Institute of Electrical and Electronics Engineers2014On sums of graph eigenvalues
We use two variational techniques to prove upper bounds for sums of the lowest several eigenvalues of matrices associated with finite, simple, combinatorial graphs. These include estimates for the adjacency matrix of a graph and for both the standard combi ...
Elsevier Science Inc2014Opaque Sets
The problem of finding "small" sets that meet every straight-line which intersects a given convex region was initiated by Mazurkiewicz in 1916. We call such a set an opaque set or a barrier for that region. We consider the problem of computing the shortest ...
Springer2014Comment on “Recent advances on solving the three-parameter infiltration equation” by Prabhata K. Swamee, Pushpa N. Rathie, Luan Carlos de S.M. Ozelim and André L.B. Cavalcante, Journal of Hydrology 509 (2014) 188-192
A recent approximation to the three-parameter infiltration was compared with an existing approximation. The new approximation has a minimum relative error that is two orders of magnitude greater than the maximum relative error of the existing approximation ...
Elsevier Science Bv2014