Publication

Sorting signed permutations by inversions in O(nlogn) time

Related publications (41)

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.

Microfluidic train station: highly robust and multiplexable sorting of droplets on electric rails

Christoph Merten

Fluorescence-activated droplet sorting (FADS) has become a widely used technique for high-throughput screening applications. However, existing methods are very sensitive to fluctuating flow rates at the sorting junction, which can be caused by the pulsing ...

2017

An Efficient Streaming Algorithm for the Submodular Cover Problem

Volkan Cevher, Ilija Bogunovic, Ya-Ping Hsieh, Ashkan Norouzi Fard, Abbas Bazzi, Marwa El Halabi

We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream wi ...

2016

Considerations for Rank-based Cryptosystems

Anna-Lena Horlemann, Joachim Rosenthal

Cryptosystems based on rank metric codes have been considered as an alternative to McEliece cryptosystems due to the relative difficulty of solving the rank syndrome decoding problem. Generic attacks have recently seen several improvements, notably in the ...

Ieee2016

A bucket sort algorithm for the particle-in-cell method on manycore architectures

Laurent Villard, Stephan Brunner, Trach-Minh Tran, Claudio Gheller

The Particle-In-Cell (PIC) method is effectively used in many scientific simulation codes. In order to optimize the performance of the PIC approach, data locality is required. This relies on efficient sorting algorithms. We present a bucket sort algorithm ...

Springer2016

Centrality of trees for capacitated -center

Ola Nils Anders Svensson, Hyung Chan An, Aditya Bhaskara

We consider the capacitated -center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) locations (called centers) and assign each ...

Springer Heidelberg2015

Sensing the real world

Juri Ranieri

A sensor is a device that detects or measures a physical property and records, indicates, or otherwise responds to it. In other words, a sensor allows us to interact with the surrounding environment, by measuring qualitatively or quantitatively a given phe ...

EPFL2014

Centrality of Trees for Capacitated k-Center

Ola Nils Anders Svensson, Hyung Chan An, Aditya Bhaskara

We consider the capacitated k-center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) k locations (called centers) and assign e ...

Springer2014

Calibration method and system

Martin Vetterli, Ivan Dokmanic

The present invention concerns a method for calibrating an array of receivers (ri), each receiver being configured for receiving a signal transmitted by at least one transmitter (si), and echoes of the transmitted signal as reflected by one or more reflect ...

2014

Santa Claus Schedules Jobs On Unrelated Machines

Ola Nils Anders Svensson

One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job j requires time p(ij) if processed on machine i. More t ...

Siam Publications2012

New Results in the Theory of Linear and Integer Programming

Nicolai Hähnle

The polynomial Hirsch conjecture states that the vertex-edge diameter of a d-dimensional polyhedron with n facets is bounded by a polynomial in d and n. For the special case where the polyhedron is defined as the set of points satisfying a system Ax ≤ b of ...

EPFL2012