Concept

Problème du postier chinois

Publications associées (37)

The Range of a Random Walk on a Comb

The graph obtained from the integer grid Z x Z by the removal of all horizontal edges that do not belong to the x-axis is called a comb. In a random walk on a graph, whenever a walker is at a vertex v, in the next step it will visit one of the neighbors of ...

Electronic Journal Of Combinatorics2013

Overview of New Approaches for Approximating TSP

Ola Nils Anders Svensson

n this extended abstract, we survey some of the recent results on approximating the traveling salesman problem on graphic metrics. We start by briefly explaining the algorithm of Oveis Gharan et al. [1] that has strong similarities to Christofides’ famo ...

Springer2013

Polynomial Approximations for Continuous Linear Programs

Daniel Kuhn

Continuous linear programs have attracted considerable interest due to their potential for modeling manufacturing, scheduling, and routing problems. While efficient simplex-type algorithms have been developed for separated continuous linear programs, crude ...

2012

Existence of Eulerian Solutions to the Semigeostrophic Equations in Physical Space: The 2-Dimensional Periodic Case

Maria Colombo

In this article we use new regularity and stability estimates for Alexandrov solutions to Monge-Ampere equations, recently established by De Philippis and Figalli [14], to provide global in time existence of distributional solutions to the semigeostrophic ...

2012

Approximating Graphic TSP by Matchings

Ola Nils Anders Svensson

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leadi ...

IEEE Computer Society2011

Joint Sink Mobility and Routing to Maximize the Lifetime of Wireless Sensor Networks: The Case of Constrained Mobility

Jean-Pierre Hubaux, Jun Luo

The longevity of wireless sensor networks (WSNs) is a major issue that impacts the application of such networks. While communication protocols are striving to save energy by acting on sensor nodes, recent results show that network lifetime can be prolonged ...

2010

An Information-Based Approximation Scheme for Stochastic Optimization Problems in Continuous Time

Daniel Kuhn

Dynamic stochastic optimization problems with a large (possibly infinite) number of decision stages and high-dimensional state vectors are inherently difficult to solve. In fact, scenario tree-based algorithms are unsuitable for problems with many stages, ...

2009

A Unified Framework for Joint Sink Mobility and Routing to Increase the Lifetime of Wireless Sensor Networks

Jean-Pierre Hubaux, Jun Luo

The longevity of wireless sensor networks is a major issue that impacts the application of such networks. While communication protocols are striving to save energy by acting on sensor nodes, recent results show that network lifetime can be prolonged by fur ...

2008

Some coloring and walking problems in graphs

Benjamin Leroy-Beaulieu

Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the following ones: graph coloring and the Hamiltonian circuit ...

EPFL2008

A source coding scheme using sparse graphs: Modern Coding Theory Course Exam 2008

Rethnakaran Pulikkoonattu

This is the report that submitted towards the final examination evaluation of the doctoral course \textit{Modern Coding theory} by Ruediger Urbanke at EPFL during Spring 2008. The problem studied can be roughly stated as source coding or compression using ...

2008

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search