Randomly rounding rationals with cardinality constraints and derandomizations (2009)
Abstract. We show how to generate randomized roundings of rational vectors that satisfy hard cardinality constraints and allow large deviations bounds. This improves and extends earlier results by...
A Tight Analysis of the (1 + 1)-EA for the Single Source Shortest Path Problem (2009)
Abstract — We conduct a rigorous analysis of the (1 + 1) evolutionary algorithm for the single source shortest path problem proposed by Scharnow, Tinnefeld and Wegener (Journal of Mathematical...
Partial Colorings of Unimodular Hypergraphs Abstract (2008)
Combinatorial discrepancy theory asks for vertex-colorings of hypergraphs such that all hyperedges contain all colors in (as good as possible) equal quantity. Unimodular hypergraphs are good in this...
Inserting Points Uniformly at Every Instance (2008)
Sachio Teramoto, Tetsuo Asano, Benjamin Doerr, Naoki Katoh
Abstract. A problem of arranging n points as uniformly as possible, which is equivalent to that of packing n equal and non-overlapping circles in a unit square, is frequently asked. In this paper we...
THE HEREDITARY DISCREPANCY IS NEARLY INDEPENDENT OF THE NUMBER OF COLORS (2008)
Abstract. We investigate the discrepancy (or balanced coloring) problem for hypergraphs and matrices in arbitrary numbers of colors. We show that the hereditary discrepancy in two different numbers...
Deterministic Random Walks on Regular Trees (2008)
Joshua Cooper, Benjamin Doerr, Tobias Friedrich, Joel Spencer
Jim Propp’s rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. Cooper and Spencer...
Abstract Unbiased Matrix Rounding (2008)
Tobias Friedrich, Benjamin Doerr, Christian Klein, Ralf Osbild
We show several ways to round a real matrix to an integer one such that the rounding errors in all rows and columns as well as the whole matrix are less than one. This is a classical problem with...
Discrepancy of Products of Hypergraphs (2008)
Benjamin Doerr, Michael Gnewuch, Nils Hebbinghaus
For a hypergraph H = (V, E), its d–fold symmetric product is ∆ d H = (V d, {E d |E ∈ E}). We give several upper and lower bounds for the c-color discrepancy of such products. In particular, we...
Benjamin Doerr, Tobias Friedrich
Abstract Deterministic and randomized balancing schemes are used to distribute workload evenly in networks. In this paper, we compare two very general ones: The random walk and the (deterministic)...
THE HEREDITARY DISCREPANCY IS NEARLY INDEPENDENT OF THE NUMBER OF COLORS (2008)
Abstract. We investigate the discrepancy (or balanced coloring) problem for hypergraphs and matrices in arbitrary numbers of colors. We show that the hereditary discrepancy in two different numbers...
On the Minimum Load Coloring Problem- Extended Abstract- (2008)
Nitin Ahuja, Andreas Baltz, Benjamin Doerr, Aleˇs Pˇrívětiv´y An
Given a graph G = (V, E) with n vertices, m edges and maximum vertex degree ∆, the load distribution of a coloring ϕ: V → {red, blue} is a pair dϕ = (rϕ, bϕ), where rϕ is the number of edges...
Improved Bounds and Schemes for the Declustering Problem ⋆ (2008)
Benjamin Doerr, Nils Hebbinghaus, Sören Werth
Abstract. The declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed among the devices. Using...
Deterministic Random Walks on Regular Trees (2008)
Cooper, Joshua, Doerr, Benjamin, Friedrich, Tobias, Spencer, Joel
Component-by-component construction of low-discrepancy point sets of small size (2008)
Doerr, Benjamin, Gnewuch, Michael, Kritzer, Peter, Pillichshammer, Friedrich
How Single Ant ACO Systems Optimize Pseudo-Boolean Functions (2008)
Johannsen, Daniel, Doerr, Benjamin, Tang, Ching Hoo
We undertake a rigorous experimental analysis of the optimization behavior of the two most studied single ant ACO systems on several pseudo-boolean functions. By tracking the behavior of the...
Genetic and Evolutionary Computation Conference 2008 : GECCO 2008 (2008)
Keijzer, Maarten, Antoniol., Giuliano, Congdon, Clare Bates, Deb, Kalyanmoy, Doerr, Benjamin, Hansen, Nikolaus, ...
Vector Balancing Games with Aging (2007)
Benjamin Doerr, Mathematisches Seminar Ii, Deutsche Forschungsgemeinschaft
In this article we study an extension of the vector balancing game investigated by Spencer and Olson (which corresponds to the on-line version of the discrepancy problem for matrices). We assume that...
Discrepancy Of Direct Products Of Hypergraphs (2007)
. We are discussing the discrepancy of direct products of hypergraphs. We show that upper bounds are multiplicative. This solves the problem of the upper bound for the d--dimensional arithmetic...
Discrepancy in Dierent Numbers of Colors (2007)
Benjamin Doerr, Mathematisches Seminar Ii
In this article we investigate the interrelation between the discrepancies of a given hypergraph in dierent numbers of colors. Being an extreme example we determine the multi-color discrepancies of...
MULTICOLOR DISCREPANCY OF ARITHMETIC PROGRESSIONS {EXTENDED ABSTRACT{ (2007)
Benjamin Doerr, Anand Srivastav
We introduce combinatorial multi-color discrepancies and show for the hypergraph of arithmetic
Vector Balancing Games with Aging | Extended Abstract | (2007)
In this article we study an extension of the vector balancing game investigated by Spencer and Olson (which corresponds to the on-line version of the discrepancy problem for matrices). We assume that...
Vector Balancing Games with Aging--- Extended Abstract--- (2007)
In this article we study an extension of the vector balancing game investigated by Spencer and Olson (which corresponds to the on-line version of the discrepancy problem for matrices). We assume that...
Antirandomizing the Wrong Game (2007)
We study a variant of the tenure game introduced by J. Spencer (Theor. Comput. Sci. 131 (1994), 415-429). In this version, chips are not removed from the game, but moved down to the lowest level...
Typical Rounding Problems (2007)
The linear discrepancy problem is to round a given [0; 1]{ vector x to a binary vector y such that the rounding error with respect to a linear form is small, i.e., such that kA(x y)k1 is small for...
Motivated by an application from image processing (Asano et al., SODA 2002), we investigate the problem to round a given [0; 1]{valued matrix to a 0; 1 matrix such that the L 1 rounding error with...
The Hereditary Discrepancy Is Nearly Independent Of The Number Of Colors (2007)
We investigate the discrepancy (or balanced coloring) problem for hypergraphs and matrices in arbitrary numbers of colors. We show that the hereditary discrepancy in two dierent numbers a; b 2 N2 of...
Deterministic Random Walks on the Two-Dimensional Grid (2007)
Doerr, Benjamin, Friedrich, Tobias
Jim Propp's rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. We analyze the...
On the influence of pheromone updates in ACO algorithms (2007)
Doerr, Benjamin, Neumann, Frank, Sudholt, Dirk, Witt, Carsten
The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. These results, however, apply particularly to...
Benjamin Doerr, Frank Neumann, Dirk Sudholt, Carsten Witt, Benjamin Doerr, Dirk Sudholt, ...
This work is a product of the Collaborative Research Center 531, “Computational
Roundings respecting hard constraints (2007)
A problem arising in integer linear programming is transforming a solution of a linear system to an integer one that is "close." The customary model for investigating such problems is, given a matrix...
On the Minimum Load Coloring Problem (2007)
Ahuja, Nitin, Baltz, Andreas, Doerr, Benjamin, Privetivy, Ales, Srivastav, Anand
Adjacency List Matchings --- An Ideal Genotype for Cycle Covers (2007)
Doerr, Benjamin, Johannsen, Daniel
We propose and analyze a novel genotype representation for walk and cycle covers in graphs. Together with a natural mutation operator, it yields superior algorithms based on randomized local search...
Deterministic random walks on the integers (2007)
Cooper, Joshua, Doerr, Benjamin, Spencer, Joel, Tardos, Gábor
Jim Propp’s P-machine, also known as the ‘rotor router model’, is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly chosen...
Matrix approximation and Tusnády’s problem (2007)
We consider the problem of approximating a given matrix by an integer one such that in all geometric submatrices the sum of the entries does not change by much. We show that for all integers m,n≥2...
Deterministic Random Walks on Regular Trees (2007)
Cooper, Joshua, Doerr, Benjamin, Friedrich, Tobias, Spencer, Joel
A Rigorous View On Neutrality (2007)
Doerr, Benjamin, Gnewuch, Michael, Hebbinghaus, Nils, Neumann, Frank
Refined Runtime Analysis of a Basic Ant Colony Optimization Algorithm (2007)
Doerr, Benjamin, Johannsen, Daniel
Neumann and Witt (2006) analyzed the runtime of the basic ant colony optimization (ACO) algorithm {\sc 1-Ant} on pseudo-boolean optimization problems. For the problem {\sc OneMax} they showed how the...
Speeding up Evolutionary Algorithms Through Asymmetric Mutation Operators (2007)
Doerr, Benjamin, Hebbinghaus, Nils, Neumann, Frank
Successful applications of evolutionary algorithms show that certain variation operators can lead to good solutions much faster than other ones. We examine this behavior observed in practice from a...
On the runtime analysis of the 1-ANT ACO algorithm (2007)
Doerr, Benjamin, Neumann, Frank, Sudholt, Dirk, Witt, Carsten
Faster Evolutionary Algorithms by Superior Graph Representation (2007)
Doerr, Benjamin, Klein, Christian, Storch, Tobias
We present a new representation for individuals in problems that have cyclic permutations as solutions. To demonstrate its usefulness, we analyze a simple randomized local search and a (1+1)...
Randomly Rounding Rationals with Cardinality Constraints and Derandomizations (2007)
We show how to generate randomized roundings of rational vectors that satisfy hard cardinality constraints and allow large deviations bounds. This improves and extends earlier results by Srinivasan...
Lp Linear discrepancy of totally unimodular matrices (2007)
Let p [1, ∞[ and cp = maxa [0, 1]((1 − a)ap + a(1 − a)p)1/p. We prove that the known upper bound lindiscp(A) cp for the Lp linear discrepancy of a totally unimodular matrix A...
Hereditary Discrepancies in Different Numbers of Colors II (2006)
Doerr, Benjamin, Fouz, Mahmoud
We bound the hereditary discrepancy of a hypergraph $\HH$ in two colors in terms of its hereditary discrepancy in $c$ colors. We show that $\herdisc(\HH,2) \le K c \herdisc(\HH,c)$, where $K$ is some...
Inserting Points Uniformly at Every Instance (2006)
TERAMOTO, Sachio, ASANO, Tetsuo, KATOH, Naoki, DOERR, Benjamin
Arranging n points as uniformly as possible is a frequently occurring problem. It is equivalent to packing n equal and non-overlapping circles in a unit square. In this paper we generalize this...
Discrepancy of Symmetric Products of Hypergraphs (2006)
Doerr, Benjamin, Gnewuch, Michael, Hebbinghaus, Nils
For a hypergraph ${\mathcal H} = (V,{\mathcal E})$, its $d$--fold symmetric product is $\Delta^d {\mathcal H} = (V^d,\{E^d |E \in {\mathcal E}\})$. We give several upper and lower bounds for the...
Unbiased Matrix Rounding (2006)
Doerr, Benjamin, Friedrich, Tobias, Klein, Christian, Osbild, Ralf
We show several ways to round a real matrix to an integer one such that the rounding errors in all rows and columns as well as the whole matrix are less than one. This is a classical problem with...
Improved Bounds and Schemes for the Declustering Problem (2006)
Doerr, Benjamin, Hebbinghaus, Nils, Werth, Sören
The declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed on the devices. Using deep results...
Deterministic Random Walks on the Integers (2006)
Cooper, Joshua, Doerr, Benjamin, Spencer, Joel, Tardos, Gabor
Jim Propp's P-machine, also known as the "rotor router model" is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it...
Rounding of sequences and matrices, with applications (2006)
Benjamin Doerr, Tobias Friedrich, Christian Klein, Ralf Osbild
Abstract. We show that any real matrix can be rounded to an integer matrix in such a way that the rounding errors of all row sums are less than one, and the rounding errors of all column sums as well...
Lp Linear Discrepancy of Totally Unimodular Matrices ∗ (2006)
Let p ∈ [1, ∞ [ andcp =max a∈[0,1]((1 − a)a p + a(1 − a) p) 1/p. We prove that the known upper bound lindiscp(A) ≤ cp for the Lp linear discrepancy of a totally unimodular matrix A is...
Speeding Up Evolutionary Algorithms through Restricted Mutation Operators (2006)
Benjamin Doerr, Nils Hebbinghaus, Frank Neumann
Abstract. We investigate the effect of restricting the mutation operator in evolutionary algorithms with respect to the runtime behavior. For the Eulerian cycle problem; we present runtime bounds on...
Balanced Partitions of Vector Sequences (2006)
Let d,r ∈ N and � · � be any norm on R d. Let B denote the unit ball with respect to this norm. We show that any sequence v1,v2,... of vectors in B can be partitioned into r subsequences...
Balanced Partitions of Vector Sequences (2006)
Let d,r ∈ N and � · � be any norm on R d. Let B denote the unit ball with respect to this norm. We show that any sequence v1,v2,... of vectors in B can be partitioned into r subsequences...
Unbiased rounding of rational matrices (2006)
Benjamin Doerr, Christian Klein
Abstract. Rounding a real-valued matrix to an integer one such that the rounding errors in all rows and columns are less than one is a classical problem. It has been applied to hypergraph coloring,...
Discrepancy of Symmetric Products of (2006)
Benjamin Doerr, Michael Gnewuch, Nils Hebbinghaus, Benjamin Doerr, Michael Gnewuch, Nils Hebbinghaus
(corresponding author)
Rounding of sequences and matrices, with applications (2006)
Benjamin Doerr, Tobias Friedrich, Christian Klein, Ralf Osbild
Abstract. We show that any real matrix can be rounded to an integer matrix in such a way that the rounding errors of all row sums are less than one, and the rounding errors of all column sums as well...
Inserting points uniformly at every instance (2006)
Teramoto, Sachio, Asano, Tetsuo, Katoh, Naoki, Doerr, Benjamin
Error Propagation in Game Trees (2006)
Game tree search is the core of most attempts to teach computers play games. We present a fairly general theoretical analysis on how evaluation error influence the value estimation of a game...
Matrix Rounding With Respect to Small Submatrices (2006)
We show that any real valued matrix A can be rounded to an integer one B such that the error in all 2 × 2 (geometric) submatrices is less than 1.5, that is, we have |aij - bij| < 1 and for all...
Generating Randomized Roundings with Cardinality Constraints and Derandomizations (2006)
Doerr, Benjamin, Durand, Bruno, Thomas, Wolfgang
We provide a general method to generate randomized roundings that satisfy cardinality constraints. Our approach is different from the one taken by Srinivasan (FOCS 2001) and Gandhi et al....
Unbiased Matrix Rounding (2006)
Doerr, Benjamin, Friedrich, Tobias, Klein, Christian, Osbild, Ralf, Arge, Lars, Freivalds, Rusins
We show several ways to round a real matrix to an integer one in such a way that the rounding errors in all rows and columns as well as the whole matrix are less than one. This is a classical problem...
Deterministic Random Walks (2006)
Cooper, Joshua, Doerr, Benjamin, Spencer, Joel, Tardos, Gábor, Raman, Rajeev, Sedwgewick, Robert, ...
Jim Propp’s P-machine, also known as ‘rotor router model’ is a simple deterministic process that simulates random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it...
Speeding Up Evolutionary Algorithms Through Restricted Mutation Operators (2006)
Doerr, Benjamin, Hebbinghaus, Nils, Neumann, Frank, Runarsson, Thomas Ph., Beyer, Hans G., Burke, Edmund, ...
We investigate the effect of restricting the mutation operator in evolutionary algorithms with respect to the runtime behavior. For the Eulerian cycle problem; we present runtime bounds on...
Deterministic Random Walks on the Two-Dimensional Grid (2006)
Doerr, Benjamin, Friedrich, Tobias, Asano, Tetsuo
Deterministic and randomized balancing schemes are used to distribute workload evenly in networks. In this paper, we compare two very general ones: The random walk and the (deterministic) Propp...
Improved Bounds and Schemes for the Declustering Problem (2006)
Doerr, Benjamin, Hebbinghaus, Nils, Werth, Sören
The declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed on the devices. Using deep results...
Unbiased Rounding of Rational Matrices (2006)
Doerr, Benjamin, Klein, Christian, Arun-Kumar, S., Garg, Naveen
Rounding a real-valued matrix to an integer one such that the rounding errors in all rows and columns are less than one is a classical problem. It has been applied to hypergraph coloring, in...
Balanced partitions of vector sequences (2006)
Let and · be any norm on . Let B denote the unit ball with respect to this norm. We show that any sequence v1, v2, … of vectors in B can be partitioned into r subsequences V1, …, Vr in a...
Inserting Points Uniformly at Every Instance (2006)
Teramoto, Sachio, Asano, Tetsuo, Katoh, Naoki, Doerr, Benjamin
Arranging n points as uniformly as possible is a frequently occurring problem. It is equivalent to packing n equal and non-overlapping circles in a unit square. In this paper we generalize this...
Non-independent randomized rounding and coloring (2006)
We propose an advanced randomized coloring algorithm for the problem of balanced colorings of hypergraphs (discrepancy problem). Instead of independently coloring the vertices with a random color, we...
Discrepancy of Symmetric Products of Hypergraphs (2006)
Doerr, Benjamin, Gnewuch, Michael, Hebbinghaus, Nils
For a hypergraph ${\mathcal H} = (V,{\mathcal E})$, its $d$--fold symmetric product is $\Delta^d {\mathcal H} = (V^d,\{E^d |E \in {\mathcal E}\})$. We give several upper and lower bounds for the...
Doerr, Benjamin, Lengler, Johannes, Steurer, Daniel, Asano, Tetsuo
We regard the problem of communication in the presence of faulty transmissions. In contrast to the classical works in this area, we assume some structure on the times when the faults occur. More...
Inserting Points Uniformly at Every Instance (2006)
TERAMOTO, Sachio, ASANO, Tetsuo, KATOH, Naoki, DOERR, Benjamin
Arranging n points as uniformly as possible is a frequently occurring problem. It is equivalent to packing n equal and non-overlapping circles in a unit square. In this paper we generalize this...
Matrix Rounding with Respect to Small (2005)
We show that any real valued matrix A can be rounded to an integer one B such that the error in all 2 × 2 (geometric) submatrices is less than 1.5, that is, we have |aij − bij | < 1 and |...
Roundings respecting hard constraints (2005)
Abstract. A problem arising in integer linear programming is to transform a solution of a linear system to an integer one which is “close”. The customary model to investigate such problems is,...
Roundings respecting hard constraints (2005)
Abstract. A problem arising in integer linear programming is to transform a solution of a linear system to an integer one which is “close”. The customary model to investigate such problems is,...
Bounds and Constructions for the (2005)
Benjamin Doerr, Michael Gnewuch
Abstract For numerical integration in higher dimensions, bounds for the star-discrepancy with polynomial dependence on the dimension d are desirable. Furthermore, it is still a great challenge to...
Bounds and constructions for the star-discrepancy via δ-covers (2005)
Benjamin Doerr, Michael Gnewuch
For numerical integration in higher dimensions, bounds for the star-discrepancy with polynomial dependence on the dimension d are desirable. Furthermore, it is still a great challenge to give...
Discrepancy of Products of Hypergraphs (2005)
Doerr, Benjamin, Hebbinghaus, Nils, Felsner, Stefan
For a hypergraph {${\mathcal{H} = (V,\mathcal{E})}$}, its {${d}$}--fold symmetric product is {${ \Delta ^{d} \mathcal{H} = (V^{d},\{ E^{d} | E {\in}\mathcal{E} \}) }$}. We give several upper and...
Bounds and Constructions for the Star-Discrepancy via Delta-Covers (2005)
Doerr, Benjamin, Gnewuch, Michael, Srivastav, Anand
For numerical integration in higher dimensions, bounds for the star-dis\-cre\-pan\-cy with polynomial dependence on the dimension $d$ are desirable. Furthermore, it is still a great challenge to give...
Deterministic Random Walks on the Integers (2005)
Cooper, Joshua, Doerr, Benjamin, Spencer, Joel, Tardos, Gabor, Felsner, Stefan
Balanced Partitions of Vector Sequences (2004)
Let $d, r \in \N$, $\|\cdot\|$ any norm on $\R^d$ and $B$ denote the unit ball with respect to this norm. We show that any sequence $v_1,v_2,...$ of vectors in $B$ can be partitioned into $r$...
Global roundings of sequences (2004)
For a given sequence a = (a1,..., an) of numbers, a global rounding is an integer sequence b = (b1,..., bn) such that the rounding error i∈I (ai − bi) | is less than one in all intervals I ⊆...
Improved bounds and schemes for the declustering problem (2004)
Benjamin Doerr, Nils Hebbinghaus, Sören Werth
The declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed on the devices. Using deep results...
Non-independent randomized rounding (2003)
We investigate an extension of the randomized rounding technique introduced by Raghavan and Thompson. Whereas their approach only requires that each variable is rounded with probabilities given by...
Typical Rounding Problems (2003)
Benjamin Doerr, Mathematisches Seminar
In this paper we strengthen this result for the common situation that the discrepancy of submatrices having n0 columns is bounded by Cnff0 for some C? 0; ff 2]0; 1]. In this case, we improve the...
Multi-Color Discrepancies (2003)
Benjamin Doerr, Anand Srivastav
In this article we introduce combinatorial multi-color discrepancies and generalize several classical results from 2-color discrepancy theory to c colors (c ≥ 2). We give a recursive method...
Non-independent Randomized Rounding and an Application to Digital Halftoning (2002)
Benjamin Doerr, Henning Schnieder
We investigate the problem to round a given [0; 1]{valued matrix to a 0; 1 matrix such that the rounding error with respect to 2 2 boxes is small. Such roundings yield good solutions for the digital...
Benjamin Doerr, Mathematisches Seminar, Bereich Ii
We study a variant of the tenure game introduced by J. Spencer (Theor. Comput. Sci. 131 (1994), 415-429). In this version, faculty is not red, but downgraded to the lowest rung instead.
Structured randomized rounding and coloring (2001)
Abstract. In this paper we propose an advanced randomized coloring algorithm for the problem of balanced colorings of hypergraphs (discrepancy problem). It allows to use structural information about...
Linear discrepancy of totally unimodular matrices (2001)
We show that the linear discrepancy of a totally unimodular mn matrix A is at most lindisc(A) 1 1
Lattice approximation and linear discrepancy of totally unimodular matrices (2001)
This paper shows that the lattice approximation problem for totally unimodular matrices A 2 R mn can be solved eciently and optimally via a linear programming approach. The complexity of our...
Coloring t-Dimensional m-Boxes (2001)
Geir Agnarsson, Benjamin Doerr, Tomasz Schoen
. Call the set S1 S t t{dimensional m{box if jS i j = m for every i = 1; : : : ; t. Let R t (m; r) be the smallest integer R such that for every r{coloring of t{fold cartesian product of [R] one can...
Recursive Randomized Coloring Beats Fair Dice Random Colorings (2001)
Benjamin Doerr, Anand Srivastav
We investigate a re ned recursive coloring approach to construct balanced colorings for hypergraphs. A coloring is called balanced if each hyperedge has (roughly) the same number of vertices in each...
Linear discrepancy of totally unimodular matrices (2001)
Benjamin Doerr, Deutsche Forschungsgemeinschaft
We show that the linear discrepancy of a totally unimodular m×n matrix A is at most lindisc(A) ≤ 1 − 1 n+1. This bound is sharp. In particular, this result proves Spencer’s con-) herdisc(A) in...
Lattice approximation and linear discrepancy of totally unimodular matrices (2001)
\Lambda y Abstract This paper shows that the lattice approximation problem for totally unimodular matrices A 2 R m\Theta n can be solved efficiently and optimally via a linear programming approach....
Object Management Group – Telecom Distributed Accounting Facility (2001)
Benjamin Doerr, Tobias Friedrich, Christian Klein, Ralf Osbild
Abstract. We show several ways to round a real matrix to an integer one such that the rounding errors in all rows and columns as well as the whole matrix are less than one. This is a classical...
Dipl Math, Benjamin Doerr, Referent Prof, Zum Druck Genehmigt
zur Erlangung des Doktorgrades
Linear discrepancy of basic totally unimodular matrices (2000)
We show that the linear discrepancy of a basic totally unimodular matrix A ∈ ^Rm×n is at most 1 − 1/n+1. This extends a result of Peng and Yan.
Approximation of multi-color discrepancy (1999)
Benjamin Doerr, Anand Srivastav
Abstract. In this article we introduce (combinatorial) multi--color discrepancy and generalize some classical results from 2--color discrepancy theory to c colors. We give a recursive method that...
Communication Complexity And The Protocol Partition Number (1999)
. In this article we investigate the connection between the communication complexity D(f) of a function f : X Y ! Z and its protocol partition number C P (f ). Using a new tree transformation we...
Linear And Hereditary Discrepancy (1999)
. Let A be a m \Theta n--matrix and q := blog 2 (m)c + 1. In this article we are going to improve the well--known bound lindisc(A) 2 herdisc(A) and show lindisc(A) 2 \Gamma 1 \Gamma 2 \Gammaq \Delta...
Approximation of multi-color discrepancy (1999)
Benjamin Doerr, Anand Srivastav
Abstract. In this article we introduce combinatorial multi-color discrepancies and generalize several classical results from 2–color discrepancy theory to c colors (c ≥ 2). We give a recursive...
Discrepancies of cartesian products of arithmetic progressions (1998)
Benjamin Doerr, Anand Srivastav, Petra Wehr
locally compact abelian groups. We determine the combinatorial discrepancy of the hypergraph H of cartesian products of d arithmetic progressions in the [N] d {lattice ([N] = f0; 1; : : : ; N 1g)....
On the discrepancy of combinatorial rectangles (1995)
Abstract. Let B d n denote the family which consists of all subsets S1 × · · · × Sd, where Si ⊆ [n], and Si � = ∅, for i = 1,..., d. We compute the L2–discrepancy of B d n and give...
On the discrepancy of combinatorial rectangles (1995)
Abstract. Let B d n denote the family which consists of all subsets S1 × · · · × Sd, where Si ⊆ [n], and Si � = ∅, for i = 1,..., d. We compute the L2–discrepancy of B d n and give...
On the Discrepancy of Combinatorial Rectangles
Noga Alon, Benjamin Doerr, Tomasz Luczak, Tomasz Schoen
Let B n denote the family which consists of all subsets S 1 S d , where S i [n], and S i 6= ;, for i = 1; : : : ; d. We n and give estimates for the L p { discrepancy of B n for 1 p 1. 1.