Publications related to Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

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.

An extremal problem on crossing vectors

Bartosz Maria Walczak, Michal Lason

For positive integers w and k, two vectors A and B from Z(w) are called k-crossing if there are two coordinates i and j such that A[i] - B[i] >= k and B[j] - A[j] >= k. What is the maximum size of a family of pairwise 1-crossing and pairwise non-k-crossing ...

Academic Press Inc Elsevier Science2014

Tracking Interacting Objects Optimally Using Integer Programming

Pascal Fua, François Fleuret, Engin Türetken, Xinchao Wang

In this paper, we show that tracking different kinds of interacting objects can be formulated as a network-flow Mixed Integer Program. This is made possible by tracking all objects simultaneously and expressing the fact that one object can appear or disapp ...

Springer Int Publishing Ag2014

On Sub-determinants and the Diameter of Polyhedra

Friedrich Eisenbrand, Martin Niemeier, Marco Di Summa, Nicolas Bonifas

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

Springer2014

Bin Packing via Discrepancy of Permutations

Friedrich Eisenbrand, Thomas Rothvoss, Doemoetoer Palvoelgyi

A well-studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxati ...

Association for Computing Machinery2013

Completeness and Ambiguity of Schema Cover

Karl Aberer, Quoc Viet Hung Nguyen, Zoltán Miklós

Given a schema and a set of concepts, representative of entities in the domain of discourse, schema cover deﬁnes correspondences between concepts and parts of the schema. Schema cover aims at interpreting the schema in terms of concepts and thus, vastly si ...

2013

Tracklet-based Multi-Commodity Network Flow for Tracking Multiple People

Pascal Fua, François Fleuret, Jérôme Berclaz, Horesh Beny Ben Shitrit

(EN)A method for continuously tracking multiple people partitioned into groups while preserving identities under global appearance constraints, wherein people's trajectories may intersect, and wherein only sparse appearance information is available is disc ...

WO2013

Reconstructing Loopy Curvilinear Structures Using Integer Programming

Pascal Fua, Engin Türetken, Fethallah Benmansour

We propose a novel approach to automated delineation of linear structures that form complex and potentially loopy networks. This is in contrast to earlier approaches that usually assume a tree topology for the networks. At the heart of our method is an Int ...

Ieee2013

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

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Graph Chatbot

Chat with Graph Search

An extremal problem on crossing vectors

Tracking Interacting Objects Optimally Using Integer Programming

On Sub-determinants and the Diameter of Polyhedra

Bin Packing via Discrepancy of Permutations

Completeness and Ambiguity of Schema Cover

Tracklet-based Multi-Commodity Network Flow for Tracking Multiple People

Reconstructing Loopy Curvilinear Structures Using Integer Programming

New Results in the Theory of Linear and Integer Programming

Vectors in a box

Santa Claus Schedules Jobs On Unrelated Machines

Reconstructing Loopy Curvilinear Structures Using Integer Programming

On Sub-determinants and the Diameter of Polyhedra

An extremal problem on crossing vectors

Bin Packing via Discrepancy of Permutations

Santa Claus Schedules Jobs On Unrelated Machines

Vectors in a box

Completeness and Ambiguity of Schema Cover

New Results in the Theory of Linear and Integer Programming

Tracking Interacting Objects Optimally Using Integer Programming

Tracklet-based Multi-Commodity Network Flow for Tracking Multiple People