Publications by Martin Niemeier

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.

We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest vector problem in the infinity-norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2^(O(n))(log(1/epsilon ...

We derive a new upper bound on the diameter of a polyhedron , where . The bound is polynomial in and the largest absolute value of a sub-determinant of , denoted by . More precisely, we show that the diameter of is bounded by . If is bounded, then we show ...

Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs ...

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 ...

This thesis is devoted to the design and analysis of algorithms for scheduling problems. These problems are ubiquitous in the modern world. Examples include the optimization of local transportation, managing access to concurrent resources like runways at a ...

We consider several real-time scheduling problems on heterogeneous multiprocessor platforms, in which the different processors share a common memory pool. These include (i)~scheduling a collection of implicit-deadline sporadic tasks with the objective of m ...

We report on the solution of a real-time scheduling problem that arises in the design of software-based operation control of aircraft. A set of tasks has to be distributed on a minimum number of machines and offsets of the tasks have to be computed. The ta ...

Given a graph G with nonnegative node labels w, a multiset of stable sets S_1,...,S_k\subseteq V(G) such that each vertex v \in V(G) is contained in w(v) many of these stable sets is called a weighted coloring. The weighted coloring number \chi_w(G) is the ...

Martin Niemeier

Chat with Graph Search

Covering Cubes and the Closest Vector Problem

On Sub-determinants and the Diameter of Polyhedra

Coloring Fuzzy Circular Interval Graphs

Scheduling periodic tasks in a hard real-time environment

Approximation Algorithms for Modern Multi-Processor Scheduling Problems

Partitioned real-time scheduling on heterogeneous shared-memory multiprocessors

Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods

Coloring fuzzy circular interval graphs

On sub-determinants and the diameter of polyhedra