2020-10-24T15:27:28Zhttp://edoc.mpg.de/ac_ft_oai.ploai:edoc.mpg.de:2018342012-09-1987:931
Approximating Energy Efficient Paths in Wireless Multi-hop Networks
Funke, Stefan
Matijevic, Domagoj
Sanders, Peter
Di Battista, Giuseppe
Zwick, Uri
expertsonly
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$ of hops. Known exact algorithms for this problem
required $\Omega(n \log n)$ per query pair $(p,q)$. In this paper we
relax the exactness requirement and only require approximate
$(1+\epsilon)$ solutions which allows us to derive schemes which
guarantee constant query time using linear space and
$O(n\log n)$ preprocessing time. The dependence on $\epsilon$ is
polynomial in $1/\epsilon$.
One tool used might be of independent interest:
For any pair of points $(p,q)\in P\subseteq\mathbb{Z}^2$
report in constant time the cluster pair $(A,B)$ representing $(p,q)$
in a well-separated pair decomposition of $P$.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201834
urn:ISBN:3-540-20064-9
Algorithms - ESA 2003: 11th Annual European Symposium, Springer, 230-241 (2003)
en
oai:edoc.mpg.de:2018352012-09-1987:931
On the Competitive Ratio for Online Facility Location
Fotakis, Dimitris
Baeten, Jos C.M.
Lenstra, Jan Karel
Parrow, Joachim
Woeginger, Gerhard J.
expertsonly
We consider the problem of Online Facility Location, where demands arrive
online and must be irrevocably assigned to an open facility upon arrival. The
objective is to minimize the sum of facility and assignment costs. We prove
that the competitive ratio for Online Facility Location is $\Theta(\frac{\log
n}{\log\log n})$. On the negative side, we show that no randomized algorithm
can achieve a competitive ratio better than $O(\frac{\log n}{\log\log n})$
against an oblivious adversary even if the demands lie on a line segment. On
the positive side, we present a deterministic algorithm achieving a competitive
ratio of $O(\frac{\log n}{\log\log n})$. The analysis is based on a
hierarchical decomposition of the optimal facility locations such that each
component either is relatively well-separated or has a relatively large
diameter, and a potential function argument which distinguishes between the two
kinds of components.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201835
urn:ISBN:3-540-40493-7
Automata, languages and programming : 30th International Colloquium, ICALP 2003, Springer, 637-652 (2003)
en
oai:edoc.mpg.de:2018572012-09-1987:931
Space Efficient Hash Tables with Worst Case Constant Access Time
Fotakis, Dimitris
Pagh, Rasmus
Sanders, Peter
Spirakis, Paul G.
Alt, Helmut
Habib, Michel
expertsonly
We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$d$-ary Cuckoo Hashing}
and show how this yields a simple hash table data structure that stores $n$
elements in $(1+\epsilon)\,n$ memory cells, for any constant $\epsilon > 0$.
Assuming uniform hashing, accessing or deleting table entries takes at most $d
= O(\ln\frac{1}{\epsilon})$ probes and the expected amortized insertion time is
constant. This is the first dictionary that has worst case constant access time
and expected constant update time, works with $(1+\epsilon)\,n$ space, and
supports satellite information. Experiments indicate that $d=4$ choices suffice
for $\epsilon \approx 0.03$. We also describe a hash table data structure using
explicit constant time hash functions, using at most $d=
O(\ln^2\frac{1}{\epsilon})$ probes in the worst case.
A corollary is an expected linear time algorithm for finding maximum
cardinality matchings in a rather natural model of sparse random bipartite
graphs.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201857
urn:ISBN:3-540-00623-0
Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003), Springer, 271-282 (2003)
en
oai:edoc.mpg.de:2018692012-09-1987:931
Fast Lightweight Suffix Array Construction and Checking
Burkhardt, Stefan
Kärkkäinen, Juha
Baeza-Yates, R.
Chávez, E.
Crochemore, M.
expertsonly
We describe an algorithm that, for any $v\in[2,n]$, constructs
the suffix array of a string of length $n$ in $\Oh{vn + n \log
n}$ time using $\Oh{v+n/\sqrt{v}}$ space in addition to the
input (the string) and the output (the suffix array). By setting
$v=\log n$, we obtain an $\Oh{n \log n}$ time algorithm using
$\Oh{n/\sqrt{\log n}}$ extra space. This solves the open problem
stated by Manzini and Ferragina [ESA\;'02] of whether there
exists a lightweight (sublinear extra space) $\Oh{n \log n}$ time
algorithm. The key idea of the algorithm is to first sort a
sample of suffixes chosen using mathematical constructs called
difference covers. The algorithm is not only lightweight but also
fast in practice as demonstrated by experiments. Additionally,
we describe fast and lightweight suffix array checkers, i.e.,
algorithms that check the correctness of a suffix array.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201869
urn:ISSN:0302-9743
Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003, Springer, 55-69 (2003)
en
oai:edoc.mpg.de:2019802012-09-1987:931
Randomized Pursuit-Evasion in Graphs
Adler, Micah
Räcke, Harald
Sivadasan, Naveen
Sohler, Christian
Vöcking, Berthold
expertsonly
2003
Article
http://edoc.mpg.de/201980
urn:ISSN:0963-5483
Combinatorics, Probability and Computing, v.12, 225-244 (2003)
en
oai:edoc.mpg.de:2020442012-09-1987:931
Smoothed Analysis of Three Combinatorial Problems
Banderier, Cyril
Beier, Rene
Mehlhorn, Kurt
Rovan, Branislav
Vojtáš, Peter
expertsonly
Smoothed analysis combines elements over worst-case and
average case analysis. For an instance $x$, the smoothed complexity is the
average complexity of an instance obtained from $x$ by a perturbation. The
smoothed complexity of a problem is the worst smoothed complexity of any
instance. Spielman and Teng introduced this notion for
continuous problems. We apply the concept to combinatorial problems and study
the smoothed complexity of three classical discrete problems: quicksort,
left-to-right maxima counting, and shortest paths.
Springer
2003
Conference-Paper
http://edoc.mpg.de/202044
urn:ISBN:3-540-40671-9
Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003, Springer, 198-207 (2003)
en
oai:edoc.mpg.de:2311772012-09-1987:931
Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Albers, Susanne
Radzik, Tomasz
expertsonly
A minimal blocker in a bipartite graph $G$ is a minimal set of edges the
removal of which leaves no perfect matching in $G$. We give an explicit
characterization of the minimal blockers of a bipartite graph $G$. This result
allows us to obtain a polynomial
delay algorithm for finding all minimal blockers of a given bipartite graph.
Equivalently, this gives a polynomial delay algorithm for listing the
anti-vertices of the perfect matching polytope $P(G)=\{x\in
\RR^E~|~Hx=\be,~~x\geq 0\}$, where $H$ is the incidence matrix of $G$. We also
give similar generation algorithms for other related problems, including
generalized perfect matchings in bipartite graphs, and perfect 2-matchings in
general graphs.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231177
urn:ISBN:3-540-23025-4
Algorithms – ESA 2004: 12th Annual European Symposium, Springer, 122-133 (2004)
en
oai:edoc.mpg.de:2311782012-09-1987:931
Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Khachiyan, Leonid
Bienstock, Daniel
Nemhauser, George
expertsonly
We consider the problems of enumerating all minimal strongly connected
subgraphs and all minimal dicuts of a given directed graph G=(V,E). We show
that the first of these problems can be solved in incremental polynomial time,
while the second problem is NP-hard: given a collection of minimal dicuts for
G, it is NP-complete to tell whether it can be extended. The latter result
implies, in particular, that for a given set of points , it is NP-hard to
generate all maximal subsets of contained in a closed half-space through the
origin. We also discuss the enumeration of all minimal subsets of whose convex
hull contains the origin as an interior point, and show that this problem
includes as a special case the well-known hypergraph transversal problem.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231178
urn:ISBN:3-540-22113-1
Integer programming and combinatorial optimization : 10th International IPCO Conference, Springer, 152-162 (2004)
en
oai:edoc.mpg.de:2311792012-09-1987:931
Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Khachiyan, Leonid
Farach-Colton, Martin
expertsonly
Given a finite set $V$, and integers $k \geq 1$ and $r \geq 0$,
denote by $\AA(k,r)$ the class of hypergraphs $\cA \subseteq 2^V$
with $(k,r)$-bounded intersections, i.e. in which
the intersection of any $k$ distinct hyperedges has size at most $r$. We
consider the problem $MIS(\cA,\cI)$:
given a hypergraph $\cA$ and a subfamily $\cI \subseteq \In$,
of its maximal independent sets (MIS) $\In$, either extend this subfamily by
constructing a new MIS $I \in \In \setminus \cI$
or prove that there are no more MIS, that is $\cI = \In$.
We show that for hypergraphs $\cA\in\AA(k,r)$ with $k+r\le const$, problem
MIS$(\cA,\cI)$ is NC-reducible to problem MIS$(\cA',\emptyset)$ of generating a
single MIS for
a partial subhypergraph $\cA'$ of $\cA$. In particular, for this class of
hypergraphs, we get an incremental polynomial algorithm for generating all MIS.
Furthermore, combining this result with the currently known algorithms for
finding a single maximal independent set of a hypergraph, we obtain efficient
parallel algorithms for incrementally generating all MIS for hypergraphs in the
classes $\AA(1,c)$, $\AA(c,0)$, and $\AA(2,1)$, where $c$ is a constant. We
also show that,
for $\cA \in \AA(k,r)$, where $k+r\le const$, the problem of
generating all MIS of $\cA$ can be solved in incremental polynomial-time with
space polynomial only in the size of $\cA$.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231179
urn:ISBN:3-540-21258-2
LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Springer, 488-498 (2004)
en
oai:edoc.mpg.de:2311802012-09-1987:931
Generating Paths and Cuts in Multi-pole (Di)graphs
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Khachiyan, Leonid
Makino, Kazuhisa
Fiala, Jirí
Koubek, Václav
Kratochvíl, Jan
expertsonly
Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given
a set of (source-sink) pairs of vertices of G, an important problem that
arises in the computation of network reliability is the enumeration of minimal
subsets of edges (arcs) that connect/disconnect all/at least one of the given
source-sink pairs of . For undirected graphs, we show that the enumeration
problems for conjunctions of paths and disjunctions of cuts can be solved in
incremental polynomial time. For directed graphs both of these problems are
NP-hard. We also give a polynomial delay algorithm for enumerating minimal sets
of arcs connecting respectively two given nodes s1 and s2 to a given vertex t1,
and each vertex of a given subset of vertices T2.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231180
urn:ISBN:3-540-22823-3
Mathematical foundations of computer science 2004 : 29th International Symposium, MFCS 2004, Springer, 298-309 (2004)
en
oai:edoc.mpg.de:2311812012-09-1987:931
An Efficient Implementation of a Joint Generation Algorithm
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Khachiyan, Leonid
Ribeiro, Celso C.
Martins, Simone L.
expertsonly
Let $\cC$ be an n-dimensional integral box, and $\pi$ be a monotone property
defined over the elements of $\cC$. We consider the problems of incrementally
generating jointly the families $\cF_{\pi}$ and $\cI(cF_{\pi})$ of all minimal
subsets satisfying property $\pi$ and all maximal subsets not satisfying
property $\pi$, when $\pi$ is given by a polynomial-time satisfiability oracle.
Problems of this type arise in many practical applications. It is known that
the above joint generation problem can be solved in incremental
quasi-polynomial time. In this paper, we present an efficient implementation of
this procedure. We present experimental results to evaluate our implementation
for a number of interesting monotone properties $\pi$.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231181
urn:ISBN:3-540-22067-4
Experimental and efficient algorithms : Third International Workshop, WEA 2004, Springer, 114-128 (2004)
en
oai:edoc.mpg.de:2311882012-09-1987:931
Engineering an External Memory Minimum Spanning Tree Algorithm
Dementiev, Roman
Sanders, Peter
Schultes, Dominik
Sibeyn, Jop F.
Lévy, Jean-Jacques
Mayr, Ernst W.
Mitchell, John C.
expertsonly
We develop an external memory algorithm for computing minimum spanning
trees. The algorithm is considerably simpler than previously known
external memory algorithms for this problem and needs a factor of at
least four less I/Os for realistic inputs.
Our implementation indicates that this algorithm processes graphs only
limited by the disk capacity of most current machines in time no more
than a factor 2--5 of a good internal algorithm with sufficient memory
space.
Kluwer
2004
Conference-Paper
http://edoc.mpg.de/231188
urn:ISBN:1-4020-8140-5
3rd IFIP International Conference on Theoretical Computer Science (TSC2004), Kluwer, 195-208 (2004)
en
oai:edoc.mpg.de:2311922012-09-1987:931
Algorithms for recognizing coordinates in two variables over UFD's
El Kahoui, M'hammed
Gutierrez, Jaime
expertsonly
ACM
2004
Conference-Paper
http://edoc.mpg.de/231192
urn:ISBN:1-58113-827-X
Proceedings of the 2004 International Symposium Symbolic and Algebraic Computation (ISSAC-04), ACM, 135-140 (2004)
en
oai:edoc.mpg.de:2311932012-09-1987:931
Scalable Multimedia Disk Scheduling
Elbassioni, Khaled
Mokbel, Mohamed F.
Aref, Walid G.
Kamel, Ibrahim
expertsonly
A new multimedia disk scheduling algorithm, termed Cascaded-SFC, is presented.
The Cascaded-SFC multimedia disk scheduler is applicable in environments where
multimedia data requests arrive with different quality of service (QoS)
requirements such as real-time deadline and user priority. Previous work on
disk scheduling has focused on optimizing the seek times and/or meeting the
real-time deadlines. The Cascaded-SFC disk scheduler provides a unified
framework for multimedia disk scheduling that scales with the number of
scheduling parameters. The general idea is based on modeling the multimedia
disk requests as points in multiple multi-dimensional sub-spaces, where each of
the dimensions represents one of the parameters (e.g., one dimension represents
the request deadline, another represents the disk cylinder number, and a third
dimension represents the priority of the request, etc.). Each multi-dimensional
sub-space represents a subset of the QoS parameters that share some common
scheduling characteristics. Then the multimedia disk scheduling problem reduces
to the problem of finding a linear order to traverse the multi-dimensional
points in each sub-space. Multiple space-filling curves are selected to fit the
scheduling needs of the QoS parameters in each sub-space. The orders in each
sub-space are integrated in a cascaded way to provide a total order for the
whole space. Comprehensive experiments demonstrate the efficiency and
scalability of the Cascaded-SFC disk scheduling algorithm over other disk
schedulers.
IEEE
2004
Conference-Paper
http://edoc.mpg.de/231193
urn:ISBN:0-7695-2065-0
20th International Conference on Data Engineering, ICDE 2004, IEEE, 498-509 (2004)
en
oai:edoc.mpg.de:2311942012-09-1987:931
Incremental Algorithms for Facility Location and k-Median
Fotakis, Dimitris
Albers, Susanne
Radzik, Tomasz
expertsonly
In the incremental versions of Facility Location and k-Median, the demand
points arrive one at a time and the algorithm must maintain a good solution by
either adding each new demand to an existing cluster or placing it in a new
singleton cluster. The algorithm can also merge some of the existing clusters
at any point in time. We present the first incremental algorithm for Facility
Location with uniform facility costs which achieves a constant performance
ratio and the first incremental algorithm for k-Median which achieves a
constant performance ratio using O(k) medians.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231194
urn:ISBN:3-540-23025-4
Algorithms – ESA 2004: 12th Annual European Symposium, Springer, 347-358 (2004)
en
oai:edoc.mpg.de:2311992012-09-1987:931
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks
Funke, Stefan
Matijevic, Domagoj
Sanders, Peter
expertsonly
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 position of
radio stations in such a way that approximately
energy optimal paths can be retrieved in constant time, i.e.,
independent of the network size.
We put particular emphasis on actual implementations which
demonstrate that large constant factors hidden in the theoretical
analysis are not a big problem in practice.
University of Bologna
2004
Conference-Paper
http://edoc.mpg.de/231199
First International Workshop on Algorithms for Wireless and Mobile Networks, University of Bologna, 97-111 (2004)
en
oai:edoc.mpg.de:2312222012-09-1987:931
A simpler linear time 2/3 - eps approximation for maximum weight matching
Pettie, Seth
Sanders, Peter
expertsonly
2004
Article
http://edoc.mpg.de/231222
Information Processing Letters, v.91, 271-276 (2004)
en
oai:edoc.mpg.de:2312242012-09-1987:931
Online scheduling with bounded migration
Sanders, Peter
Sivadasan, Naveen
Skutella, Martin
Díaz, Josep
Karhumäki, Juhani
Lepistö, Arto
Sannella, Donald
expertsonly
Springer
2004
Conference-Paper
http://edoc.mpg.de/231224
urn:ISBN:3-540-22849-7
Automata, languages and programming : 31st International Colloquium, ICALP 2004, Springer, 1111-1122 (2004)
en
oai:edoc.mpg.de:2312262012-09-1987:931
Topology matters: Smoothed competitiveness of metrical task systems
Schäfer, Guido
Sivadasan, Naveen
Diekert, Volker
Habib, Michel
expertsonly
Springer
2004
Conference-Paper
http://edoc.mpg.de/231226
urn:ISBN:3-540-21236-1
21st Annual Symposium on Theoretical Aspects of Computer Science (STACS-04), Springer, 489-500 (2004)
en
oai:edoc.mpg.de:2312312012-09-1987:931
Controlled Perturbation for Voronoi Diagrams
Klein, Christian
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231231
en
oai:edoc.mpg.de:2318842012-09-1987:931
Scalable Multimedia Disk Scheduling
Elbassioni, Khaled
Mokbel, Mohamed F.
Aref, Walid G.
Kamel, Ibrahim
expertsonly
A new multimedia disk scheduling algorithm, termed Cascaded-SFC, is presented.
The Cascaded-SFC multimedia disk scheduler is applicable in environments where
multimedia data requests arrive with different quality of service (QoS)
requirements such as real-time deadline and user priority. Previous work on
disk scheduling has focused on optimizing the seek times and/or meeting the
real-time deadlines. The Cascaded-SFC disk scheduler provides a unified
framework for multimedia disk scheduling that scales with the number of
scheduling parameters. The general idea is based on modeling the multimedia
disk requests as points in multiple multi-dimensional sub-spaces, where each of
the dimensions represents one of the parameters (e.g., one dimension represents
the request deadline, another represents the disk cylinder number, and a third
dimension represents the priority of the request, etc.). Each multi-dimensional
sub-space represents a subset of the QoS parameters that share some common
scheduling characteristics. Then the multimedia disk scheduling problem reduces
to the problem of finding a linear order to traverse the multi-dimensional
points in each sub-space. Multiple space-filling curves are selected to fit the
scheduling needs of the QoS parameters in each sub-space. The orders in each
sub-space are integrated in a cascaded way to provide a total order for the
whole space. Comprehensive experiments demonstrate the efficiency and
scalability of the Cascaded-SFC disk scheduling algorithm over other disk
schedulers.
IEEE
2004
Conference-Paper
http://edoc.mpg.de/231884
urn:ISBN:0-7695-2065-0
20th International Conference on Data Engineering, ICDE 2004, IEEE, 498-509 (2004)
en
oai:edoc.mpg.de:2319722012-09-1987:931
A simpler linear time 2/3 - eps approximation for maximum weight matching
Pettie, Seth
Sanders, Peter
expertsonly
2004
Article
http://edoc.mpg.de/231972
Information Processing Letters, v.91, 271-276 (2004)
en
oai:edoc.mpg.de:2319842012-09-1987:931
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks
Funke, Stefan
Matijevic, Domagoj
Sanders, Peter
expertsonly
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 position of
radio stations in such a way that approximately
energy optimal paths can be retrieved in constant time, i.e.,
independent of the network size.
We put particular emphasis on actual implementations which
demonstrate that large constant factors hidden in the theoretical
analysis are not a big problem in practice.
University of Bologna
2004
Conference-Paper
http://edoc.mpg.de/231984
First International Workshop on Algorithms for Wireless and Mobile Networks, University of Bologna, 97-111 (2004)
en
oai:edoc.mpg.de:2319892012-09-1987:931
Online scheduling with bounded migration
Sanders, Peter
Sivadasan, Naveen
Skutella, Martin
Díaz, Josep
Karhumäki, Juhani
Lepistö, Arto
Sannella, Donald
expertsonly
Springer
2004
Conference-Paper
http://edoc.mpg.de/231989
urn:ISBN:3-540-22849-7
Automata, languages and programming : 31st International Colloquium, ICALP 2004, Springer, 1111-1122 (2004)
en
oai:edoc.mpg.de:2319962012-09-1987:931
Incremental Algorithms for Facility Location and k-Median
Fotakis, Dimitris
Albers, Susanne
Radzik, Tomasz
expertsonly
In the incremental versions of Facility Location and k-Median, the demand
points arrive one at a time and the algorithm must maintain a good solution by
either adding each new demand to an existing cluster or placing it in a new
singleton cluster. The algorithm can also merge some of the existing clusters
at any point in time. We present the first incremental algorithm for Facility
Location with uniform facility costs which achieves a constant performance
ratio and the first incremental algorithm for k-Median which achieves a
constant performance ratio using O(k) medians.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231996
urn:ISBN:3-540-23025-4
Algorithms – ESA 2004: 12th Annual European Symposium, Springer, 347-358 (2004)
en
oai:edoc.mpg.de:2320002012-09-1987:931
Algorithms for recognizing coordinates in two variables over UFD's
El Kahoui, M'hammed
Gutierrez, Jaime
expertsonly
ACM
2004
Conference-Paper
http://edoc.mpg.de/232000
urn:ISBN:1-58113-827-X
Proceedings of the 2004 International Symposium Symbolic and Algebraic Computation (ISSAC-04), ACM, 135-140 (2004)
en
oai:edoc.mpg.de:2320082012-09-1987:931
Engineering an External Memory Minimum Spanning Tree Algorithm
Dementiev, Roman
Sanders, Peter
Schultes, Dominik
Sibeyn, Jop F.
Lévy, Jean-Jacques
Mayr, Ernst W.
Mitchell, John C.
expertsonly
We develop an external memory algorithm for computing minimum spanning
trees. The algorithm is considerably simpler than previously known
external memory algorithms for this problem and needs a factor of at
least four less I/Os for realistic inputs.
Our implementation indicates that this algorithm processes graphs only
limited by the disk capacity of most current machines in time no more
than a factor 2--5 of a good internal algorithm with sufficient memory
space.
Kluwer
2004
Conference-Paper
http://edoc.mpg.de/232008
urn:ISBN:1-4020-8140-5
3rd IFIP International Conference on Theoretical Computer Science (TSC2004), Kluwer, 195-208 (2004)
en
oai:edoc.mpg.de:2320242012-09-1987:931
Topology matters: Smoothed competitiveness of metrical task systems
Schäfer, Guido
Sivadasan, Naveen
Diekert, Volker
Habib, Michel
expertsonly
Springer
2004
Conference-Paper
http://edoc.mpg.de/232024
urn:ISBN:3-540-21236-1
21st Annual Symposium on Theoretical Aspects of Computer Science (STACS-04), Springer, 489-500 (2004)
en
oai:edoc.mpg.de:2320262012-09-1987:931
An Efficient Implementation of a Joint Generation Algorithm
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Khachiyan, Leonid
Ribeiro, Celso C.
Martins, Simone L.
expertsonly
Let $\cC$ be an n-dimensional integral box, and $\pi$ be a monotone property
defined over the elements of $\cC$. We consider the problems of incrementally
generating jointly the families $\cF_{\pi}$ and $\cI(cF_{\pi})$ of all minimal
subsets satisfying property $\pi$ and all maximal subsets not satisfying
property $\pi$, when $\pi$ is given by a polynomial-time satisfiability oracle.
Problems of this type arise in many practical applications. It is known that
the above joint generation problem can be solved in incremental
quasi-polynomial time. In this paper, we present an efficient implementation of
this procedure. We present experimental results to evaluate our implementation
for a number of interesting monotone properties $\pi$.
Springer
2004
Conference-Paper
http://edoc.mpg.de/232026
urn:ISBN:3-540-22067-4
Experimental and efficient algorithms : Third International Workshop, WEA 2004, Springer, 114-128 (2004)
en
oai:edoc.mpg.de:2320272012-09-1987:931
Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Khachiyan, Leonid
Farach-Colton, Martin
expertsonly
Given a finite set $V$, and integers $k \geq 1$ and $r \geq 0$,
denote by $\AA(k,r)$ the class of hypergraphs $\cA \subseteq 2^V$
with $(k,r)$-bounded intersections, i.e. in which
the intersection of any $k$ distinct hyperedges has size at most $r$. We
consider the problem $MIS(\cA,\cI)$:
given a hypergraph $\cA$ and a subfamily $\cI \subseteq \In$,
of its maximal independent sets (MIS) $\In$, either extend this subfamily by
constructing a new MIS $I \in \In \setminus \cI$
or prove that there are no more MIS, that is $\cI = \In$.
We show that for hypergraphs $\cA\in\AA(k,r)$ with $k+r\le const$, problem
MIS$(\cA,\cI)$ is NC-reducible to problem MIS$(\cA',\emptyset)$ of generating a
single MIS for
a partial subhypergraph $\cA'$ of $\cA$. In particular, for this class of
hypergraphs, we get an incremental polynomial algorithm for generating all MIS.
Furthermore, combining this result with the currently known algorithms for
finding a single maximal independent set of a hypergraph, we obtain efficient
parallel algorithms for incrementally generating all MIS for hypergraphs in the
classes $\AA(1,c)$, $\AA(c,0)$, and $\AA(2,1)$, where $c$ is a constant. We
also show that,
for $\cA \in \AA(k,r)$, where $k+r\le const$, the problem of
generating all MIS of $\cA$ can be solved in incremental polynomial-time with
space polynomial only in the size of $\cA$.
Springer
2004
Conference-Paper
http://edoc.mpg.de/232027
urn:ISBN:3-540-21258-2
LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Springer, 488-498 (2004)
en
oai:edoc.mpg.de:2320302012-09-1987:931
Generating Paths and Cuts in Multi-pole (Di)graphs
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Khachiyan, Leonid
Makino, Kazuhisa
Fiala, Jirí
Koubek, Václav
Kratochvíl, Jan
expertsonly
Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given
a set of (source-sink) pairs of vertices of G, an important problem that
arises in the computation of network reliability is the enumeration of minimal
subsets of edges (arcs) that connect/disconnect all/at least one of the given
source-sink pairs of . For undirected graphs, we show that the enumeration
problems for conjunctions of paths and disjunctions of cuts can be solved in
incremental polynomial time. For directed graphs both of these problems are
NP-hard. We also give a polynomial delay algorithm for enumerating minimal sets
of arcs connecting respectively two given nodes s1 and s2 to a given vertex t1,
and each vertex of a given subset of vertices T2.
Springer
2004
Conference-Paper
http://edoc.mpg.de/232030
urn:ISBN:3-540-22823-3
Mathematical foundations of computer science 2004 : 29th International Symposium, MFCS 2004, Springer, 298-309 (2004)
en
oai:edoc.mpg.de:2320362012-09-1987:931
Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Albers, Susanne
Radzik, Tomasz
expertsonly
A minimal blocker in a bipartite graph $G$ is a minimal set of edges the
removal of which leaves no perfect matching in $G$. We give an explicit
characterization of the minimal blockers of a bipartite graph $G$. This result
allows us to obtain a polynomial
delay algorithm for finding all minimal blockers of a given bipartite graph.
Equivalently, this gives a polynomial delay algorithm for listing the
anti-vertices of the perfect matching polytope $P(G)=\{x\in
\RR^E~|~Hx=\be,~~x\geq 0\}$, where $H$ is the incidence matrix of $G$. We also
give similar generation algorithms for other related problems, including
generalized perfect matchings in bipartite graphs, and perfect 2-matchings in
general graphs.
Springer
2004
Conference-Paper
http://edoc.mpg.de/232036
urn:ISBN:3-540-23025-4
Algorithms – ESA 2004: 12th Annual European Symposium, Springer, 122-133 (2004)
en
oai:edoc.mpg.de:2320522012-09-1987:931
Controlled Perturbation for Voronoi Diagrams
Klein, Christian
expertsonly
Universität des Saarlandes
2004
Thesis
http://edoc.mpg.de/232052
en
oai:edoc.mpg.de:2378732012-09-1987:931
On the Hadwiger's conjecture for graph products
Chandran, L. Sunil
Sivadasan, Naveen
expertsonly
Max-Planck-Institut für Informatik
2004
Report
http://edoc.mpg.de/237873
en
oai:edoc.mpg.de:2378752012-09-1987:931
A comparison of polynomial evaluation schemes
Schmitt, Susanne
Fousse, Laurent
Max-Planck-Institut für Informatik
2004
Report
http://edoc.mpg.de/237875
en
oai:edoc.mpg.de:2378772012-09-1987:931
On scheduling with bounded migration
Sivadasan, Naveen
Sanders, Peter
Skutella, Martin
expertsonly
Max-Planck-Institut für Informatik
2004
Report
http://edoc.mpg.de/237877
en
oai:edoc.mpg.de:2378782012-09-1987:931
On algorithms for online topological ordering and sorting
Katriel, Irit
expertsonly
Max-Planck-Institut für Informatik
2004
Report
http://edoc.mpg.de/237878
en
oai:edoc.mpg.de:2378802012-09-1987:931
A simpler linear time 2/3-epsilon approximation
Sanders, Peter
Pettie, Seth
expertsonly
Max-Planck-Institut für Informatik
2004
Report
http://edoc.mpg.de/237880
en
oai:edoc.mpg.de:2378812012-09-1987:931
Filtering algorithms for the Same and UsedBy constraints
Beldiceanu, Nicolas
Katriel, Irit
Thiel, Sven
expertsonly
Max-Planck-Institut für Informatik
2004
Report
http://edoc.mpg.de/237881
en
oai:edoc.mpg.de:2791222012-09-1987:931
Earliest Arrival Flows with Multiple Sources
Rauf, Imran
expertsonly
This thesis addresses the earliest arrival flow problem, defined on dynamic networks with several sources and a single sink. A dynamic network is a directed graph with capacities and transit times on its edges. Given an integral supply specified at each source of a dynamic network, the problem is to send exactly the right amount of flow out of each source and into the sink, such that the amount of flow arriving at the sink by time $\theta$ is the
maximum possible for all $\theta \geq 0$. One obvious approach is to solve the easier static flow problem in a time-expanded network that contains one copy of the same network for each discrete time step. However, this approach is not practical in general due to the exponential size of time-expanded networks.
In \cite{FleischerSkutella}, Fleischer and Skutella describe a fully polynomial approximation scheme to solve this problem, while a special case when all transit times are zero, has been considered by Fleischer \cite{Fleischer01b}.
This thesis presents the first exact algorithm that avoids a time-expanded network, and solves a more general class of the earliest arrival flow problem in dynamic networks with multiple sources. The class is characterized by the
property that the total supply at the sources is equal to the value of the maximum dynamic flow in time bound $T$, where $T$ is the minimum time needed to evacuate all supplies.
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/279122
en
oai:edoc.mpg.de:2791342012-09-1987:931
The diamond operator - Implementation of exact real algebraic numbers
Schmitt, Susanne
Ganzha, Victor G.
Mayr, Ernst W.
Vorozhtsov, Evgenii V.
expertsonly
The LEDA number type real is extended by the diamond operator, which
allows to compute exactly with real algebraic numbers given as roots
of polynomials. The coefficients of these polynomials can be
arbitrary real algebraic numbers. The two important steps of
the implementation (isolating interval computation and approximation)
are described. Experiments with two other existing implementations of
real algebraic numbers (CORE, EXACUS) show that the implementation
is comparable with CORE and is more general than CORE or EXACUS.
Springer
2005
Conference-Paper
http://edoc.mpg.de/279134
urn:ISBN:3-540-28966-6
Computer Algebra in Scientific Computing, 8th International Workshop, CASC 2005, Springer, 355-366 (2005)
en
oai:edoc.mpg.de:2791412012-09-1987:931
Implementing Minimum Cycle Basis Algorithms
Mehlhorn, Kurt
Michail, Dimitrios
Nikoletseas, Sotiris
expertsonly
In this paper we consider the problem of computing a minimum cycle basis of an
undirected graph $G = (V,E)$ with $n$ vertices and $m$ edges. We describe an
efficient implementation of an $O(m^3 + mn^2\log n)$ algorithm presented
in~\cite{PINA95}. For sparse graphs this is the currently best known algorithm.
This algorithm's running time can be partitioned into two parts
with time $O(m^3)$ and $O( m^2n + mn^2 \log n)$ respectively.
Our experimental findings imply that the true bottleneck of a
sophisticated implementation is the $O( m^2 n + mn^2 \log n)$ part. A
straightforward implementation would require $\Omega(nm)$ shortest path
computations, thus we develop several heuristics in order to get a practical
algorithm. Our experiments show that in random graphs our techniques result in
a significant speedup.
Based on our experimental observations, we combine the two fundamentally
different approaches to compute a minimum cycle basis used
in~\cite{PINA95,KMMP04} and~\cite{HOR87,MATR02}, to obtain a new hybrid
algorithm with running time
$O( m^2 n^2 )$. The hybrid algorithm is very efficient in practice for random
dense unweighted graphs.
Finally, we compare these two algorithms with a number of previous
implementations for finding a minimum cycle basis in an undirected graph.
Springer
2005
Conference-Paper
http://edoc.mpg.de/279141
urn:ISBN:3-540-25920-1
Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005, Springer, 32-43 (2005)
en
oai:edoc.mpg.de:2791522012-09-1987:931
Energy efficient communication in ad hoc networks from user's and designer's perspective
Kesselmann, Alexander
Kowalski, Dariusz
Segal, Michael
expertsonly
2005
Article
http://edoc.mpg.de/279152
ACM SIGMOBILE Mobile Computing and Communications Review, v.9, 15-26 (2005)
en
oai:edoc.mpg.de:2791532012-09-1987:931
Deterministic Random Walks on Infinite Grids
Friedrich, Tobias
expertsonly
The rotor-router model is a simple deterministic analogue of random walk invented by Jim Propp. Instead of distributing chips to randomly chosen neighbors, it serves the neighbors in a fixed order. This thesis investigates how well this process simulates a random walk on an infinite two-dimensional grid. Independent of the starting configuration, at each time and on each vertex, the number of chips on this vertex deviates from the expected number of chips in the random walk model by at most a constant $c$. It is proved that $7.2 < c < 11.8$ in general.
Surprisingly, these bounds depend on the order in which the neighbors are served. It is also shown that in a generalized setting, where one just requires that no neighbor gets more than $\Delta$ chips more than another, there is also such a constant $c'$ with $7.7\Delta < c' < 26.9\Delta$.
Friedrich-Schiller-Universität Jena
2005
Thesis
http://edoc.mpg.de/279153
en
oai:edoc.mpg.de:2791582012-09-1987:931
A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs
Kavitha, Telikepalli
Mehlhorn, Kurt
Diekert, Volker
Durand, Bruno
expertsonly
Springer
2005
Conference-Paper
http://edoc.mpg.de/279158
urn:ISBN:3-540-24998-2
STACS 2005 : 22nd Annual Symposium on Theoretical Aspects of Computer Science, Springer, 654-665 (2005)
en
oai:edoc.mpg.de:2791622012-09-1987:931
Controlled Perturbation for Delaunay Triangulations
Funke, Stefan
Klein, Christian
Mehlhorn, Kurt
Schmitt, Susanne
expertsonly
Most geometric algorithms are idealistic in the sense that they are designed
for the Real-RAM model of computation and for inputs in general
position. Real inputs may be degenerate and floating point arithmetic is
only an approximation of real arithmetic.
Perturbation replaces an input by a nearby input which is (hopefully)
in general position and on which the algorithm can be run with floating point
arithmetic. Controlled perturbation as proposed by Halperin et al. calls for
more: control over the amount of perturbation needed for a given precision of
the floating point system. Or conversely, a control over the precision needed
for a given amount of perturbation. Halperin et al.~gave controlled
perturbation schemes for arrangements of polyhedral surfaces, spheres, and
circles. We extend their work and point out that controlled perturbation is a
general scheme for converting idealistic algorithms into algorithms which can
be executed with floating point arithmetic. We also show how to use controlled
perturbation in the context of randomized geometric algorithms without
deteriorating the running time. Finally, we give concrete schemes for planar
Delaunay triangulations and convex hulls and Delaunay triangulations in
arbitrary dimensions. We analyze the relation between the
perturbation amount and the precision of the floating point system. We also
report about experiments with a planar Delaunay diagram algorithm.
SIAM
2005
Conference-Paper
http://edoc.mpg.de/279162
urn:ISBN:0-89871-585-7
Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05), SIAM, 1047-1056 (2005)
en
oai:edoc.mpg.de:2791702012-09-1987:931
D-resultant and subresultants
El Kahoui, M'hammed
expertsonly
2005
Article
http://edoc.mpg.de/279170
Proceedings of the Amercian Mathematical Society, v.133, 2193-2199 (2005)
en
oai:edoc.mpg.de:2791712012-09-1987:931
UFDs with commuting linearly independent locally nilpotent derivations
El Kahoui, M'hammed
expertsonly
In this paper we study affine -UFDs of transcendence degree n without
nonconstant units, having n-1 commuting linearly independent locally nilpotent
-derivations. We prove in case n=2, and algebraically closed of characteristic
zero, that such rings are polynomial rings in two variables over . We then show
that the commuting derivations Conjecture is equivalent to a weak version of
the Abhyankar–Sathaye Conjecture.
2005
Article
http://edoc.mpg.de/279171
Journal of Algebra, v.289, 446-452 (2005)
en
oai:edoc.mpg.de:2791742012-09-1987:931
Angel, Devil, and King
Kutz, Martin
Pór, Attila
Wang, Lusheng
expertsonly
Springer
2005
Conference-Paper
http://edoc.mpg.de/279174
urn:ISBN:3-540-28061-8
Computing and Combinatorics : 11th Annual International Conference, COCOON 2005, Springer, 925-934 (2005)
en
oai:edoc.mpg.de:2791762012-09-1987:931
Energy-Aware Stage Illumination
Eisenbrand, Friedrich
Funke, Stefan
Karrenbauer, Andreas
Matijevic, Domagoj
expertsonly
Consider the following illumination problem: given a stage represented by
a line segment $\Stage$ and a set of lightsources represented by a set of
points $S$
in the plane, assign powers to the lightsources such that every point
on the stage receives a sufficient amount -- let's say one unit -- of light
while
minimizing the overall power consumption. By assuming that the amount of light
arriving
from a fixed lightsource decreases rapidly with the distance from the
lightsource, this becomes
an interesting optimization problem.
We propose to reconsider the classical illumination problems as known from
computational
geometry literature (e.g. \cite{u-agip-00}) under this light attenuation model.
This paper
examines the simple problem introduced above and presents different solutions,
based on
convex optimization, discretization and linear programming, as well as a purely
combinatorial approximation algorithm. Some experimental results are also
provided.
ACM
2005
Conference-Paper
http://edoc.mpg.de/279176
urn:ISBN:1-58113-991-8
Proceedings of the 21st Annual Symposium on Computational Geometry : (SCG05), ACM, 336-346 (2005)
en
oai:edoc.mpg.de:2791772012-09-1987:931
A Descartes algorithm for polynomials with bit-stream coefficients
Eigenwillig, Arno
Kettner, Lutz
Krandick, Werner
Mehlhorn, Kurt
Schmitt, Susanne
Wolpert, Nicola
Ganzha, Viktor G.
Mayr, Ernst W.
Vorozhtsov, Evenii V.
expertsonly
Springer
2005
Conference-Paper
http://edoc.mpg.de/279177
urn:ISBN:3-540-28966-6
Computer Algebra in Scientific Computing : 8th International Workshop, CASC 2005, Springer, 138-149 (2005)
en
oai:edoc.mpg.de:2791832012-09-1987:931
Better External Memory Suffix Array Construction
Dementiev, Roman
Kärkkäinen, Juha
Mehnert, Jens
Sanders, Peter
Demetrescu, Camil
Sedgewick, Robert
Tamassia, Roberto
expertsonly
Suffix arrays are a simple and powerful data structure for text processing
that can be used for full text indexes, data compression, and many
other applications in particular in bioinformatics.
However, so far it looked prohibitive to build suffix arrays
for huge inputs that do not fit into main memory.
This paper presents design, analysis, implementation, and
experimental evaluation of
several new and improved algorithms for suffix array construction.
The algorithms are asymptotically optimal in the worst case
or on the average. Our implementation can construct
suffix arrays for inputs of up to 4GByte in hours
on a low cost machine where
all previous implementations we are aware of would fail or take days.
We also present a simple and efficient external algorithm for checking
whether an array of indexes is a suffix array.
As a tool of possible independent interest we present a systematic way
to design, analyze, and implement \emph{pipelined}
algorithms.
SIAM
2005
Conference-Paper
http://edoc.mpg.de/279183
urn:ISBN:0-89871-596-2
Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO 2005), SIAM, 86-97 (2005)
en
oai:edoc.mpg.de:2791892012-09-1987:931
EXACUS: Efficient and exact algorithms for curves and surfaces
Berberich, Eric
Eigenwillig, Arno
Hemmer, Michael
Hert, Susan
Kettner, Lutz
Mehlhorn, Kurt
Reichel, Joachim
Schmitt, Susanne
Schömer, Elmar
Wolpert, Nicola
Brodal, Gerth S.
Leonardi, Stefano
expertsonly
We present the first open-source release of the
C\texttt{++} libraries of the \textsc{Exacus} project
of the Max-Planck-Institut f{\"u}r Informatik. Our
software computes arrangements of curves and curve
segments, and boolean operations on polygons bounded
by curve segments. We pursued the goals efficiency,
correctness, and completeness for all input cases,
implying robustness. We present the structure of the
libraries and their generic design. With our work we
contribute one milestone on the way towards a
systematic support of non-linear geometry in software
libraries.
Springer
2005
Conference-Paper
http://edoc.mpg.de/279189
urn:ISBN:3-540-29118-0
13th Annual European Symposium on Algorithms (ESA 2005), Springer, 155-166 (2005)
en
oai:edoc.mpg.de:2791952012-09-1987:931
New Constructions of (alpha, beta)-Spanners and Purely Additive Spanners
Baswana, Surender
Kavitha, Telikepalli
Mehlhorn, Kurt
Pettie, Seth
expertsonly
SIAM
2005
Conference-Paper
http://edoc.mpg.de/279195
urn:ISBN:0-89871-585-7
Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05), SIAM, 672-681 (2005)
en
oai:edoc.mpg.de:2791962012-09-1987:931
All-pairs nearly 2-approximate shortest paths in $O(n^2 \mathrm polylog n)$ time
Baswana, Surender
Goyal, Vishrut
Sen, Sandeep
Diekert, Volker
Durand, Bruno
expertsonly
Let $G=(V,E)$ be an unweighted undirected graph on $n$ vertices.
Let $\delta(u,v)$ denote the distance between vertices $u,v\inV$.
An algorithm is said to compute all-pairs $t$-approximate shortest
-paths/distances, for some $t\ge 1$, if for each pair of vertices
$u,v\in V$, the path/distance reported by the algorithm is not longer/greater
than $t\delta(u,v)$.\\
This paper presents two randomized algorithms for computing all-pairs nearly
2-approximate shortest distances.
The first algorithm takes expected $O(m^{2/3}n\log n + n^2)$ time, and for any
$u,v\in V$ reports distance no greater than $2\delta(u,v)+1$.
Our second algorithm requires expected $O(n^2\log^{3/2} n)$
time, and for any $u,v\in V$, reports distance bounded by $2\delta(u,v) + 3$.\\
This paper also presents the first expected $O(n^2)$ time algorithm to compute
all-pairs 3-approximate distances.
Springer
2005
Conference-Paper
http://edoc.mpg.de/279196
urn:ISBN:3-540-24998-2
STACS 2005 : 22nd Annual Symposium on Theoretical Aspects of Computer Science, Springer, 666-679 (2005)
en
oai:edoc.mpg.de:2791992012-09-1987:931
Why Spectral Retrieval Works
Bast, Holger
Majumdar, Debapriyo
Marchionini, Gary
Moffat, Alistair
Tait, John
Baeza-Yates, Ricardo
Ziviani, Nivio
expertsonly
We introduce the \emph{synonymy graph} as a new angle of looking at spectral
retrieval techniques, including latent semantic indexing (LSI) and its many
successors. The synonymy graph is defined for each pair of terms in the
collection, and our findings suggest that it is at the heart of what makes
spectral retrieval work in practice.
%
We show that LSI and many of its variants can be equivalently viewed as a
particular document expansion (not query expansion) process, where each term
effects the insertion of some other term if and only if the synonymy graph for
that term pair has a certain characteristic shape. We provide a simple,
parameterless algorithm for detecting that shape.
%
We point out inherent problems of every algorithm that bases its expansion
decisions merely on individual values of the synonymy graph, as done by almost
all existing methods. Our new algorithm overcomes these limitations, and it
consistently outperforms previous methods on a number of test collections.
%
Our synonymy graphs also shed light on the effectiveness of three fundamental
types of variations of the basic LSI scheme.
ACM
2005
Conference-Paper
http://edoc.mpg.de/279199
urn:ISBN:1-58113-881-4
Proceedings of SIGIR 2005 (SIGIR-05) : the Twenty-Eighth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, ACM, 11-18 (2005)
en
oai:edoc.mpg.de:2792032012-09-1987:931
Pareto-optimality in house allocation problems
Abraham, David
Mehlhorn, Kurt
Fleischer, Rudolf
Trippen, G.
expertsonly
Springer
2005
Conference-Paper
http://edoc.mpg.de/279203
urn:ISBN:3-540-24131-0
Algorithms and Computation: 15th International Symposium, ISAAC 2004, Springer, 3-15 (2005)
en
oai:edoc.mpg.de:2792042012-09-1987:931
Popular Matchings
Abraham, David
Irving, Robert
Mehlhorn, Kurt
Telikepalli, Kavitha
expertsonly
SIAM
2005
Conference-Paper
http://edoc.mpg.de/279204
urn:ISBN:0-89871-585-7
Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05), SIAM, 424-432 (2005)
en
oai:edoc.mpg.de:3143612012-09-1987:931
(Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram
Funke, Stefan
Malamatos, Theocharis
Matijevic, Domagoj
Wolpert, Nicola
Rappaport, David
expertsonly
For a given point set in Euclidean space we consider the problem of finding
(approximate) nearest neighbors of a query point but restricting only to
points that lie within a fixed cone with apex at the query point.
Apart from being a rather natural question to ask,
solutions to this problem have applications in surface reconstruction and
dimension detection.
We investigate the structure of the Voronoi diagram induced by this notion of
proximity and present
approximate and exact data structures for answering cone-restricted nearest
neighbor queries. In particular
we develop an approximate Voronoi diagram of size $O((n/\epsilon^d)\log
(1/\epsilon))$ that can be used
to answer cone-restricted nearest neighbor queries in $O(\log (n/\epsilon))$
time.
School of Computing, Queen's University
2006
Conference-Paper
http://edoc.mpg.de/314361
18th Canadian Conference on Computational Geometry, School of Computing, Queen's University, 23-26 (2006)
en
oai:edoc.mpg.de:3143672012-09-1987:931
New bounds for the Descartes method
Krandick, Werner
Mehlhorn, Kurt
expertsonly
We give a new bound for the number of recursive subdivisions in the Descartes
method for polynomial real root isolation. Our proof uses Ostrowski’s theory of
normal power series from 1950 which has so far been overlooked in the
literature. We combine Ostrowski’s results with a theorem of Davenport from
1985 to obtain our bound. We also characterize normality of cubic polynomials
by explicit conditions on their roots and derive a generalization of one of
Ostrowski’s theorems.
2006
Article
http://edoc.mpg.de/314367
Journal of Symbolic Computation, v.41, 49-66 (2006)
en
oai:edoc.mpg.de:3144032012-09-1987:931
Generating Randomized Roundings with Cardinality Constraints and Derandomizations
Doerr, Benjamin
Durand, Bruno
Thomas, Wolfgang
expertsonly
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. (FOCS 2002) for one global constraint
and the bipartite edge weight rounding problem.
Also for these special cases, our approach is the first that can be
derandomized. For the bipartite edge weight rounding problem, in addition, we
gain an factor run-time improvement for generating the randomized solution.
We also improve the current best result on the general problem of derandomizing
randomized roundings. Here we obtain a simple O(mnlog n) time algorithm that
works in the RAM model for arbitrary matrices with entries in . This improves
over the O(mn2 log(mn)) time solution of Srivastav and Stangier.
Springer
2006
Conference-Paper
http://edoc.mpg.de/314403
urn:ISBN:3-540-32301-5
STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Springer, 571-583 (2006)
en
oai:edoc.mpg.de:3144052012-09-1987:931
IO-Top-k: Index-Access Optimized Top-k Query Processing
Bast, Holger
Majumdar, Debapriyo
Schenkel, Ralf
Theobald, Martin
Weikum, Gerhard
Dayal, Umeshwar
Whang, Kyu-Young
Lomet, David B.
Alonso, Gustavo
Lohman, Guy M.
Kersten, Martin L.
Cha, Sang Kyun
Kim, Young-Kuk
expertsonly
Top-$k$ query processing is an important building block for ranked retrieval,
with applications ranging from text and data integration to distributed
aggregation of network logs and sensor data.
Top-$k$ queries operate on index lists for a query's elementary conditions
and aggregate scores for result candidates. One of the best implementation
methods in this setting is the family of threshold algorithms, which aim
to terminate the index scans as early as possible based on lower and upper
bounds for the final scores of result candidates. This procedure
performs sequential disk accesses for sorted index scans, but also has the
option
of performing random accesses to resolve score uncertainty. This entails
scheduling for the two kinds of accesses: 1) the prioritization of different
index lists in the sequential accesses, and 2) the decision on when to perform
random accesses and for which candidates.
The prior literature has studied some of these scheduling issues, but only for
each of the two access types in isolation.
The current paper takes an integrated view of the scheduling issues and develops
novel strategies that outperform prior proposals by a large margin.
Our main contributions are new, principled, scheduling methods based on a
Knapsack-related
optimization for sequential accesses and a cost model for random accesses.
The methods can be further boosted by harnessing probabilistic estimators for
scores,
selectivities, and index list correlations.
In performance experiments with three different datasets (TREC Terabyte, HTTP
server logs, and IMDB),
our methods achieved significant performance gains compared to the best
previously known methods.
ACM
2006
Conference-Paper
http://edoc.mpg.de/314405
urn:ISBN:1-59593-385-9
Proceedings of the 32nd International Conference on Very Large Data Bases, VLDB 2006, ACM, 475-486 (2006)
en
oai:edoc.mpg.de:3144202012-09-1987:931
Output-Sensitive Autocompletion Search
Bast, Holger
Mortensen, Christian Worm
Weber, Ingmar
Crestani, Fabio
Ferragina, Paolo
Sanderson, Mark
expertsonly
We consider the following autocompletion search scenario: imagine a user of a
search engine typing a query; then with every keystroke display those
completions of the last query word that would lead to the best hits, and also
display the best such hits. The following problem is at the core of this
feature: for a fixed document collection, given a set D of documents, and an
alphabetical range W of words, compute the set of all word-in-document pairs (w
,d) from the collection such that w ∈W and d∈D. We present a new data structure
with the help of which such autocompletion queries can be processed, on the
average, in time linear in the input plus output size, independent of the size
of the underlying document collection. At the same time, our data structure
uses no more space than an inverted index. Actual query processing times on a
large test collection correlate almost perfectly with our theoretical bound.
Springer
2006
Conference-Paper
http://edoc.mpg.de/314420
urn:ISBN:978-3-540-45774-9
String Processing and Information Retrieval : 13th International Conference, SPIRE 2006, Springer, 150-162 (2006)
en
oai:edoc.mpg.de:3144252012-09-1987:931
Sampling Rooted 3-Connected Planar Graphs in Deterministic Polynomial Time
Johannsen, Daniel
expertsonly
In this thesis an algorithm for sampling rooted 3-connected planar graphs (c-nets) in deterministic polynomial time is presented. The algorithm is based on a decomposition strategy for c-nets, which is formulated as a system of bijections between classes of c-nets parameterized by the number of vertices, faces, and edges on the outer face. This system is then used in three ways: First, as system of recursive equations to derive the sizes of above classes by using an algorithm based on dynamic programming. Second, as system of equations of generating functions to derive an algebraic generating function and a single parameter recursion formula for c-nets. Third, as composition scheme to sample c-nets uniformly at random with the recursive method of sampling. The thesis is based on the paper \emph{A Direct Decomposition of 3-connected Planar Graphs} by Manuel Bodirsky, Clemens Gr{\"o}pl, Mihyun Kang and the author~\cite{3connplanar} and extends it by the parameter for the number of edges and a full proof of the decomposition.
Humboldt-Universität zu Berlin
2006
Thesis
http://edoc.mpg.de/314425
en
oai:edoc.mpg.de:3144272012-09-1987:931
Type Less, Find More: Fast Autocompletion Search with a Succinct Index
Bast, Holger
Weber, Ingmar
Efthimiadis, Efthimis N.
Dumais, Susan
Hawking, David
Järvellin, Kalervo
expertsonly
We consider the following full-text search autocompletion feature. Imagine a
user of a search engine typing a query. Then with every letter being typed, we
would like an instant display of completions of the last query word which would
lead to good hits. At the same time, the best hits for any of these completions
should be displayed. Known indexing data structures that apply to this problem
either incur large processing times for a substantial class of queries, or they
use a lot of space. We present a new indexing data structure that uses no more
space than a state-of-the-art compressed inverted index, but with 10 times
faster query processing times. Even on the large TREC Terabyte collection,
which comprises over 25 million documents, we achieve, on a single machine and
with the index on disk, average response times of one tenth of a second. We
have built a full-fledged, interactive search engine that realizes the proposed
autocompletion feature combined with support for proximity search,
semi-structured (XML) text, subword and phrase completion, and semantic tags.
ACM
2006
Conference-Paper
http://edoc.mpg.de/314427
urn:ISBN:1-59593-369-7
SIGIR 2006: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, ACM, 364-371 (2006)
en
oai:edoc.mpg.de:3144302012-09-1987:931
The Space Complexity of Pass-Efficient Algorithms for Clustering
Chang, Kevin L.
Kannan, Ravi
expertsonly
We present multiple pass streaming algorithms for a basic clustering problem
for massive data sets. If our algorithm is allotted 2l passes, it will produce
an approximation with error at most ε using Õ(k3/ε2/l) bits of memory, the most
critical resource for streaming computation. We demonstrate that this tradeoff
between passes and memory allotted is intrinsic to the problem and model of
computation by proving lower bounds on the memory requirements of any l pass
randomized algorithm that are nearly matched by our upper bounds. To the best
of our knowledge, this is the first time nearly matching bounds have been
proved for such an exponential tradeoff for randomized computation.In this
problem, we are given a set of n points drawn randomly according to a mixture
of k uniform distributions and wish to approximate the density function of the
mixture. The points are placed in a datastream (possibly in adversarial order),
which may only be read sequentially by the algorithm. We argue that this
models, among others, the datastream produced by a national census of the
incomes of all citizens.
ACM / Siam
Copyright 2006 ACM. Permission to make digital or hard copies of part or all
of this work for personal or classroom use is granted without fee provided that
copies are not made or distributed for profit or commercial advantage and that
copies bear this notice and the full citation on the first page. Copyrights for
components of this work owned by others than ACM must be honored. Abstracting
with credit is permitted. To copy otherwise, to republish, to post on servers
or to redistribute to lists, requires prior specific permission and/or a fee.
2006
Conference-Paper
http://edoc.mpg.de/314430
urn:ISBN:0-89871-605-5
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'06, ACM / Siam, 1157-1166 (2006)
en
oai:edoc.mpg.de:3144322012-09-1987:931
A New Approximation Algorithm for Multidimensional Rectangle Tiling
Paluch, Katarzyna
Asano, Tetsuo
expertsonly
Springer
2006
Conference-Paper
http://edoc.mpg.de/314432
urn:ISBN:978-3-540-49694-6
Algorithms and Computation : 17th International Symposium, ISAAC 2006, Springer, 712-721 (2006)
en
oai:edoc.mpg.de:3144432012-09-1987:931
Unbiased Matrix Rounding
Doerr, Benjamin
Friedrich, Tobias
Klein, Christian
Osbild, Ralf
Arge, Lars
Freivalds, Rusins
notspecified
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 with applications in many
fields, in particular, statistics.
We improve earlier solutions of different authors in two ways. For rounding $m
\times n$ matrices, we reduce the runtime from $O( (m n)^2 ) $ to $O(m n \log(m
n))$. Second, our roundings also have a rounding error of less than one in all
initial intervals of rows and columns. Consequently, arbitrary intervals have
an error of at most two. This is particularly useful in the statistics
application of controlled rounding.
The same result can be obtained via (dependent) randomized rounding. This has
the additional advantage that the rounding is unbiased, that is, for all
entries $y_{ij}$ of our rounding, we have $E(y_{ij}) = x_{ij}$, where $x_{ij}$
is the corresponding entry of the input matrix.
Springer
2006
Conference-Paper
http://edoc.mpg.de/314443
urn:ISBN:978-3-540-35753-7
Algorithm theory - SWAT 2006 : 10th Scandinavian Workshop on Algorithm Theory, Springer, 102-112 (2006)
en
oai:edoc.mpg.de:3144482012-09-1987:931
Deterministic Rendezvous in Graphs
Dessmark, Anders
Fraigniaud, Pierre
Kowalski, Dariusz
Pelc, Andrzej
expertsonly
Two mobile agents having distinct identifiers and located in nodes of an
unknown anonymous connected graph, have to meet at some node of the graph. We
seek fast deterministic algorithms for this rendezvous problem, under two
scenarios: simultaneous startup, when both agents start executing the algorithm
at the same time, and arbitrary startup, when starting times of the agents are
arbitrarily decided by an adversary. The measure of performance of a rendezvous
algorithm is its cost: for a given initial location of agents in a graph, this
is the number of steps since the startup of the later agent until rendezvous is
achieved. We first show that rendezvous can be completed at cost O(n + log l)
on any n-node tree, where l is the smaller of the two identifiers, even with
arbitrary startup. This complexity of the cost cannot be improved for some
trees, even with simultaneous startup. Efficient rendezvous in trees relies on
fast network exploration and cannot be used when the graph contains cycles. We
further study the simplest such network, i.e., the ring. We prove that, with
simultaneous startup, optimal cost of rendezvous on any ring is Θ(D log l),
where D is the initial distance between agents. We also establish bounds on
rendezvous cost in rings with arbitrary startup. For arbitrary connected
graphs, our main contribution is a deterministic rendezvous algorithm with cost
polynomial in n, τ and log l, where τ is the difference between startup times
of the agents. We also show a lower bound Ω (n2) on the cost of rendezvous in
some family of graphs. If simultaneous startup is assumed, we construct a
generic rendezvous algorithm, working for all connected graphs, which is
optimal for the class of graphs of bounded degree, if the initial distance
between agents is bounded.
2006
Article
http://edoc.mpg.de/314448
urn:ISSN:0178-4617
Algorithmica, v.46, 69-96 (2006)
en
oai:edoc.mpg.de:3144512012-09-1987:931
Algorithmic methods for investigating equilibria in epidemic modeling
Brown, Christopher
El Kahoui, M'hammed
Novotni, Dominik
Weber, Andreas
expertsonly
The calculation of threshold conditions for models of infectious diseases is of
central importance for developing vaccination policies. These models are often
coupled systems of ordinary differential equations, in which case the
computation of threshold conditions can be reduced to the question of stability
of the disease-free equilibrium. This paper shows how computing threshold
conditions for such models can be done fully algorithmically using quantifier
elimination for real closed fields and related simplification methods for
quantifier-free formulas. Using efficient quantifier elimination techniques for
special cases that have been developed by Weispfenning and others, we can also
compute whether there are ranges of parameters for which sub-threshold endemic
equilibria exist.
2006
Article
http://edoc.mpg.de/314451
Journal of Symbolic Computation, v.41, 1157-1173 (2006)
en
oai:edoc.mpg.de:3144522012-09-1987:931
Hole Detection or: "How Much Geometry Hides in Connectivity?"
Funke, Stefan
Klein, Christian
Amenta, Nina
Cheong, Otfried
expertsonly
Wireless sensor networks typically consist of small, very simple network nodes
without any positioning device like GPS.
After an initialization phase, the nodes know with whom they can talk directly,
but have no idea about their relative geographic locations.
We examine how much geometry information is nevertheless hidden in the
communication graph of the network:
Assuming that the connectivity is determined by the well-known unit-disk graph
model, we prove that using an extremely simple linear-time algorithm
one can identify nodes on the boundaries of holes of the network. That is,
there is enough geometry information hidden in the connectivity structure
to identify topological features -- in our example the holes in the network.
While the theoretical analysis turns out to be quite conservative, an actual
implementation shows that the algorithm works well under less stringent
conditions.
ACM
2006
Conference-Paper
http://edoc.mpg.de/314452
urn:ISBN:1-59593-340-9
Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06, ACM, 377-385 (2006)
en
oai:edoc.mpg.de:3144612012-09-1987:931
Exact, Efficient and Complete Arrangement Computation for Cubic Curves
Eigenwillig, Arno
Kettner, Lutz
Schömer, Elmar
Wolpert, Nicola
expertsonly
The Bentley-Ottmann sweep-line method can compute the
arrangement of planar curves, provided a number of geometric
primitives operating on the curves are available. We discuss the
reduction of the primitives to the analysis of curves and curve pairs,
and describe efficient realizations of these analyses
for planar algebraic curves of degree three or less. We
obtain a \emph{complete}, \emph{exact}, and \emph{efficient\/}
algorithm for computing arrangements of cubic curves.
Special cases of cubic curves are
conics as well as implicitized cubic splines and B\'ezier curves.
The algorithm is \emph{complete\/} in that it handles all possible
degeneracies such as tangential intersections and singularities.
It is \emph{exact\/} in that it provides the mathematically correct
result. It is \emph{efficient\/} in that it can handle hundreds of
curves with a quarter million of segments in the final arrangement.
The algorithm has been implemented in C\texttt{++} as an \textsc{Exacus}
library called \textsc{CubiX}.
Copyright © 2005 Elsevier B.V. All rights reserved.
This article has been published in Computational Geometry 35(1-2), August 2006,
Pages 36-73.
2006
Article
http://edoc.mpg.de/314461
urn:ISSN:0925-7721
Computational Geometry, v.35, 36-73 (2006)
en
oai:edoc.mpg.de:3144652012-09-1987:931
Speeding Up Evolutionary Algorithms Through Restricted Mutation Operators
Doerr, Benjamin
Hebbinghaus, Nils
Neumann, Frank
Runarsson, Thomas Ph.
Beyer, Hans G.
Burke, Edmund
Merelo-Guervós, Juan J.
Whitley, L. Darrell
Yao, Xin
expertsonly
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 evolutionary algorithms with a restricted
operator that are much smaller than the best upper bounds for the general case.
It turns out that a plateau that both algorithms have to cope with is left
faster by the new algorithm. In addition, we present a lower bound for the
unrestricted algorithm which shows that the restricted operator speeds up
computation by at least a linear factor.
Springer
2006
Conference-Paper
http://edoc.mpg.de/314465
urn:ISBN:978-3-540-38990-3
Parallel Problem Solving from Nature - PPSN IX, 9th International Conference, Springer, 978-987 (2006)
en
oai:edoc.mpg.de:3144922012-09-1987:931
Deterministic Random Walks on the Two-Dimensional Grid
Doerr, Benjamin
Friedrich, Tobias
Asano, Tetsuo
expertsonly
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 machine. Roughly speaking, we show that on
the two-dimensional grid, the Propp machine always has the same number of
tokens on a node as does the random walk in expectation, apart from an additive
error of less than eight. This constant is independent of the total number of
tokens and the runtime of the two processes. However, we also show that it
makes a difference whether the Propp machine serves the neighbors in a circular
or non-circular order.
Springer
2006
Conference-Paper
http://edoc.mpg.de/314492
urn:ISBN:978-3-540-49694-6
Algorithms and Computation : 17th International Symposium, ISAAC 2006, Springer, 474-483 (2006)
en
oai:edoc.mpg.de:3145042012-09-1987:931
Unbiased Rounding of Rational Matrices
Doerr, Benjamin
Klein, Christian
Arun-Kumar, S.
Garg, Naveen
expertsonly
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 scheduling and in statistics.
Here, it often is also desirable to round each entry randomly such that the
probability of rounding it up equals its fractional part.
This is known as unbiased rounding in statistics and as randomized rounding in
computer science.
We show how to compute such an unbiased rounding of an $m \times n$ matrix in
expected time $O(m n q^2)$, where $q$ is the common denominator of the matrix
entries.
We also show that if the denominator can be written as $q=\prod_{i=1}^\ell q_i$
for some integers $q_i$, the expected runtime can be reduced to $O(m n
\sum_{i=1}^\ell q_i^2)$.
Our algorithm can be derandomised efficiently using the method of conditional
probabilities.
Our roundings have the additional property that the errors in all initial
intervals of rows and columns are less than one.
Springer
2006
Conference-Paper
http://edoc.mpg.de/314504
urn:ISBN:978-3-540-49994-7
FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science: 26th International Conference, Springer, 200-211 (2006)
en
oai:edoc.mpg.de:3145312012-09-1987:931
A computational study of external memory BFS algorithms
Ajwani, Deepak
Dementiev, Roman
Meyer, Ulrich
expertsonly
ACM / Siam
2006
Conference-Paper
http://edoc.mpg.de/314531
urn:ISBN:0-89871-605-5
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'06, ACM / Siam, 601-610 (2006)
en
oai:edoc.mpg.de:3145422012-09-1987:931
Almost Tight Recursion Tree Bounds for the Descartes Method
Eigenwillig, Arno
Sharma, Vikram
Yap, Chee K.
Dumas, Jean-Guillaume
expertsonly
We give a unified ("basis free") framework for the Descartes method for real
root isolation of square-free real polynomials. This framework encompasses the
usual Descartes' rule of sign method for polynomials in the power basis as well
as its analog in the Bernstein basis. We then give a new bound on the size of
the recursion tree in the Descartes method for polynomials with real
coefficients. Applied to polynomials $A(X) = \sum_{i=0}^n a_iX^i$ with integer
coefficients $\abs{a_i} < 2^L$, this yields a bound of $O(n(L + \log n))$ on
the size of recursion trees. We show that this bound is tight for $L =
\Omega(\log n)$, and we use it to derive the best known bit complexity bound
for the integer case.
ACM
Copyright (c) ACM, 2006. This is the authors' version of the work. It is posted
here by permission of ACM for your personal use. Not for redistribution. The
definitive version was published in the Proceedings of the 2006 International
Symposium on Symbolic and Algebraic Computation (ISSAC 2006),
http://doi.acm.org/10.1145/1145768.1145786
2006
Conference-Paper
http://edoc.mpg.de/314542
urn:ISBN:1-59593-276-3
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation, ACM, 71-78 (2006)
en
oai:edoc.mpg.de:3145512012-09-1987:931
A Goal-Directed Shortest Path Algorithm Using Precomputed Cluster Distances
Maue, Jens
expertsonly
This thesis introduces a new acceleration heuristic for shortest path queries, called the PCD algorithm (\textbf{P}recomputed \textbf{C}luster \textbf{D}istances). PCD precomputes shortest path distances between the partitions of the input graph, which can be obtained by any graph partitioning method. Since the number of partitions can be varied between one and the number of nodes, the method presents an interpolation between all pairs and ordinary single source single target shortest path search.
This allows a flexible trade-off between preprocessing time and space on the one hand and query time on the other, allowing significant speedups even for a sublinear amount of extra space. The method can be applied to arbitrary graphs with non-negative edge weights and does not afford a layout. Experiments on large street networks with a suitable clustering method are shown to yield average speedups of up to 114.9 for PCD as a stand-alone method.
Furthermore, the algorithm's space-efficiency, simplicity, and goal-directed behaviour make PCD an alternative method to provide other acceleration heuristics with goal-direction.
Universität des Saarlandes
2006
Thesis
http://edoc.mpg.de/314551
en
oai:edoc.mpg.de:3145532012-09-1987:931
Combinatorial Approaches to Trunk Packing
Reichel, Joachim
expertsonly
Universität des Saarlandes
2006
PhD-Thesis
http://edoc.mpg.de/314553
en
oai:edoc.mpg.de:3145672012-09-1987:931
Analysis of Real Algebraic Plane Curves
Kerber, Michael
expertsonly
This work describes a new method to compute geometric properties of a real algebraic plane curve of arbitrary degree. These properties contain the topology of the curve as well as the location of singular points and vertical asymptotes. The algorithm is based on the Bitstream Descartes method (Eigenwillig et al.: "A Descartes Algorithm for Polynomials with Bit-Stream Coefficients", LNCS~3718), which computes exact information about the real roots of a polynomial from approximate coefficients. For symbolic calculations with algebraic numbers, especially for counting distinct real roots, it uses Sturm-Habicht sequences (Gonzalez-Vega et al.: "Sturm-Habicht Sequences
\ldots", in: Caviness, Johnson(eds.): {\it Quantifier Elimination\ldots}, Springer, 1998), which are related to polynomial remainder sequences. Our work explains how to combine these methods to reduce the amount of symbolic calculations without losing exactness.\par
The geometry of the curve is computed with respect to the predetermined coordinate system. The algorithm changes coordinates in some situations to bring the curve into a generic position, but a new technique transports the computed information back into the original system efficiently. The conditions for a generic position of the curve are less restrictive than in other approaches and can be checked more efficiently during the analysis.\par
The algorithm has been implemented as part of the software library EXACUS. This work presents comprehensive experimental results. They show that the new approach consistently outperforms the method by Seidel and Wolpert ("On the Exact Computation \ldots", SCG 2005, 107--115) and the frequently cited algorithm of Gonzalez-Vega and Necula ("Efficient Topology Determination \ldots", {\it Comp.\ Aided Design} {\bf 19} (2002) 719--743). We therefore claim that our algorithm reflects the state-of-the-art in the resultant-based analysis of algebraic curves.
Universität des Saarlandes
2006
Thesis
http://edoc.mpg.de/314567
en
oai:edoc.mpg.de:3146062012-09-1987:931
Discrepancy of Symmetric Products of Hypergraphs
Doerr, Benjamin
Gnewuch, Michael
Hebbinghaus, Nils
expertsonly
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 $c$-color discrepancy of such products.
In particular, we show that the bound ${disc}(\Delta^d {\mathcal H},2) \le
{disc}({\mathcal H},2)$ proven for all $d$ in [B. Doerr, A. Srivastav, and P.
Wehr, Discrepancy of {C}artesian products of arithmetic progressions, Electron.
J. Combin. 11(2004), Research Paper 5, 16 pp.] cannot be extended to more than
$c = 2$ colors. In fact, for any $c$ and $d$ such that $c$ does not divide
$d!$, there are hypergraphs having arbitrary large discrepancy and
${disc}(\Delta^d {\mathcal H},c) = \Omega_d({disc}({\mathcal H},c)^d)$. Apart
from constant factors (depending on $c$ and $d$), in these cases the symmetric
product behaves no better than the general direct product ${\mathcal H}^d$,
which satisfies ${disc}({\mathcal H}^d,c) = O_{c,d}({disc}({\mathcal H},c)^d)$.
2006
Article
http://edoc.mpg.de/314606
urn:ISSN:1077-8926
The Electronic Journal of Combinatorics, v.13, 1-12 (2006)
en
oai:edoc.mpg.de:3146292012-09-1987:931
Minimum Cycle Basis, Algorithms & Applications
Michail, Dimitrios
expertsonly
Universität des Saarlandes
2006
PhD-Thesis
http://edoc.mpg.de/314629
en
oai:edoc.mpg.de:3146412012-09-1987:931
The Interval Liar Game
Doerr, Benjamin
Lengler, Johannes
Steurer, Daniel
Asano, Tetsuo
expertsonly
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 realistic seems the model
that
all faults occur in some small time interval.
Like previous work, our problem can best be modelled as a two-player perfect
information game, in which one player (“Paul”) has to guess a number x from
{1, . . . , n} using Yes/No-questions, which the second player (“Carole”) has to
answer truthfully apart from few lies. In our setting, all lies have to be in a
consecutive
set of k rounds.
We show that Paul needs roughly log n + log log n + k rounds to determine the
number, which is only k more than the case of just one single lie.
Springer
2006
Conference-Paper
http://edoc.mpg.de/314641
urn:ISBN:978-3-540-49694-6
Algorithms and Computation : 17th International Symposium, ISAAC 2006, Springer, 318-327 (2006)
en
oai:edoc.mpg.de:3146512012-09-1987:931
Computing Steiner Minimal Trees in Hamming Metric
Althaus, Ernst
Naujoks, Rouven
expertsonly
ACM / Siam
2006
Conference-Paper
http://edoc.mpg.de/314651
urn:ISBN:0-89871-605-5
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'06, ACM / Siam, 172-181 (2006)
en
oai:edoc.mpg.de:3146692012-09-1987:931
An O(n^2.75) algorithm for online topological ordering
Ajwani, Deepak
Friedrich, Tobias
Meyer, Ulrich
Arge, Lars
Freivalds, Rusins
expertsonly
We present a simple algorithm which maintains the topological order of a
directed acyclic graph with $n$ nodes under an online edge insertion sequence
in $\O(n^{2.75})$ time, independent of the number of edges $m$ inserted. For
dense DAGs, this is an improvement over the previous best result of
$\O(\min\{m^{\frac{3}{2}} \log{n}, m^{\frac{3}{2}} + n^2 \log{n}\})$ by Katriel
and Bodlaender. We also provide an empirical comparison of our algorithm with
other algorithms for online topological sorting.
Springer
2006
Conference-Paper
http://edoc.mpg.de/314669
urn:ISBN:978-3-540-35753-7
Algorithm theory - SWAT 2006 : 10th Scandinavian Workshop on Algorithm Theory, Springer, 53-64 (2006)
en
oai:edoc.mpg.de:3444042012-09-1987:931
A Method for Obtaining Randomized Algorithms with Small Tail Probabilities
Alt, Helmut
Guibas, L.
Mehlhorn, Kurt
Karp, Richard M.
Wigderson, A.
expertsonly
We study strategies for converting randomized algorithms of the Las Vegas type
into randomized algorithms with small tail probabilities.
1996
Article
http://edoc.mpg.de/344404
urn:ISSN:0178-4617
Algorithmica, v.16, 543-547 (1996)
en
oai:edoc.mpg.de:3444292012-09-1987:931
From Algorithms to Working Programs: On the Use of Program Checking in LEDA
Mehlhorn, Kurt
Näher, Stefan
Brim, Lubos
Gruska, Jozef
Zlatuska, Jirí
expertsonly
Springer
1998
Conference-Paper
http://edoc.mpg.de/344429
urn:ISBN:3-540-64827-5
Mathematical foundations of computer science (MFCS-98) : 23rd international symposium, Springer, 84-93 (1998)
en
oai:edoc.mpg.de:3444322012-09-1987:931
Average-Case Complexity of Shortest-Paths Problems in the Vertex-Potential Model
Cooper, Colin
Frieze, Alan M.
Mehlhorn, Kurt
Priebe, Volker
expertsonly
We study the average-case complexity of shortest-paths problems in the
vertex-potential model. The vertex-potential model is a family of probability
distributions on complete directed graphs with arbitrary real edge lengths but
without negative cycles. We show that on a graph with $n$ vertices and with
respect to this model, the single-source shortest-paths problem can be solved
in $O(n^2)$ expected time, and the all-pairs shortest-paths problem can be
solved in $O(n^2 \log n)$ expected time.
2000
Article
http://edoc.mpg.de/344432
urn:ISSN:1042-9832
Random Structures & Algorithms, v.16, 33-46 (2000)
en
oai:edoc.mpg.de:3444342012-09-1987:931
LEDA-SM : Extending LEDA to Secondary Memory
Crauser, Andreas
Mehlhorn, Kurt
Vitter, Jeffrey S.
Zaroliagis, Christos D.
expertsonly
During the last years, many software libraries for \emph{in-core} computation
have been developed. Most internal memory algorithms perform very badly when
used in an \emph{external memory} setting. We introduce LEDA-SM that extends
the LEDA-library~\cite{LEDAbook} towards secondary memory computation. LEDA-SM
uses I/O-efficient algorithms and data structures that do not suffer from the
so called {\em I/O bottleneck}. LEDA is used for in-core computation. We
explain the design of LEDA-SM and report on performance results.
Springer
1999
Conference-Paper
http://edoc.mpg.de/344434
urn:ISBN:3-540-66427-0
Algorithm engineering (WAE-99) : 3rd International Workshop, WAE'99, Springer, 228-242 (1999)
en
oai:edoc.mpg.de:3444372012-09-1987:931
A correctness certificate for the Stoer-Wagner min-cut algorithm
Arikati, Srinivasa Rao
Mehlhorn, Kurt
expertsonly
The Stoer–Wagner algorithm computes a minimum cut in a weighted undirected
graph. The algorithm works in n−1 phases, where n is the number of nodes of G.
Each phase takes time O(m+nlogn), where m is the number of edges of G, and
computes a pair of vertices s and t and a minimum cut separating s and t. We
show how to extend the algorithm such that each phase also computes a maximum
flow from s to t. The flow is computed in O(m) additional time and certifies
the cut computed in the phase.
1999
Article
http://edoc.mpg.de/344437
Information Processing Letters, v.70, 251-254 (1999)
en
oai:edoc.mpg.de:3444412012-09-1987:931
Geometric Computing with CGAL and LEDA
Mehlhorn, Kurt
Schirra, Stefan
Laurent, Pierre-Jean
Sablonnière, Paul
Schumaker, Larry L.
expertsonly
Vanderbilt University Press
2000
Conference-Paper
http://edoc.mpg.de/344441
urn:ISBN:0-8265-1356-1
Curve and surface design, Saint-Malo 1999, Vanderbilt University Press, 277-286 (2000)
en
oai:edoc.mpg.de:3444482012-09-1987:931
LOOK - a Lazy Object-Oriented Kernel for Geometric Computation
Funke, Stefan
Mehlhorn, Kurt
expertsonly
ACM
2000
Conference-Paper
http://edoc.mpg.de/344448
urn:ISBN:1-58113-224-7
Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00), ACM, 156-165 (2000)
en
oai:edoc.mpg.de:3444512012-09-1987:931
A Polynomial-Time Fragment of Dominance Constraints
Koller, Alexander
Mehlhorn, Kurt
Niehren, Joachim
expertsonly
Dominance constraints are a logical language for describing trees that is
widely used in computational linguistics. Their general satisfiability problem
is known to be NP-complete. Here we identify \emph{normal} dominance
constraints, a natural fragment whose satisfiability problem we show to be in
polynomial time. We present a quadratic satisfiability algorithm and use it in
another algorithm that enumerates solutions efficiently. Our result is useful
for various applications of dominance constraints and related formalisms.
Morgan Kaufmann
2000
Conference-Paper
http://edoc.mpg.de/344451
urn:ISBN:1-558-60729-3
Proceedings of the 38th Annual Meeting of the Association of Computational Linguistics (ACL-00), Morgan Kaufmann, 368-375 (2000)
en
oai:edoc.mpg.de:3444532012-09-1987:931
Implementation of $O(nm \log n)$ weighted matchings: The power of data structures
Mehlhorn, Kurt
Schäfer, Guido
Näher, Stefan
Wagner, Dorothea
expertsonly
We describe the implementation of an $O(nm \log n)$ algorithm
for weighted matchings in general graphs. The algorithm is a variant of the
algorithm of Galil, Micali, and Gabow and requires the use of concatenable
priority queues. No previous implementation had a worst-case guarantee of
$O(nm \log n)$. We compare our implementation to the experimentally fastest
implementation (called Blossom IV) due to Cook and Rohe; Blossom IV is an
implementation of Edmonds' algorithm and has a running time no better than
$O(n^3)$. Blossom IV requires only very simple data structures.
Our experiments show that our new implementation is competitive
to Blossom IV.
Springer
2000
Conference-Paper
http://edoc.mpg.de/344453
urn:ISBN:3-540-42512-8
4th International Workshop on Algorithm Engineering, Springer, 23-38 (2000)
en
oai:edoc.mpg.de:3444562012-09-1987:931
Traveling Salesman-Based Curve Reconstruction in Polynomial Time
Althaus, Ernst
Mehlhorn, Kurt
expertsonly
An instance of the curve reconstruction problem is a finite sample set $V$ of an
unknown curve $\gamma$. The task is to connect the points in $V$ in the
order in which they lie on $\gamma$. Giesen~\cite{Giesen:TSP} showed recently
that the Traveling Salesman tour of $V$ solves the reconstruction problem under
fairly week assumptions on $\gamma$ and $V$. We extend his result along three
dimensions. We weaken the assumptions, give an alternate proof, and
show that in the context of curve reconstruction,
the Traveling Salesman tour can be constructed in polynomial time.
2001
Article
http://edoc.mpg.de/344456
urn:ISSN:0097-5397
SIAM Journal on Computing, v.31, 27-66 (2001)
en
oai:edoc.mpg.de:3444572012-09-1987:931
CNOP - {A} Package for Constrained Network Optimization
Mehlhorn, Kurt
Ziegelmann, Mark
Buchsbaum, Adam L.
Snoeyink, Jack
expertsonly
We present a generic package for resource constrained network optimization
problems. We illustrate the flexibility and the use of our package by solving
four applications: route planning, curve approximation, minimum cost
reliability constrained spanning trees and the table layout problem.
Springer
2001
Conference-Paper
http://edoc.mpg.de/344457
urn:ISBN:3-540-42560-8
Algorithm engineering and experimentation (ALENEX-01) :Third International Workshop ALENEX 2001 ; revised papers, Springer, 17-31 (2001)
en
oai:edoc.mpg.de:3445052012-09-1987:931
Introduction
Mehlhorn, Kurt
Näher, Stefan
Nievergelt, Jurg
expertsonly
1994
Article
http://edoc.mpg.de/344505
urn:ISSN:0747-7171
Journal of Symbolic Computation, v.17, 295-295 (1994)
en
oai:edoc.mpg.de:3445562012-09-1987:931
The 'almost all' theory of subrecursive degrees is decidable
Mehlhorn, Kurt
Loeckx, Jacques
expertsonly
Springer
1974
Conference-Paper
http://edoc.mpg.de/344556
urn:ISBN:3-540-06841-4
Automata, languages and programming : 2nd colloquium (ICALP-74), Springer, 317-325 (1974)
en
oai:edoc.mpg.de:3445572012-09-1987:931
Monotone Switching Circuits and Boolean Matrix Product
Mehlhorn, Kurt
Galil, Zvi
expertsonly
We explore the concept of local transformations of monotone switching circuits,
i.e. what kind of local changes in a network leave the input/output behavior
invariant. We obtain several general theorems in this direction. We apply these
results to boolean matrix product and prove that the school-method for matrix
multiplication yields the unique monotone circuit.
1976
Article
http://edoc.mpg.de/344557
urn:ISBN:0010-485X (printed version)
Computing, v.16, 99-111 (1976)
en
oai:edoc.mpg.de:3445582012-09-1987:931
An Improved Lower Bound on the Formula Complexity of Context-Free Recognition
Mehlhorn, Kurt
expertsonly
1976
Article
http://edoc.mpg.de/344558
Elektronische Informationsverarbeitung und Kybernetik, v.12, 523-524 (1976)
en
ResultSet_66kZUELjHcp_range_100-199