Publications related to Results on Sparse Integer Programming and Geometric Independent Sets

Detecting and Tracking Cells using Network Flow Programming

Pascal Fua, Engin Türetken, Xinchao Wang, Carlos Joaquin Becker

We propose a novel approach to automatically detecting and tracking cell populations in time-lapse images. Unlike earlier ones that rely on linking a predetermined and potentially under-complete set of detections, we generate an overcomplete set of competi ...

2015

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

Coloring Relatives of Interval Overlap Graphs via On-line Games

Bartosz Maria Walczak

The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs defined by geometric representations and competitivity analysis of on-line algorithms. This connection became apparent after the recent construction ...

Springer-Verlag Berlin2014

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

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Bartosz Maria Walczak, Michal Lason

A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line L if the intersection of any member with L is a nonempty segment. It is proved that the intersection graphs of simple families of com ...

Springer2014

Triangle-free intersection graphs of line segments with large chromatic number

Bartosz Maria Walczak, Michal Lason

In the 1970s Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is no. Specifically, for each positive integer k we construct a triangle-free fam ...

Academic Press Inc Elsevier Science2014

Approximation algorithms for regret minimization in vehicle routing problems

Adrian Aloysius Bock

In this thesis, we present new approximation algorithms as well as hardness of approximation results for NP-hard vehicle routing problems related to public transportation. We consider two different problem classes that also occur frequently in areas such a ...

EPFL2014

Coding Structure and Replication Optimization for Interactive Multiview Video Streaming

Pascal Frossard

Multiview video refers to videos of the same dynamic 3-D scene captured simultaneously by multiple closely spaced cameras from different viewpoints. We study interactive streaming of pre-encoded multiview videos, where, at any time, a client can request an ...

Ieee-Inst Electrical Electronics Engineers Inc2014

LP-Based Algorithms for Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodo ...

IEEE2014

An Exact Algorithm to Compute the DCJ Distance for Genomes with Duplicate Genes

Bernard Moret, Yu Lin, Mingfu Shao

Computing the edit distance between two genomes is a basic problem in the study of genome evolution. The double-cut-and-join (DCJ) model has formed the basis for most algorithmic research on rearrangements over the last few years. The edit distance under t ...

Springer Verlag2014

Results on Sparse Integer Programming and Geometric Independent Sets

Graph Chatbot

Chat with Graph Search

Detecting and Tracking Cells using Network Flow Programming

Node-weighted network design and maximum sub-determinants

Coloring Relatives of Interval Overlap Graphs via On-line Games

Centrality of Trees for Capacitated k-Center

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Triangle-free intersection graphs of line segments with large chromatic number

Approximation algorithms for regret minimization in vehicle routing problems

Coding Structure and Replication Optimization for Interactive Multiview Video Streaming

LP-Based Algorithms for Capacitated Facility Location

An Exact Algorithm to Compute the DCJ Distance for Genomes with Duplicate Genes

Node-weighted network design and maximum sub-determinants

Centrality of Trees for Capacitated k-Center

LP-Based Algorithms for Capacitated Facility Location

Approximation algorithms for regret minimization in vehicle routing problems

Coding Structure and Replication Optimization for Interactive Multiview Video Streaming

An Exact Algorithm to Compute the DCJ Distance for Genomes with Duplicate Genes

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Coloring Relatives of Interval Overlap Graphs via On-line Games

Triangle-free intersection graphs of line segments with large chromatic number

Detecting and Tracking Cells using Network Flow Programming