Publications related to Diophantine approximation

Analysis of time compression approximations

TCA, time compression approximation, is a practical and often quite accurate tool to predict postponding infiltration for field applications. A modified approximation (MTCA) can be used just as easily and, in general, will reduce the error by about 50%. Th ...

American Geophysical Union2011

Reliability of clustered vs. declustered replica placement in data storage systems

Rüdiger Urbanke, Christina Fragouli

The placement of replicas across storage nodes in a replication-based storage system is known to affect rebuild times and therefore system reliability. Earlier work has shown that, for a replication factor of two, the reliability is essentially unaffected ...

2011

k-Edge-Connectivity: Approximation and LP Relaxation

David Pritchard

This paper's focus is the following family of problems, denoted k-ECSS, where k denotes a positive integer: given a graph (V, E) and costs for each edge, find a minimum-cost subset F of E such that (V, F) is k-edge-connected. For k=1 it is the spanning tre ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

Approximating Linear Threshold Predicates

Ola Nils Anders Svensson, Mahdi Cheraghchi Bashi Astaneh

We study constraint satisfaction problems on the domain {-1,1}, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form sgn(w_1 x_1 + ... + w_n x_n) for some positive integer weights w_1, ..., w_n. Despite t ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

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

Scheduling periodic tasks in a hard real-time environment

Friedrich Eisenbrand, Martin Niemeier, Nicolai Hähnle

We give a rigorous account on the complexity landscape of an important real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks

\tau_i=(c_i,p_i)

on a minimum number of identical machines a ...

Springer-Verlag2010

Diagonal Quartic Surfaces And Transcendental Elements Of The Brauer Group

Evis Ieronymou

We exhibit central simple algebras over the function field of a diagonal quartic surface over the complex numbers that represent the 2-torsion part of its Brauer group. We investigate whether the 2-primary part of the Brauer group of a diagonal quartic sur ...

Cambridge University Press2010

EDF-schedulability of synchronous periodic task systems is coNP-hard

Friedrich Eisenbrand, Thomas Rothvoss

In the synchronous periodic task model, a set \tau_1,...,\tau_n of tasks is given, each releasing jobs of running time c_i with relative deadline d_i, at each integer multiple of the period p_i. It is a classical result that Earliest Deadline First (EDF) i ...

2010

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Scheduling periodic tasks in a hard real-time environment

Friedrich Eisenbrand, Martin Niemeier, Nicolai Hähnle

We give a rigorous account on the complexity landscape of an important real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks

\tau_i=(c_i,p_i)

on a minimum number of identical machines a ...

Springer-Verlag2010

Diophantine approximation

Analysis of time compression approximations

Flexible and Robust Calibration of the Yule-Nielsen Model for CMYK Prints

Reliability of clustered vs. declustered replica placement in data storage systems

Programmable Triangular Neighborhood Functions of Kohonen Self-Organizing Maps Realized in CMOS Technology

k-Edge-Connectivity: Approximation and LP Relaxation

Approximating Linear Threshold Predicates

Connected facility location via random facility sampling and core detouring

Scheduling periodic tasks in a hard real-time environment

Diagonal Quartic Surfaces And Transcendental Elements Of The Brauer Group

EDF-schedulability of synchronous periodic task systems is coNP-hard

Graph Chatbot

Chat with Graph Search

k-Edge-Connectivity: Approximation and LP Relaxation

Reliability of clustered vs. declustered replica placement in data storage systems

Analysis of time compression approximations

Programmable Triangular Neighborhood Functions of Kohonen Self-Organizing Maps Realized in CMOS Technology

Flexible and Robust Calibration of the Yule-Nielsen Model for CMYK Prints

Scheduling periodic tasks in a hard real-time environment

Approximating Linear Threshold Predicates

EDF-schedulability of synchronous periodic task systems is coNP-hard

Connected facility location via random facility sampling and core detouring

Diagonal Quartic Surfaces And Transcendental Elements Of The Brauer Group