Publication

An Improved Analysis of Local Search for Max-Sum Diversification

Related publications (68)

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.

Calibration by Correlation Using Metric Embedding from Nonmetric Similarities

Davide Scaramuzza

This paper presents a new intrinsic calibration method that allows us to calibrate a generic single-view point camera just by waving it around. From the video sequence obtained while the camera undergoes random motion, we compute the pairwise time correlat ...

2013

Understanding the Ecumene through Interactive Mapping and Movement-Sensitive Population Indicators: the Case of the Canton Valais, Switzerland

André Ourednik

The canton of Valais can be considered, in many respects, as a synecdoche of the Swiss territory. Presenting many linguistic, cultural or economical polarities that extend over short distances, exacerbating the tension between the ecumene and the ereme, su ...

Universitatea Alexandru Ioan Cuza2013

Commuting Scales. Dynamic Mapping of Time Accessibility

Boris Beaude, Luc Guillemot

Visualization tools can facilitate access to complex spatial phenomenon. This access is what the application to be presented aims at. As a case study to such a complex phenomenon, the addressed question is that of the commuters' space of the Swiss federal ...

2012

Consistent Digital Line Segments

Doemoetoer Palvoelgyi

We introduce a novel and general approach for digitalization of line segments in the plane that satisfies a set of axioms naturally arising from Euclidean axioms. In particular, we show how to derive such a system of digital segments from any total order o ...

2012

Supporting opportunistic search in meetings with tangible tabletop

Pierre Dillenbourg, Frédéric Kaplan, Nan Li

Web searches are often needed in collocated meetings. Many research projects have been conducted for supporting collaborative search in information-seeking meetings, where searches are executed both intentionally and intensively. However, for most common m ...

ACM Press2012

Tight lower bounds for the size of epsilon-nets

János Pach, Gábor Tardos

According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an epsilon-net of size O (1/epsilon log 1/epsilon). Using probabilistic techniques, Pach and Woeginger (1990) showed that there exist range space ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2011

Coding in the Presence of Semantic Value of Information: Unequal Error Protection Using Poset Decoders

In this work we explore possibilities for coding when information worlds have different (semantic) values. We introduce a loss function that expresses the overall performance of a coding scheme for discrete channels and exchange the usual goal of minimizin ...

2011

Overlap properties of geometric expanders

The overlap number of a finite (d + 1)-uniform hypergraph H is the largest constant c(H) is an element of (0, 1] such that no matter how we map the vertices of H into R-d, there is a point covered by at least a c(H)-fraction of the simplices induced by the ...

De Gruyter2011

Order Types of Convex Bodies

We prove a Hadwiger transversal-type result, characterizing convex position on a family of non-crossing convex bodies in the plane. This theorem suggests a definition for the order type of a family of convex bodies, generalizing the usual definition of ord ...

2011

Distributed Sensor Network Localization from Local Connectivity: Performance Analysis for the HOP-TERRAIN Algorithm

Amin Karbasi

This paper addresses the problem of determining the node locations in ad-hoc sensor networks when only connectivity information is available. In previous work, we showed that the localization algorithm MDS-MAP proposed by Y. Shang \textit{et al} is able to ...

2010