77 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- ETH ZurichCH12 papers
- Institute of Theoretical Computer ScienceCH4 papers
- Royal Military College of CanadaCA3 papers
- University of California, DavisUS3 papers
- Charles UniversityCZ2 papers
- Johns Hopkins UniversityUS2 papers
- Aarhus UniversityDK1 paper
- École Polytechnique Fédérale de LausanneCH1 paper
- Institute for Biomedical EngineeringCH1 paper
- Technical University of MunichDE1 paper
- Technische Universität BerlinDE1 paper
- University of WashingtonUS1 paper
12 papers
Convergence of a Packet Routing Model to Flows Over Time
Leon Sering, Laura Vargas Koch, Theresa Ziemke
The mathematical approaches for modeling dynamic traffic can roughly be divided into two categories: discrete packet routing models and continuous flow over time models. Despite ve…
Light on the Infinite Group Relaxation
Amitabh Basu, Robert Hildebrand, Matthias Köppe
This is a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their gro…
Graver basis and proximity techniques for block-structured separable convex integer minimization problems
Raymond Hemmecke, Matthias Köppe, Robert Weismantel
We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In pre…
Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case
Amitabh Basu, Robert Hildebrand, Matthias Köppe
We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson's infinite group problem that are piecewise linear (possibly discontinuous) with…
Counting Unique-Sink Orientations
Jan Foniok, Bernd Gärtner, Lorenz Klaus +1
Unique-sink orientations (USOs) are an abstract class of orientations of the n-cube graph. We consider some classes of USOs that are of interest in connection with the linear compl…
Combinatorial Characterizations of K-matrices
Jan Foniok, Komei Fukuda, Lorenz Klaus
We present a number of combinatorial characterizations of K-matrices. This extends a theorem of Fiedler and Ptak on linear-algebraic characterizations of K-matrices to the setting…
Dualities and dual pairs in Heyting algebras
Jan Foniok, Jaroslav Nesetril, Ales Pultr +1
We extract the abstract core of finite homomorphism dualities using the techniques of Heyting algebras and (combinatorial) categories.
Interleaved adjoints on directed graphs
Jan Foniok, Jaroslav Nesetril, Claude Tardif
For an integer k >= 1, the k-th interlacing adjoint of a digraph G is the digraph i_k(G) with vertex-set V(G)^k, and arcs ((u_1, ..., u_k), (v_1, ..., v_k)) such that (u_i,v_i) \in…
Pivoting in Linear Complementarity: Two Polynomial-Time Cases
Jan Foniok, Komei Fukuda, Bernd Gärtner +1
We study the behavior of simple principal pivoting methods for the P-matrix linear complementarity problem (P-LCP). We solve an open problem of Morris by showing that Murty's least…
Adjoint functors and tree duality
Jan Foniok, Claude Tardif
A family T of digraphs is a complete set of obstructions for a digraph H if for an arbitrary digraph G the existence of a homomorphism from G to H is equivalent to the non-existenc…
Computing Groebner Fans
Komei Fukuda, Anders N. Jensen, Rekha R. Thomas
This paper presents algorithms for computing the Groebner fan of an arbitrary polynomial ideal. The computation involves enumeration of all reduced Groebner bases of the ideal. Our…
Fast optical layer mesh protection using pre-cross-connected trails
Timothy Y. Chow, Fabian Chudak, Anthony M. Ffrench
Conventional optical networks are based on SONET rings, but since rings are known to use bandwidth inefficiently, there has been much research into shared mesh protection, which pr…