Concept

Siegel's lemma

Related publications (5)

Comment 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

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

New Hardness Results for Diophantine Approximation

Friedrich Eisenbrand, Thomas Rothvoss

We revisit simultaneous diophantine approximation, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input of the decision version of this problem consists of a rational vector \alpha, an error b ...

Springer2009

Solving a system of linear diophantine equations with lower and upper bounds on the variables

Arjen Lenstra

We develop an algorithm for solving a system of diophantine equations with lower and upper bounds on the variables. The algorithm is based on lattice basis reduction. It first finds a short vector satisfying the system of diophantine equations, and a set o ...

INFORMS2000

Market split and basis reduction: towards a solution of the Cornuejols-Dawande instances

Arjen Lenstra

Previously, G. Cornuejols and M. Dawande (1998) proposed a set of 0-1 linear programming instances that proved to be very hard to solve by traditional methods, and in particular by linear programming based branch-and-bound. They offered these market split ...

2000

Graph Chatbot

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.