Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Hardness of approximation

Publications associées (26)

Fast O(1) Bilateral Filtering Using Trigonometric Range Kernels

Michaël Unser, Daniel Sage, Kunal Narayan Chaudhury

It is well known that spatial averaging can be realized (in space or frequency domain) using algorithms whose complexity does not scale with the size or shape of the filter. These fast algorithms are generally referred to as constant-time or O(1) algorithm ...

IEEE2011

Joint Sink Mobility and Routing to Maximize the Lifetime of Wireless Sensor Networks: The Case of Constrained Mobility

Jean-Pierre Hubaux, Jun Luo

The longevity of wireless sensor networks (WSNs) is a major issue that impacts the application of such networks. While communication protocols are striving to save energy by acting on sensor nodes, recent results show that network lifetime can be prolonged ...

2010

The Median Problems on Linear Multichromosomal Genomes: Graph Representation and Fast Exact Solutions

In genome rearrangement, given a set of genomes G and a distance measure d, the median problem asks for another genome q that minimizes the total distance Sigma(g is an element of G d(q, g)). This is a key problem in genome rearrangement based phylogenetic ...

Mary Ann Liebert2010

Connected facility location via random facility sampling and core detouring

Friedrich Eisenbrand, Thomas Rothvoss

We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the ...

2010

Pre-Synthesis Optimization of Arithmetic Circuits

Ajay Kumar Verma

The efficient synthesis of circuits is a well-studied problem. Due to the NP-hardness of the problem, no optimal algorithm has been presented so far. However, the heuristics presented by several researchers in the past, which are also adopted by commercial ...

EPFL2010

Testing additive integrality gaps

Friedrich Eisenbrand, Doemoetoer Palvoelgyi, Nicolai Hähnle

We consider the problem of testing whether the maximum integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomi ...

2010