Publications related to Multi-Objective Quality-Driven Service Selection-A Fully Polynomial Time Approximation Scheme

Complexity Constrained Representation Selection for Dynamic Adaptive Streaming

Pascal Frossard, Laura Toni, Chenglin Li

In this paper, we propose a representation selection optimization problem for complexity constrained adaptive video streaming that properly takes into account the different complexity-rate-distortion (C-R-D) characteristics of the videos when implementing ...

Ieee2016

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Lukas Polacek

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [2012] ...

Assoc Computing Machinery2016

From Massive Parallelization to Quantum Computing: Seven Novel Approaches to Query Optimization

Immanuel Trummer

The goal of query optimization is to map a declarative query (describing data to generate) to a query plan (describing how to generate the data) with optimal execution cost. Query optimization is required to support declarative query interfaces. It is a co ...

EPFL2016

Exact Algorithms for $ L ^{ 1 } $ -TV Regularization of Real-Valued or Circle-Valued Signals

Michaël Unser, Martin Kurt Storath

We consider

L ^{ 1 }

-TV regularization of univariate signals with values on the real line or on the unit circle. While the real data space leads to a convex optimization problem, the problem is nonconvex for circle-valued data. In this paper, we deriv ...

SIAM2016

A Comment on “Computational Complexity of Stochastic Programming Problems”

Daniel Kuhn, Grani Adiwena Hanasusanto, Wolfram Wiesemann

Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Mathematical Programming A, 106(3):423–432, 200 ...

Springer Heidelberg2016

Parallelizing Query Optimization on Shared-Nothing Architectures

Christoph Koch, Immanuel Trummer

Data processing systems offer an ever increasing degree of parallelism on the levels of cores, CPUs, and processing nodes. Query optimization must exploit high degrees of parallelism in order not to gradually become the bottleneck of query evaluation. We s ...

Assoc Computing Machinery2016

Pattern formation with voluminous processes

Alexandre David Olivier Maurer

When a shoal of small fishes notices a predator, they typically change their collective shape and form a specific pattern. They do so efficiently (in parallel) and without collision. This motivates us to design algorithms with similar properties. In this p ...

EPFL2016

Collision-Free Pattern Formation

Rachid Guerraoui, Alexandre David Olivier Maurer

Shoals of small fishes can change their collective shape and form a specific pattern. They do so efficiently (in parallel) and without collision. In this paper, we study the analog problem of distributed pattern formation. A set of processes needs to move ...

2016

Imprecise Security: Quality and Complexity Tradeoffs for Hardware Information Flow Tracking

Paolo Ienne, Andrew James Becker, Ryan Charles Kastner, Wei Hu

Secure hardware design is a challenging task that goes far beyond ensuring functional correctness. Important design properties such as non-interference cannot be verified on functional circuit models due to the lack of essential information (e.g., sensitiv ...

Assoc Computing Machinery2016

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

János Pach

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of ev ...

Society for Industrial and Applied Mathematics2016

Multi-Objective Quality-Driven Service Selection-A Fully Polynomial Time Approximation Scheme

Graph Chatbot

Chat with Graph Search

Complexity Constrained Representation Selection for Dynamic Adaptive Streaming

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

From Massive Parallelization to Quantum Computing: Seven Novel Approaches to Query Optimization

Exact Algorithms for $ L ^{ 1 } $ -TV Regularization of Real-Valued or Circle-Valued Signals

A Comment on “Computational Complexity of Stochastic Programming Problems”

Parallelizing Query Optimization on Shared-Nothing Architectures

Pattern formation with voluminous processes

Collision-Free Pattern Formation

Imprecise Security: Quality and Complexity Tradeoffs for Hardware Information Flow Tracking

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

Imprecise Security: Quality and Complexity Tradeoffs for Hardware Information Flow Tracking

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

Parallelizing Query Optimization on Shared-Nothing Architectures

Pattern formation with voluminous processes

From Massive Parallelization to Quantum Computing: Seven Novel Approaches to Query Optimization

A Comment on “Computational Complexity of Stochastic Programming Problems”

Collision-Free Pattern Formation

Complexity Constrained Representation Selection for Dynamic Adaptive Streaming

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Exact Algorithms for $ L ^{ 1 } $ -TV Regularization of Real-Valued or Circle-Valued Signals