A combinatorial algorithm for computing a maximum independent set in a $t$-perfect graph (2008)
Eisenbrand, Friedrich, Funke, Stefan, Garg, Naveen, Könemann, Jochen
Point containment in the integer hull of a polyhedron (2008)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
Packing a trunk - Now with a twist! (2008)
Eisenbrand, Friedrich, Funke, Stefan, Karrenbauer, Andreas, Reichel, Joachim, Schomer, Elmar
In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of...
Energy-aware stage illumination (2008)
Eisenbrand, Friedrich, Karrenbauer, Andreas, Funke, Stefan, Matijevic, Domagoj
Consider the following illumination problem: given a stage represented by a line segment L and a set of lightsources represented by a set of points S in the plane, assign powers to the lightsources...
Power Assignment Problems in Wireless Communication (2006)
Funke, Stefan, Laue, Soeren, Lotker, Zvi, Naujoks, Rouven
A fundamental class of problems in wireless communication is concerned with the assignment of suitable transmission powers to wireless devices/stations such that the resulting communication graph...
Approximating k-hop minimum-spanning trees (2005)
Althaus, Ernst, Funke, Stefan, Har-Peled, Sariel, Könemann, Jochen, A. Ramos, Edgar, Skutella, Martin
Given a complete graph on~n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Approximating k-hop minimum-spanning trees (2005)
Althaus, Ernst, Funke, Stefan, Har-Peled, Sariel, Könemann, Jochen, A. Ramos, Edgar, Skutella, Martin
Given a complete graph on~n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Approximating k-Hop Minimum-Spanning Trees (2004)
Ernst Althaus, Stefan Funke, Sariel Har-peled, Jochen Konemann, Edgar A. Ramos, Martin Skutella
Given a complete graph on n nodes with metric edge costs, the minimum-cost k- hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Ernst Althaus, Stefan Funke, Sariel Har-peled, Jochen Konemann, Edgar A. Ramos, Martin Skutella
Given a complete graph on n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
This thesis has two main parts. The first part deals with the problem of curve reconstruction. Given a finite sample set S from an unknown collection of curves Gamma, the task is to compute the graph...
Point Containment in the Integer Hull of a Polyhedron (2004)
Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, Kurt Mehlhorn
We show that the point containment problem in the integer hull of a polyhedron, which is de ned by m inequalities, with coecients of at most ' bits can be solved in time O(m + ') in the...
Friedrich Eisenbrand, Stefan Funke, Joachim Reichel
We report on a project with a German car manufacturer.
Point containment in the integer hull of a polyhedron (2004)
Althaus,Ernst, Eisenbrand,Friedrich, Funke,Stefan, Mehlhorn,Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks (2004)
Funke,Stefan, Matijevic,Domagoj, Sanders,Peter
We investigate algorithms for computing energy efficient paths in ad-hoc radio networks. We demonstrate how advanced data structures from computational geometry can be employed to preprocess the...
Improved Approximation Algorithms for Connected Sensor Cover (2004)
Funke,Stefan, Kesselmann,Alexander, Lotker,Zvi, Segal,Michael
Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and...
Point Containment in the Integer Hull of a Polyhedron (2004)
Althaus,Ernst, Eisenbrand,Friedrich, Funke,Stefan, Mehlhorn,Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time...
The LEDA class real number - extended version (2004)
Funke,Stefan, Mehlhorn,Kurt, Schmitt,Susanne, Burnikel,Christoph, Fleischer,Rudolf, Schirra,Stefan
Point containment in the integer hull of a polyhedron (2004)
Althaus,Ernst, Eisenbrand,Friedrich, Funke,Stefan, Mehlhorn,Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Point containment in the integer hull of a polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks (2004)
Funke, Stefan, Matijevic, Domagoj, Sanders, Peter
We investigate algorithms for computing energy efficient paths in ad-hoc radio networks. We demonstrate how advanced data structures from computational geometry can be employed to preprocess the...
Improved Approximation Algorithms for Connected Sensor Cover (2004)
Funke, Stefan, Kesselmann, Alexander, Lotker, Zvi, Segal, Michael, Nikolaidis, Ioanis, Barbeau, Michel, ...
Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and...
Point Containment in the Integer Hull of a Polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time...
The LEDA class real number - extended version (2004)
Funke, Stefan, Mehlhorn, Kurt, Schmitt, Susanne, Burnikel, Christoph, Fleischer, Rudolf, Schirra, Stefan
Point containment in the integer hull of a polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Curve Reconstruction from Noisy Samples (2003)
Siu-wing Cheng, Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-hung Poon, Edgar Ramos
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Approximating Energy Ecient Paths In Wireless Multi-Hop Networks (2003)
Stefan Funke, Domagoj Matijevic, Peter S
Given the positions of n sites in a radio network we consider the problem of finding routes between any pair of sites that minimize energy consumption and do not use more than some constant number k...
A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-perfect Graph (2003)
Friedrich Eisenbrand, Stefan Funke, Naveen Garg, Jochen Knemann
We present a combinatorial polynomial time algorithm to compute a maximum stable set of a t-perfect graph. The algorithm rests on an e-approximation algorithm for general set covering and packing...
Certifying and Repairing Solutions to Large LPs (2003)
Are Lp-solvers, Marcel Dhiflaoui, Stefan Funke, Kurt Mehlhorn, Michael Seel, Elmar Sch, ...
State-of-the-art linear programming (LP) solvers give solutions without any warranty. Solutions are not guaranteed to be optimal or even close to optimal. Of course, it is generally believed that the...
Curve reconstruction from noisy samples (2003)
Cheng, Siu-Wing, Funke, Stefan, Golin, Mordecai J., Kumar, Piyush, Poon, Sheung-Hung, Ramos, Edgar A.
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Approximating Energy Efficient Paths in Wireless Multi-hop Networks (2003)
Funke,Stefan, Matijevic,Domagoj, Sanders,Peter
Given the positions of $n$ sites in a radio network we consider the problem of finding routes between any pair of sites that minimize energy consumption and do not use more than some constant number...
Certifying and Repairing Solutions to Large LPs - How Good are LP-Solvers? (2003)
Dhiflaoui,Marcel, Funke,Stefan, Kwappik,Carsten, Mehlhorn,Kurt, Seel,Michael, Schömer,Elmar, ...
Eisenbrand,Friedrich, Funke,Stefan, Reichel,Joachim, Schömer,Elmar
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to...
Eisenbrand,Friedrich, Funke,Stefan, Reichel,Joachim, Schömer,Elmar
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to...
Curve Reconstruction from Noisy Samples (2003)
Cheng,Siu-Wing, Funke,Stefan, Golin,Mordecai J., Kumar,Piyush, Poon,Sheung-Hung, Ramos,Edgar A.
A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-perfect Graph (2003)
Eisenbrand,Friedrich, Funke,Stefan, Garg,Naveen, Könemann,Jochen
A combinatorial algorithm for computing a maximum independent set in a t-perfect graph (2003)
Eisenbrand,Friedrich, Funke,Stefan, Garg,Naveen, Könemann,Jochen
We present a combinatorial polynomial time algorithm to compute a maximum stable set of a $t$-perfect graph. The algorithm rests on an $e$-approximation algorithm for general set covering and packing...
Approximating Energy Efficient Paths in Wireless Multi-hop Networks (2003)
Funke, Stefan, Matijevic, Domagoj, Sanders, Peter, Di Battista, Giuseppe, Zwick, Uri
Given the positions of $n$ sites in a radio network we consider the problem of finding routes between any pair of sites that minimize energy consumption and do not use more than some constant number...
Certifying and Repairing Solutions to Large LPs - How Good are LP-Solvers? (2003)
Dhiflaoui, Marcel, Funke, Stefan, Kwappik, Carsten, Mehlhorn, Kurt, Seel, Michael, Schömer, Elmar, ...
Eisenbrand, Friedrich, Funke, Stefan, Reichel, Joachim, Schömer, Elmar, Di Battista, Giuseppe, Zwick, Uri
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to...
Eisenbrand, Friedrich, Funke, Stefan, Reichel, Joachim, Schömer, Elmar, Di Battista, Giuseppe, Zwick, Uri
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to...
Curve Reconstruction from Noisy Samples (2003)
Cheng, Siu-Wing, Funke, Stefan, Golin, Mordecai J., Kumar, Piyush, Poon, Sheung-Hung, Ramos, Edgar A.
A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-perfect Graph (2003)
Eisenbrand, Friedrich, Funke, Stefan, Garg, Naveen, Könemann, Jochen
A combinatorial algorithm for computing a maximum independent set in a t-perfect graph (2003)
Eisenbrand, Friedrich, Funke, Stefan, Garg, Naveen, Könemann, Jochen
We present a combinatorial polynomial time algorithm to compute a maximum stable set of a $t$-perfect graph. The algorithm rests on an $e$-approximation algorithm for general set covering and packing...
Smooth-Surface Reconstruction in Near-Linear Time (2002)
A surface reconstruction algorithm takes as input a set of sample points from an unknown closed and smooth surface in 3-d space, and produces a piece-wise linear approximation of the surface that...
This thesis has two main parts. The first part deals with the problem of curve reconstruction. Given a finite sample set S from an unknown collection of curves #, the task is to compute the graph...
Tamal K. Dey, Stefan Funke, Edgar A. Ramos
We describe an implementation of the COCONE algorithm for smooth surface reconstruction which runs in O(n log n) time if the sample is "locally uniform" in addition to being good in the sense...
Smooth-Surface Reconstruction in Near Linear Time (2001)
A surface reconstruction algorithm takes as input a set of sample points from an unknown closed and smooth surface in 3-d space, and produces a piece-wise linear approximation of the surface that...
Surface Reconstruction in Almost Linear Time under Locally Uniform Sampling (2001)
Tamal K. Dey, Stefan Funke, Edgar A. Ramos
We describe a new implementation of the COCONE algorithm for smooth surface reconstruction by Amenta et al. (2000). This implementation runs in O(n log n) time if the sample is "locally uniform" in...
Smooth-Surface Reconstruction in Near Linear Time (2001)
A surface reconstruction algorithm takes as input a set of sample points from an unknown closed and smooth surface in 3-d space, and produces a piece-wise linear approximation of the surface that...
A Separation Bound for Real Algebraic Expressions (2001)
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt
Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking...
Surface Reconstruction in Almost Linear Time under Locally Uniform Sampling (2001)
Tamal K. Dey, Stefan Funke, Edgar A. Ramos
We describe an implementation of the COCONE algorithm for smooth surface reconstruction which runs in O(n log n) time if the sample is "locally uniform" in addition to being good in the sense...
Reconstructing a Collection of Curves with Corners and Endpoints (2001)
We present an algorithm which provably reconstructs a collection of curves with corners and endpoints from a sample set that satisfies a certain sampling condition. The algorithm outputs a polygonal...
This thesis has two main parts. The first part deals with the problem of curve reconstruction. Given a finite sample set S from an unknown collection of curves Gamma, the task is to compute the graph...
LOOK - A Lazy Object-Oriented Kernel for Geometric Computation (2000)
In this paper we describe and discuss a new kernel design for geometric computation in the plane. It combines different kinds of floating-point filter techniques and a lazy evaluation scheme with the...
Structural Filtering - A Paradigm for Efficient and Exact Geometric Programs (1999)
We introduce a new and simple ltering technique that can be used in the implementation of geometric algorithms called "structural ltering". Using this ltering technique we gain about 20 % when...
Exact Geometric Computation Using Cascading (1999)
Christoph Burnikel, Stefan Funke, Michael Seel
In this paper we talk about a new ecient numerical approach to deal with inaccuracy when implementing geometric algorithms. Using various oating-point lters together with arbitrary precision...
Structural Filtering A Paradigm for Ecient and Exact Geometric Programs (1999)
We introduce a new ltering technique that can be used in the implementation of geometric algorithms called "structural ltering". Using this ltering techniques we gain about 20 % when compared to...
Structural Filtering - A Paradigm for Efficient and Exact Geometric Programs (1999)
We introduce a new ltering technique that can be used in the implementation of geometric algorithms called "structural ltering". Using this ltering techniques we gain about 20 % when compared to...
Exact Geometric Predicates using Cascaded Computation (1998)
Christoph Burnikel, Stefan Funke, Michael Seel
In this paper we talk about a new efficient numerical approach to deal with inaccuracy when implementing geometric algorithms. Using various floating-point filters together with arbitrary precision...
Dresden, Med. Akad., Diss. A, 1989 (Nicht f.d. Austausch).
Beigeheftet 2 Sonderabdr. aus Verh. Dtsch. Ges. Path.