2020-10-20T20:58:37Zhttp://edoc.mpg.de/ac_p_oai.ploai:edoc.mpg.de:2017852012-09-1987:931
A theoretical and experimental study on the construction of suffix arrays in external memory
Crauser, Andreas
Ferragina, Paolo
The construction of full-text indexes on very large text collections
is nowadays a hot problem. The suffix array [Manber-Myers,~1993] is
one of the most attractive full-text indexing data structures due to
its simplicity, space efficiency and powerful/fast search operations
supported. In this paper we analyze, both theoretically and
experimentally, the I/O-complexity and the working space of six
algorithms for constructing large suffix arrays. Three of them are
the state-of-the-art, the other three algorithms are our new
proposals. We perform a set of experiments based on three different
data sets (English texts, Amino-acid sequences and random texts) and
give a precise hierarchy of these algorithms according to their
working-space vs. construction-time tradeoff. Given the current
trends in model design~\cite{Farach-et-al,Vitter} and disk
technology~\cite{quantum,Ruemmler-Wilkes}, we will pose particular
attention to differentiate between ``random'' and ``contiguous''
disk accesses, in order to reasonably explain some practical
I/O-phenomena which are related to the experimental behavior of
these algorithms and that would be otherwise meaningless in the
light of other simpler external-memory models.
At the best of our knowledge, this is the first study which provides
a wide spectrum of possible approaches to the construction of suffix
arrays in external memory, and thus it should be helpful to anyone
who is interested in building full-text indexes on very large text
collections.
Finally, we conclude our paper by addressing two other issues. The
former concerns with the problem of building word-indexes; we show
that our results can be successfully applied to this case too,
without any loss in efficiency and without compromising the
simplicity of programming so to achieve a uniform, simple and
efficient approach to both the two indexing models. The latter issue
is related to the intriguing and apparently counterintuitive
``contradiction'' between the effective practical performance of the
well-known BaezaYates-Gonnet-Snider's algorithm~\cite{book-info},
verified in our experiments, and its unappealing (i.e., cubic)
worst-case behavior. We devise a new external-memory algorithm that
follows the basic philosophy underlying that algorithm but in a
significantly different manner, thus resulting in a novel approach
which combines good worst-case bounds with efficient practical
performance.
2002
Article
http://edoc.mpg.de/201785
urn:ISSN:0178-4617
Algorithmica, v.32, 1-35 (2002)
en
oai:edoc.mpg.de:2017882012-09-1987:931
Heuristics for Semi-External Depth First Search on Directed Graphs
Sibeyn, Jop F.
Abello, James
Meyer, Ulrich
Computing the strong components of a directed graph is an essential
operation for a basic structural analysis of it. This problem can
be solved by twice running a depth-first search (DFS).
In an external setting, in which all data can no longer be stored in
the main memory, the DFS problem is unsolved so far. Assuming that
node-related data can be stored internally, semi-external computing
does not make the problem substantially easier. Considering the
definite need to analyze very large graphs, we have developed a set
of heuristics which together allow the performance of semi-external DFS for
directed graphs in practice. The heuristics have been applied to
graphs with very different graph properties, including ``web graphs''
as described in the most recent literature and some call graphs from
ATT. Depending on the graph structure, the program is between 10 and
200 times faster than the best alternative, a factor that will
further increase with future technological developments.
ACM
2002
Conference-Paper
http://edoc.mpg.de/201788
urn:ISBN:1-58113-529-7
SPAA 2002 : Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, 282-292 (2002)
en
oai:edoc.mpg.de:2017892012-09-1987:931
Exact geometric computation
Mehlhorn, Kurt
Lipitakis, Elias A.
LEA
2002
Conference-Paper
http://edoc.mpg.de/201789
urn:ISBN:960-85176-9-9
HERCMA 2001 : proceedings of the 5th Hellenic-European Conference on Computer Mathematics and its Applications (HERCMA-01), LEA, 87-87 (2002)
en
oai:edoc.mpg.de:2017932012-09-1987:931
External-Memory Breadth-First Search with Sublinear I/O
Mehlhorn, Kurt
Meyer, Ulrich
Möhring, Rolf
Raman, Rajeev
Breadth-first search (BFS) is a basic graph exploration technique.
We give the first external-memory algorithm for sparse
undirected graphs with sublinear I/O. The best
previous algorithm requires O( n + sort(n+m) ) I/Os
on a graph with n nodes and m edges and a machine with
main-memory of size M, D parallel disks, and block size B.
We present two versions of a new algorithm which requires only
O( sqrt( n/m * (n+m)/(D*B) ) * log_{M/B} (n/B) + sort(n+m)) I/Os
(expected or worst-case, respectively).
Hence, for m = O(n), they improve upon the I/O-performance
of the best previous algorithm by nearly a factor of sqrt(D*B).
Our approach is fairly simple and we conjecture at least the
randomized version to be practical.
Springer
2002
Conference-Paper
http://edoc.mpg.de/201793
urn:ISBN:3-540-44180-8
Algorithms - ESA 2002 : 10th Annual European Symposium, Springer, 723-735 (2002)
en
oai:edoc.mpg.de:2017962012-09-1987:931
Minimum Cost Flows Over Time without Intermediate Storage
Fleischer, Lisa
Skutella, Martin
Flows over time (also called dynamic flows)
generalize standard network flows by introducing
an element of time. They naturally model problems where
travel and transmission are not instantaneous. Solving these problems
raises issues that do not arise in standard network flows.
One issue is the question of storage of flow at intermediate nodes.
In most applications
(such as, e.g., traffic routing, evacuation planning,
telecommunications etc.), intermediate storage is limited, undesired,
or prohibited.
The minimum cost flow over time problem is NP-hard. In this paper we
1)~prove that the minimum cost flow over time never requires storage;
2)~provide the first approximation scheme for minimum cost flows over
time that does not require storage; 3)~provide the first approximation
scheme for minimum cost flows over time that meets hard cost
constraints, while approximating only makespan.
Our approach is based on a condensed variant of time-expanded
networks. It also yields fast approximation schemes with simple
solutions for the quickest multicommodity flow problem.
Finally, using completely different techniques, we describe a very
simple capacity scaling FPAS for the minimum cost flow over time
problem when costs are proportional to transit times.
The algorithm builds upon our observation about the
structure of optimal solutions to this problem:
they are universally quickest flows. Again, the FPAS
does not use intermediate node storage.
In contrast to the preceding algorithms that use a
time-expanded network, this FPAS runs directly on the original
network.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201796
urn:ISBN:0-89871-538-5
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03), ACM, 66-75 (2003)
en
oai:edoc.mpg.de:2018012012-09-1987:931
Better Filtering with Gapped q-Grams
Burkhardt, Stefan
Kärkkäinen, Juha
A popular and well-studied class of filters for approximate string
matching compares substrings of length $q$, \emph{the $q$-grams}, in
the pattern and the text to identify text areas that contain potential
matches. A generalization of the method that uses {\em gapped}
$q$-grams instead of contiguous substrings is mentioned a few times in
literature but has never been analyzed in any depth. In this paper,
we report the first results of a study on gapped $q$-grams. We show
that gapped $q$-grams can provide orders of magnitude faster and/or
more efficient filtering than contiguous $q$-grams. To achieve these
results the arrangement of the gaps in the $q$-gram and a filter
parameter called \emph{threshold} have to be optimized. Both of these
tasks are nontrivial combinatorial optimization problems for which we
present efficient solutions. We concentrate on the $k$~mismatches
problem, i.e, approximate string matching with the Hamming distance.
2003
Article
http://edoc.mpg.de/201801
urn:ISSN:0169-2968
Fundamenta Informaticae, v.56, 51-70 (2003)
en
oai:edoc.mpg.de:2018062012-09-1987:931
Algorithms for Memory Hierarchies
Meyer, Ulrich
Sanders, Peter
Sibeyn, Jop F.
Springer
2003
Book
http://edoc.mpg.de/201806
urn:ISBN:3-540-00883-7
en
oai:edoc.mpg.de:2018112012-09-1987:931
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm
Becchetti, Luca
Leonardi, Stefano
Marchetti-Spaccamela, Alberto
Schäfer, Guido
Vredeveld, Tjark
In this paper we introduce the notion of smoothed competitive analysis of
online algorithms. Smoothed analysis has been proposed by Spielman and Teng
\cite{ST01} to explain the behaviour of algorithms that work well in practice
while performing very poorly from a worst case analysis point of view. We
apply this notion to analyze the Multi-Level Feedback (MLF) algorithm to
minimize the total flow time on a sequence of jobs released over time when the
processing time of a job is only known at time of completion.
The initial processing times are integers in the range $[1,2^K]$. We use a
partial bit randomization model, where the initial processing times are
smoothened by changing the $k$ least significant bits under a quite general
class of probability distributions. We show that MLF admits a smoothed
competitive ratio of $O((2^k/\sigma)^3 + (2^k/\sigma)^2 2^{K-k})$, where
$\sigma$ denotes the standard deviation of the distribution. In particular, we
obtain a competitive ratio of $O(2^{K-k})$ if $\sigma = \Theta(2^k)$. We also
prove an $\Omega(2^{K-k})$ lower bound for any deterministic algorithm that is
run on processing times smoothened according to the partial bit randomization
model. For various other smoothening models, including the additive symmetric
smoothening model used by Spielman and Teng \cite{ST01}, we give a higher
lower bound of $\Omega(2^K)$.
A direct consequence of our result is also the first average case analysis of
MLF. We show a constant expected ratio of the total flow time of MLF to the
optimum under several distributions including the uniform distribution.
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201811
44th Annual Symposium on Foundations of Computer Science (FOCS-03), IEEE, 462-471 (2003)
en
oai:edoc.mpg.de:2018172012-09-1987:931
The complexity of economic equilibria for house allocation markets
Fekete, Sandor P.
Skutella, Martin
Woeginger, Gerhard J.
We prove NP-completeness of deciding the existence of an economic equilibrium
in so-called house allocation markets. House allocation markets are markets
with indivisible goods in which every agent holds exactly one copy of some
good.
2003
Article
http://edoc.mpg.de/201817
urn:ISSN:0020-0190
Information Processing Letters, v.88, 219-223 (2003)
en
oai:edoc.mpg.de:2018272012-09-1987:931
Algorithms and Experiments for the Webgraph
Laura, Luigi
Leonardi, Stefano
Millozzi, Stefano
Meyer, Ulrich
Sibeyn, Jop F.
Di Battista, Giuseppe
Zwick, Uri
Springer
2003
Conference-Paper
http://edoc.mpg.de/201827
urn:ISSN:0302-9743
Algorithms - ESA 2003: 11th Annual European Symposium, Springer, 703-714 (2003)
en
oai:edoc.mpg.de:2018292012-09-1987:931
Reconciling simplicity and realism in parallel disk models
Sanders, Peter
For the design and analysis of algorithms that process huge data sets, a
machine model is needed that handles parallel disks. There seems to be
a dilemma between simple and flexible use of such a model and accurate
modelling of details of the hardware. This paper explains how many
aspects of this problem can be resolved. The programming model
implements one large logical disk allowing concurrent access to
arbitrary sets of variable size blocks. This model can
be implemented efficienctly on multiple
independent disks even if zones with different speed,
communication bottlenecks
and failed disks are allowed. These results not only provide useful
algorithmic tools but also imply a theoretical justification for
studying external memory algorithms using simple abstract models.
The algorithmic approach is random redundant placement of data and
optimal scheduling of accesses. The analysis generalizes a previous
analysis for simple abstract external memory models in several ways
(Higher efficiency, variable block sizes, more detailed disk model).
As a side effect, an apparently new Chernoff-Hoeffding bound for sums of
weighted 0-1 random variables is derived.
2002
Article
http://edoc.mpg.de/201829
urn:ISSN:0167-8191
Parallel Computing, v.28, 705-723 (2002)
en
oai: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
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.
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:2018442012-09-1987:931
Simple Linear Work Suffix Array Construction
Kärkkäinen, Juha
Sanders, Peter
Baeten, Jos C.M.
Lenstra, Jan Karel
Parrow, Joachim
Woeginger, Gerhard J.
A suffix array represents the suffixes of a string in sorted order.
Being a simpler and more compact alternative to suffix trees, it
is an important tool for full text indexing and other string
processing tasks. We introduce the \emph{skew algorithm}
for suffix array construction over integer alphabets that can be
implemented to run in linear time using integer sorting as its only
nontrivial subroutine:\\
1. recursively sort suffixes beginning at positions $i\bmod 3\neq 0$.\\
2. sort the remaining suffixes using the information
obtained in step one.\\
3. merge the two sorted sequences obtained in steps one and two.\\
The algorithm is much
simpler than previous linear time algorithms that
are all based on the more complicated suffix tree data structure.
Since sorting is a well studied problem, we obtain
optimal algorithms for several other models of computation,
e.g.\ external memory with parallel disks, cache oblivious,
and parallel. The adaptations for BSP and EREW-PRAM
are asymptotically faster than the best previously known algorithms.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201844
urn:ISBN:3540404937
Automata, languages and programming : 30th International Colloquium, ICALP 2003, Springer, 943-955 (2003)
en
oai:edoc.mpg.de:2018502012-09-1987:931
Certifying and Repairing Solutions to Large LPs - How Good are LP-Solvers?
Dhiflaoui, Marcel
Funke, Stefan
Kwappik, Carsten
Mehlhorn, Kurt
Seel, Michael
Schömer, Elmar
Schulte, Ralph
Weber, Dennis
ACM
2003
Conference-Paper
http://edoc.mpg.de/201850
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03), ACM, 255-256 (2003)
en
oai:edoc.mpg.de:2018512012-09-1987:931
Experimental comparison of heuristic and approximation algorithms for uncapacitated facility location
Hoefer, Martin
Jansen, Klaus
Margraf, Marian
Mastrolli, Monaldo
Rolim, José D. P.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201851
urn:ISBN:3-540-40205-5
Experimental and efficient algorithms : Second International Workshop, WEA 2003, Springer, 165-178 (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
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:2018592012-09-1987:931
A Practical Minimum Spanning Tree Algorithm Using the Cycle Property
Katriel, Irit
Sanders, Peter
Träff, Jesper Larsson
Di Battista, Giuseppe
Zwick, Uri
Springer
2003
Conference-Paper
http://edoc.mpg.de/201859
urn:ISBN:3540200649
Algorithms - ESA 2003: 11th Annual European Symposium, Springer, 679-690 (2003)
en
oai:edoc.mpg.de:2018612012-09-1987:931
Memory hierarchies - models and lower bounds
Sanders, Peter
Meyer, Ulrich
Sanders, Peter
Sibeyn, Jop
Springer
2003
InBook
http://edoc.mpg.de/201861
urn:ISBN:3-540-00883-7
Algorithms for memory hierarchies, 1-10 (2003)
en
oai:edoc.mpg.de:2018632012-09-1987:931
Nearest Neighbors Can Be Found Efficiently If the Dimension Is Small Relative to the Input Size
Hagedoorn, Michiel
Calvanese, Diego
Lenzerini, Maurizio
Motwani, Rajeev
Springer
The copyright for this distribution is held by Springer.
© Springer-Verlag
http://www.springer.de/comp/lncs/index.html
2003
Conference-Paper
http://edoc.mpg.de/201863
urn:ISBN:3-540-00323-1
Database Theory - ICDT 2003 : 9th International Conference, Springer, 440-454 (2003)
en
oai:edoc.mpg.de:2018642012-09-1987:931
Scheduling and Traffic Allocation for Tasks with Bounded Splittability
Krysta, Piotr
Sanders, Peter
Vöcking, Berthold
Rovan, Branislav
Vojtáš, Peter
Springer
2003
Conference-Paper
http://edoc.mpg.de/201864
urn:ISBN:3540406719
Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003, Springer, 500-510 (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.
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:2018702012-09-1987:931
The factor algorithm for regular all-to-all communication on clusters of SMP nodes
Sanders, Peter
Träff, Jesper Larsson
Monien, Burkhard
Feldman, Rainer
Springer
2002
Conference-Paper
http://edoc.mpg.de/201870
urn:ISBN:3-450-67956-1
Proceedings of the 8th International Euro-Par Conference, Springer, 799-803 (2002)
en
oai:edoc.mpg.de:2018712012-09-1987:931
Random Arc Allocation and Applications to Disks, Drums and DRAMs
Sanders, Peter
Vöcking, Berthold
Penttonen, Martti
Meineche Schmidt, Erik
Springer
2002
Conference-Paper
http://edoc.mpg.de/201871
urn:ISBN:3-540-43866-1
Algorithm theory, SWAT 2002 : 8th Scandinavian Workshop on Algorithm Theory, Springer, 121-130 (2002)
en
oai:edoc.mpg.de:2018742012-09-1987:931
The reliable algorithmic software challenge RASC : dedicated to Thomas Ottmann on the occassion of his 60th birthday
Mehlhorn, Kurt
Klein, Rolf
Six, Hans-Werner
Wegner, Lutz
Springer
2003
InBook
http://edoc.mpg.de/201874
urn:ISBN:3-540-00579-X
Computer Science in Perspective : essays dedicated to Thomas Ottmann, 255-263 (2003)
en
oai:edoc.mpg.de:2018782012-09-1987:931
Tail bounds and expectations for random arc allocation and applications
Sanders, Peter
Vöcking, Berthold
2003
Article
http://edoc.mpg.de/201878
urn:ISSN:0963-5483
Combinatorics, Probability and Computing, v.12, 225-244 (2003)
en
oai:edoc.mpg.de:2018852012-09-1987:931
Preemptive scheduling with rejection
Hoogeveen, Han
Skutella, Martin
Woeginger, Gerhard J.
We consider the problem of preemptively scheduling a set of $n$ jobs
on $m$ (identical, uniformly related, or unrelated) parallel
machines. The scheduler may reject a subset of the jobs and thereby
incur job-dependent penalties for each rejected job, and he must
construct a schedule for the remaining jobs so as to optimize the
preemptive makespan on the $m$ machines plus the sum of the
penalties of the jobs rejected.
We provide a complete classification of these scheduling problems
with respect to complexity and approximability. Our main results
are on the variant with an arbitrary number of unrelated machines.
This variant is \apx-hard, and we design a $1.58$-approximation
algorithm for it. All other considered variants are weakly
\np-hard, and we provide fully polynomial time approximation schemes
for them. Finally, we argue that our results for unrelated machines
can be carried over to the corresponding preemptive open shop
scheduling problem with rejection.
2003
Article
http://edoc.mpg.de/201885
urn:ISSN:0025-5610
Mathematical Programming, v.94, 361-374 (2003)
en
oai:edoc.mpg.de:2018892012-09-1987:931
The Safari Interface for Visualizing Time-dependent Volume Data Using Iso-surfaces and Contour Spectra
Kettner, Lutz
Rossignac, Jarek
Snoeyink, Jack
We describe a geometric basis for the visualization of time-varying
volume data of one or several variables as they occur in scientific
and engineering applications. We demonstrate a prototype
interface for gridded data, extending the contour spectrum interface of
Bajaj, Pascucci, and Schikore to higher dimensions and to topological
properties that are not decomposable. We also describe a data structure
for pentatope meshes that supports the computation of isosurfaces and their
properties.
2003
Article
http://edoc.mpg.de/201889
urn:ISSN:0925-7721
Computational Geometry - Theory and Applications, v.25, 97-116 (2003)
en
oai:edoc.mpg.de:2018902012-09-1987:931
Fast Bound-Consistency for the Global Cardinality Constraint
Katriel, Irit
Thiel, Sven
Rossi, Francesca
Springer
2003
Conference-Paper
http://edoc.mpg.de/201890
urn:ISBN:3-540-20202-1
Principles and Practice of Constraint Programming - CP 2003 : 9th International Conference, CP 2003, Springer, 437-451 (2003)
en
oai:edoc.mpg.de:2018912012-09-1987:931
Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation
Granados, Miguel
Hachenberger, Peter
Hert, Susan
Kettner, Lutz
Mehlhorn, Kurt
Seel, Michael
Di Battista, Giuseppe
Zwick, Uri
We describe a data structure for three-dimensional Nef complexes, algorithms
for boolean operations on them, and our implementation of data structure and
algorithms. Nef polyhedra were introduced by W. Nef in his seminal 1978 book on
polyhedra. They are the closure of half-spaces under boolean operations and can
represent non-manifold situations, open and closed boundaries, and mixed
dimensional complexes. Our focus lies on the generality of the data structure,
the completeness of the algorithms, and the exactness and efficiency of the
implementation. In particular, all degeneracies are handled.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201891
Algorithms - ESA 2003: 11th Annual European Symposium, Springer, 654-666 (2003)
en
oai:edoc.mpg.de:2019002012-09-1987:931
Asynchronous Scheduling of Redundant Disk Arrays
Sanders, Peter
2003
Article
http://edoc.mpg.de/201900
urn:ISSN:0018-9340
IEEE Transactions on Computers, v.52, 1170-1184 (2003)
en
oai:edoc.mpg.de:2019022012-09-1987:931
Scheduling multicasts on unit-capacity trees and meshes
Henzinger, Monika R.
Leonardi, Stefano
2003
Article
http://edoc.mpg.de/201902
urn:ISSN:0022-0000
Journal of Computer and System Sciences, v.66, 567-611 (2003)
en
oai:edoc.mpg.de:2019062012-09-1987:931
A Bandwidth Latency Tradeoff for Broadcast and Reduction
Sanders, Peter
Sibeyn, Jop F.
2003
Article
http://edoc.mpg.de/201906
urn:ISSN:0020-0190
Information Processing Letters, v.86, 33-38 (2003)
en
oai:edoc.mpg.de:2019102012-09-1987:931
Infimaximal frames: A technique for making lines look like segments
Mehlhorn, Kurt
Seel, Michael
2003
Article
http://edoc.mpg.de/201910
International Journal of Computational Geometry & Applications, v.13, 241-255 (2003)
en
oai:edoc.mpg.de:2019112012-09-1987:931
Asynchronous Parallel Disk Sorting
Dementiev, Roman
Sanders, Peter
ACM
2003
Conference-Paper
http://edoc.mpg.de/201911
urn:ISBN:1581136617
Proceedings of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA-03), ACM, 138-148 (2003)
en
oai:edoc.mpg.de:2019122012-09-1987:931
A Heuristic for Dijkstra's Algorithm With Many Targets and its Use in Weighted Matching Algorithms
Bast, Holger
Mehlhorn, Kurt
Schäfer, Guido
Tamaki, Hisao
We consider the single-source many-targets shortest-path (SSMTSP) problem in
directed graphs with non-negative
edge weights. A source node $s$ and a target set $T$ is specified and the goal
is to compute a shortest path from $s$ to a node in $T$.
Our interest in the shortest path problem with many targets stems from its use
in weighted bipartite matching algorithms. A weighted bipartite matching in a
graph with $n$ nodes on each side reduces to $n$ SSMTSP problems, where the
number
of targets varies between $n$ and $1$.
The SSMTSP problem can be solved by Dijkstra's algorithm. We describe a
heuristic
that leads to a significant improvement in running time for the weighted
matching
problem; in our experiments a speed-up by up to a factor of 12 was achieved.
We also present a partial analysis that gives some theoretical support for our
experimental findings.
2003
Article
http://edoc.mpg.de/201912
Algorithmica, v.36, 75-88 (2003)
en
oai:edoc.mpg.de:2019162012-09-1987:931
Improving Linear Programming Approaches for the Steiner Tree Problem
Althaus, Ernst
Polzin, Tobias
Vahdati Daneshmand, Siavash
Jansen, Klaus
Margraf, Marian
Mastrolli, Monaldo
Rolim, José D. P.
We present two theoretically interesting and empirically successful
techniques for improving the linear programming approaches, namely
graph transformation and local cuts, in the context of the
Steiner problem. We show the impact of these techniques on the
solution of the largest benchmark instances ever solved.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201916
Experimental and efficient algorithms : Second International Workshop, WEA 2003, Springer, 1-14 (2003)
en
oai:edoc.mpg.de:2019192012-09-1987:931
Packing a Trunk
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 pack as many identical boxes of size $4 × 2 × 1$ units
as possible into the interior of the trunk. This measure is
important for car manufacturers, because it is a standard in the
European Union.
First, we prove that a natural formal variant of this problem is
NP-complete. Further, we use a combination of integer linear
programming techniques and heuristics that exploit the geometric
structure to attack this problem. Our experiments show that for
all considered instances, we can get very close to the optimal
solution in reasonable time.
Springer
(c) Springer-Verlag
2003
Conference-Paper
http://edoc.mpg.de/201919
urn:ISBN:3-540-20064-9
Algorithms - ESA 2003: 11th Annual European Symposium, Springer, 618-629 (2003)
en
oai:edoc.mpg.de:2019232012-09-1987:931
Isoperimetric Inequalities and Width Parameters of Graphs
Telikepalli, Kavitha
Chandran, Sunil
Subramanian, C. R.
Warnow, Tandy
Zhu, Binhai
Springer
2003
Conference-Paper
http://edoc.mpg.de/201923
Computing and Combinatorics : 9th Annual International Conference, COCOON 2003, Springer, 385-393 (2003)
en
oai:edoc.mpg.de:2019252012-09-1987:931
Elliptic Curves : A Computational Approach
Schmitt, Susanne
Zimmer, Horst G.
The purpose of the present text is to give an elementary
introduction to the arithmetic of elliptic curves over number
fields from a computational point of view. This branch of
number theory is particularly accessible to computer assisted
calculations, and the authors make use of this feature by
approaching the theory from a computational point of view.
Specifically, the computer-algebra package SIMATH is applied
on several occasions.
de Gruyter
2003
Book
http://edoc.mpg.de/201925
urn:ISBN:3-11-016808-1
en
oai:edoc.mpg.de:2019272012-09-1987:931
Approximating Minimum Size 1,2-Connected Networks
Krysta, Piotr
2003
Article
http://edoc.mpg.de/201927
Discrete Applied Mathematics, v.125, 267-288 (2003)
en
oai:edoc.mpg.de:2019342012-09-1987:931
Optimal Search for Rationals
Kwek, St.
Mehlhorn, Kurt
2003
Article
http://edoc.mpg.de/201934
Information Processing Letters, v.86, 23-26 (2003)
en
oai:edoc.mpg.de:2019362012-09-1987:931
Scanning multiple sequences via cache memory
Mehlhorn, Kurt
Sanders, Peter
2003
Article
http://edoc.mpg.de/201936
urn:ISSN:0178-4617
Algorithmica, v.35, 75-93 (2003)
en
oai:edoc.mpg.de:2019372012-09-1987:931
Average-case complexity of single-source shortest-path algorithms: lower and upper bounds
Meyer, Ulrich
2003
Article
http://edoc.mpg.de/201937
urn:ISSN:0196-6774
Journal of Algorithms, v.48, 91-134 (2003)
en
oai:edoc.mpg.de:2019382012-09-1987:931
On Steiner trees and minimum spanning trees in hypergraphs
Polzin, Tobias
Vahdati Daneshmand, Siavash
2003
Article
http://edoc.mpg.de/201938
urn:ISSN:0167-6377
Operations Research Letters, v.31, 12-20 (2003)
en
oai:edoc.mpg.de:2019412012-09-1987:931
Data Management in Networks: Experimental Evaluation of a Provably Good Strategy
Krick, Christof
Meyer auf der Heide, Friedhelm
Räcke, Harald
Vöcking, Berthold
Westermann, Matthias
2003
Article
http://edoc.mpg.de/201941
Theory of Computing Systems, v.35, 217-245 (2003)
en
oai:edoc.mpg.de:2019442012-09-1987:931
Full-Text Indexes in External Memory
Kärkkäinen, Juha
Rao, S. Srinivasa
Meyer, Ulrich
Sanders, Peter
Sibeyn, Jop
Springer
2003
InBook
http://edoc.mpg.de/201944
urn:ISBN:3-540-00883-7
Algorithms for Memory Hierarchies, 149-170 (2003)
en
oai:edoc.mpg.de:2019452012-09-1987:931
Polynomial Time Algorithms For Network Information Flow
Sanders, Peter
Egner, Sebastian
Tolhuizen, Ludo
ACM
2003
Conference-Paper
http://edoc.mpg.de/201945
urn:ISBN:1581136617
Proceedings of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA-03), ACM, 286-294 (2003)
en
oai:edoc.mpg.de:2019542012-09-1987:931
Certifying algorithms for recognizing interval graphs and permutation graph
Kratsch, Dieter
McConnell, R.
Mehlhorn, Kurt
Spinrad, J.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201954
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03), ACM, 158-167 (2003)
en
oai:edoc.mpg.de:2019552012-09-1987:931
An experimental study of k-splittable scheduling for DNS-based traffic allocation
Agarwal, Amit
Agarwal, Tarun
Chopra, Sumit
Feldmann, Anja
Kammenhuber, Nils
Krysta, Piotr
Vöcking, Berthold
Kosch, Harald
Böszörményi, László
Hellwagner, Hermann
Springer
2003
Conference-Paper
http://edoc.mpg.de/201955
urn:ISBN:3-540-40788-X
Euro-Par 2003 parallel processing : 9th International Euro-Par Conference ; proceedings, Springer, 230-235 (2003)
en
oai:edoc.mpg.de:2019562012-09-1987:931
On external-memory planar depth first search
Arge, Lars
Meyer, Ulrich
Toma, Laura
Zeh, Norbert
2003
Article
http://edoc.mpg.de/201956
urn:ISSN:1526-1719
Journal of Graph Algorithms and Applications, v.7, 105-129 (2003)
en
oai:edoc.mpg.de:2019572012-09-1987:931
Scheduling to minimize flow time metrics
Becchetti, Luca
Leonardi, Stefano
Marchetti-Spaccamela, Alberto
Schäfer, Guido
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201957
urn:ISBN:0-7695-1926-1
International Parallel and Distributed Processing Symposium (IPDPS-03), IEEE, 223b-CDROM (2003)
en
oai:edoc.mpg.de:2019592012-09-1987:931
Efficient Algorithms for Abelian group isomorphism and related problems
Telikepalli, Kavitha
Pandya, Paritosh
Radhakrishnan, Jaikumar
Springer
2003
Conference-Paper
http://edoc.mpg.de/201959
FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science : 23rd Conference, Springer, 277-288 (2003)
en
oai:edoc.mpg.de:2019612012-09-1987:931
On Shortest Paths in Line Arrangements
Telikepalli, Kavitha
McAllister, Michael
Dalhousie University
2003
Conference-Paper
http://edoc.mpg.de/201961
15th Canadian Conference in Computational Geometry (CCCG-03), Dalhousie University, 170-173 (2003)
en
oai:edoc.mpg.de:2019622012-09-1987:931
Elementary Graph Algorithms in External Memory
Katriel, Irit
Meyer, Ulrich
Meyer, Ulrich
Sanders, Peter
Sibeyn, Jop
Springer
2003
InBook
http://edoc.mpg.de/201962
urn:ISBN:3-540-00883-7
Algorithms for Memory Hierarchies, 62-84 (2003)
en
oai:edoc.mpg.de:2019652012-09-1987:931
Sweep Synchronization as a Global Propagation Mechanism
Beldiceanu, Nicolas
Carlsson, Mats
Thiel, Sven
Centre for Research on Transportation
2003
Conference-Paper
http://edoc.mpg.de/201965
Fifth International Workshop on Integration of AI and OR Techniques
in Constraint Programming for Combinatorial Optimization Problems, Centre for Research on Transportation, 139-152 (2003)
en
oai:edoc.mpg.de:2019662012-09-1987:931
I/O-Efficient Undirected Shortest Paths
Meyer, Ulrich
Zeh, Norbert
Di Battista, Giuseppe
Zwick, Uri
Springer
2003
Conference-Paper
http://edoc.mpg.de/201966
urn:ISSN:0302-9743
Algorithms - ESA 2003: 11th Annual European Symposium, Springer, 434-445 (2003)
en
oai:edoc.mpg.de:2019692012-09-1987:931
Power Efficient Range Assignment in Ad-hoc Wireless
Althaus, Ernst
Calinescu, Gruia
Mandoiu, Ion
Prasad, Sushil
Tchervenski, Nickolay
Zelikovsly, Alexander
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201969
Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC-03), IEEE, 1889-1894 (2003)
en
oai:edoc.mpg.de:2019712012-09-1987:931
Optimizing Misdirection
Berman, Piotr
Krysta, Piotr
ACM
2003
Conference-Paper
http://edoc.mpg.de/201971
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03), ACM, 192-201 (2003)
en
oai:edoc.mpg.de:2019722012-09-1987:931
Random Knapsack in Expected Polynomial Time
Beier, Rene
Vöcking, Berthold
In this paper, we present the first average-case analysis proving an expected
polynomial running time for an exact algorithm for the 0/1 knapsack problem.
In particular, we prove, for various input distributions, that the number of
{\em dominating solutions\/} (i.e., Pareto-optimal knapsack fillings)
to this problem is polynomially bounded in the number of available items.
An algorithm by Nemhauser and Ullmann can enumerate these solutions very
efficiently so that a polynomial upper bound on the number of dominating
solutions
implies an algorithm with expected polynomial running time.
The random input model underlying our analysis is very general
and not restricted to a particular input distribution. We assume adversarial
weights and randomly drawn profits (or vice versa). Our analysis covers general
probability
distributions with finite mean, and, in its most general form, can even
handle different probability distributions for the profits of different items.
This feature enables us to study the effects of correlations between profits
and weights. Our analysis confirms and explains practical studies showing
that so-called {\em strongly correlated\/} instances are harder to solve than
{\em weakly correlated\/} ones.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201972
urn:ISBN:1-58113-674-9
Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC-03), ACM, 232-241 (2003)
en
oai:edoc.mpg.de:2019742012-09-1987:931
An Efficient Algorithm for the Configuration Problem of Dominance Graphs
Althaus, Ernst
Duchier, Denys
Koller, Alexander
Mehlhorn, Kurt
Niehren, Joachim
Thiel, Sven
2003
Article
http://edoc.mpg.de/201974
urn:ISSN:0196-6774
Journal of Algorithms, v.48, 194-219 (2003)
en
oai:edoc.mpg.de:2019782012-09-1987:931
Proof of a conjecture of Bollobas and Eldridge for graphs of maximum degree three
Csaba, Bela
Let $G_1$ and $G_2$ be simple graphs on $n$ vertices. If there are
edge-disjoint copies of $G_1$ and $G_2$ in $K_n$, then we say there is
a packing of $G_1$ and $G_2$. A conjecture of Bollob\'as and Eldridge
~\cite{be78} asserts that if $(\Delta(G_1)+1)(\Delta(G_2)+1)\le n+1$ then
there is a packing of $G_1$ and $G_2$. We prove this conjecture when
$\Delta(G_1)=3$, for sufficiently large $n$.
2003
Article
http://edoc.mpg.de/201978
urn:ISSN:0209-9683
Combinatorica, v.23, 35-72 (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
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:2019862012-09-1987:931
Curve Reconstruction from Noisy Samples
Cheng, Siu-Wing
Funke, Stefan
Golin, Mordecai J.
Kumar, Piyush
Poon, Sheung-Hung
Ramos, Edgar A.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201986
Proceedings of the 19th Annual Symposium on Computational Geometry (SCG-03), ACM, 420-429 (2003)
en
oai:edoc.mpg.de:2019972012-09-1987:931
Solving geometric optimization problems using graphics hardware
Denny, Markus
Brunet, Pere
Fellner, Dieter W.
Blackwell
2003
Conference-Paper
http://edoc.mpg.de/201997
EUROGRAPHICS 2003 : the European Association for Computer Graphics 24th Annual Conference, Blackwell, 441-451 (2003)
en
oai:edoc.mpg.de:2020032012-09-1987:931
Automatic Layout and Labelling of State Diagrams
Klau, Gunnar W.
Mutzel, Petra
Jäger, Willi
Krebs, Hans-Joachim
Springer
2003
InBook
http://edoc.mpg.de/202003
urn:ISBN:3-540-44220-0
Mathematics: Key Technology for the Future : Joint Projects Between Universities and Industry, 584-608 (2003)
en
oai:edoc.mpg.de:2020082012-09-1987:931
A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-perfect Graph
Eisenbrand, Friedrich
Funke, Stefan
Garg, Naveen
Könemann, Jochen
ACM
2003
Conference-Paper
http://edoc.mpg.de/202008
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03), ACM, 517-522 (2003)
en
oai:edoc.mpg.de:2020092012-09-1987:931
Multicommodity Flows Over Time: Efficient Algorithms and Complexity
Hall, Alex
Hippler, Steffen
Skutella, Martin
Baeten, Jos C.M.
Lenstra, Jan Karel
Parrow, Joachim
Woeginger, Gerhard J.
Flow variation over time is an important feature in network flow
problems arising in various applications such as road or air traffic
control, production systems, communication networks (e.g., the
Internet), and financial flows. The common characteristic are
networks with capacities and transit times on the arcs which specify
the amount of time it takes for flow to travel through a particular
arc. Moreover, in contrast to static flow problems, flow values on
arcs may change with time in these networks.
While the `maximum $s$-$t$-flow over time' problem can be solved
efficiently and `min-cost flows over time' are known to be NP-hard,
the complexity of (fractional) `multicommodity flows over time' has
been open for many years. We prove that this problem is NP-hard,
even for series-parallel networks, and present new and efficient
algorithms under certain assumptions on the transit times or on the
network topology. As a result, we can draw a complete picture of
the complexity landscape for flow over time problems.
Springer
2003
Conference-Paper
http://edoc.mpg.de/202009
urn:ISBN:3-540-40493-7
Automata, languages and programming : 30th International Colloquium, ICALP 2003, Springer, 397-409 (2003)
en
oai:edoc.mpg.de:2020342012-09-1987:931
Δ-stepping: a parallelizable shortest path algorithm
Meyer, Ulrich
Sanders, Peter
2003
Article
http://edoc.mpg.de/202034
urn:ISSN:0196-6774
Journal of Algorithms, v.49, 114-152 (2003)
en
oai:edoc.mpg.de:2020382012-09-1987:931
Tight Degree Bounds for Pseudo-triangulations of Points
Kettner, Lutz
Kirkpatrick, David
Mantler, Andrea
Snoeyink, Jack
Speckmann, Bettina
Takeuchi, Fumihiko
We show that every set of $n$ points in general position has a
minimum pseudo-triangulation whose maximum vertex degree is five.
In addition, we demonstrate that every point set in general position
has a minimum pseudo-triangulation whose maximum face degree is four
(i.e.\ each interior face of this pseudo-triangulation has at most
four vertices). Both degree bounds are tight. Minimum
pseudo-triangulations realizing these bounds (individually but not
jointly) can be constructed in $O(n \log n)$ time.
2003
Article
http://edoc.mpg.de/202038
urn:ISSN:0925-7721
Computational Geometry - Theory and Applications, v.25, 3-12 (2003)
en
oai:edoc.mpg.de:2020432012-09-1987:931
An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times
Hall, Alex
Langkau, Katharina
Skutella, Martin
Arora, Sanjeev
Jansen, Klaus
Rolim, Jose D. P.
Sahai, Amit
Given a network with capacities and transit times on the arcs, the
quickest flow problem asks for a `flow over time' that satisfies
given demands within minimal time. In the setting of flows over
time, flow on arcs may vary over time and the transit time of an arc
is the time it takes for flow to travel through this arc. In most
real-world applications (such as, e.g., road traffic, communication
networks, production systems, etc.), transit times are not fixed but
depend on the current flow situation in the network. We consider
the model where the transit time of an arc is given as a
nondecreasing function of the rate of inflow into the arc. We prove
that the quickest $s$-$t$-flow problem is NP-hard in this setting
and give various approximation results, including an FPTAS for the
quickest multicommodity flow problem with bounded cost.
Springer
2003
Conference-Paper
http://edoc.mpg.de/202043
urn:ISBN:3-540-40770-7
Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques ; 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Springer, 71-82 (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
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:2020532012-09-1987:931
Energy Optimal Routing in Radio Networks Using Geometric Data Structures
Beier, Rene
Sanders, Peter
Sivadasan, Naveen
Widmayer, Peter
Triguero, Francisco
Morales, Rafael
Hennessy, Matthew
Eidenbenz, Stephan
Conejo, Ricardo
Springer
2002
Conference-Paper
http://edoc.mpg.de/202053
urn:ISBN:3-540-43884-5
Automata, Languages and Programming : 29th International Colloquium, ICALP 2002, Springer, 366-376 (2002)
en
oai:edoc.mpg.de:2020542012-09-1987:931
Scheduling at Twilight the Easy Way
Bast, Hannah
Ferreira, Afonso
Alt, Helmut
We investigate particularly simple algorithms for optimizing the tradeoff
between load imbalance and assignment overheads in dynamic multiprocessor
scheduling scenarios, when the information that is available about the
processing time of a task before it is completed is vague.
We describe a simple and elegant generic algorithm that, in a very
general model, always comes surprisingly close to the theoretical optimum,
and the performance of which we can analyze exactly with respect to constant
factors. In contrast, we prove that algorithms that assign tasks
in equal-sized portions
perform far from optimal in general. In fact, we give evidence that the
performance of our generic scheme cannot be improved by any constant factor
without sacrificing the simplicity of the algorithm. We also give lower
bounds on the performance of the various decreasing-size heuristics that
have typically been used so far in concrete applications.
Springer
2002
Conference-Paper
http://edoc.mpg.de/202054
urn:ISBN:3-540-43283-3
STACS 2002 : 19th Annual Symposium on Theoretical Aspects of Computer Science, Springer, 166-178 (2002)
en
oai:edoc.mpg.de:2020552012-09-1987:931
Basic analytic combinatorics of directed lattice paths
Banderier, Cyril
Flajolet, Philippe
2002
Article
http://edoc.mpg.de/202055
urn:ISSN:0304-3975
Theoretical Computer Science, v.281, 37-80 (2002)
en
oai:edoc.mpg.de:2020562012-09-1987:931
Multiple Robot Motion Planning = Parallel Processing + Geometry
Hert, Susan
Richards, Brad
Christensen, Henrik
Hager, Greg
We present two problems in multiple-robot motion planning that can be quite
naturally solved using techniques from the parallel processing community to
dictate how the robots interact with each other and techniques from
computational geometry to apply these techniques in the geometric environment
in which the robots operate. The first problem we consider is a load-balancing
problem in which a pool of work must be divided among a set of
processors in order to minimize the amount of time required to complete all
the work. We describe a simple polygon partitioning algorithm that allows
techniques from parallel processor scheduling to be applied in the
multiple-robot setting in order to achieve a good balance of the work.
The second problem is that of collision avoidance, where one must avoid that
two (or more) processors occupy the same resource at the same time.
For this problem, we describe a procedure for robot interaction that is
derived from procedures used to shared-memory computers along with a geometric
data structure that can efficiently determine when there are potential
robot collisions.
Springer
2002
Conference-Paper
http://edoc.mpg.de/202056
Sensor Based Intelligent Robots, Springer, 183-205 (2002)
en
oai:edoc.mpg.de:2020572012-09-1987:931
Randomized Pursuit-Evasion in Graphs
Adler, Micah
Räcke, Harald
Sivadasan, Naveen
Sohler, Christian
Vöcking, Berthold
Widmayer, Peter
Triguero, Francisco
Morales, Rafael
Hennessy, Matthew
Eidenbenz, Stephan
Conejo, Ricardo
{
We analyze a randomized pursuit-evasion game on graphs. This game is
played by two players, a {\em hunter} and a {\em rabbit}. Let
$G$ be any connected, undirected graph with $n$ nodes.
The game is played in rounds and in each round both the
hunter and the rabbit are located at a node of the graph. Between rounds
both the hunter and the rabbit can stay at the current node or move to
another node. The hunter is assumed to be {\em restricted} to the
graph $G$: in every round, the hunter can move using at most one edge.
For the rabbit we investigate two models: in one
model the rabbit is restricted to the same graph as the hunter, and in
the other model the rabbit is {\em unrestricted}, i.e., it can jump to
an arbitrary node in every round.
We say that the rabbit is {\em caught}\/ as soon as hunter and rabbit
are located at the same node in a round. The goal of the hunter is to
catch the rabbit in as few rounds as possible, whereas the rabbit aims
to maximize the number of rounds until it is caught. Given a
randomized hunter strategy for $G$, the {\em escape length} for that
strategy is the worst case expected number of rounds it takes the
hunter to catch the rabbit, where the worst case is with regards to
all (possibly randomized) rabbit strategies.
Our main result is a hunter strategy for general graphs
with an escape length of only $\O(n \log (\diam(G)))$ against
restricted as well as unrestricted rabbits.
This bound is close to optimal since $\Omega(n)$ is a trivial lower bound
on the escape length in both models.
Furthermore, we prove that our upper bound is optimal
up to constant factors against unrestricted rabbits.
}
Springer
2002
Conference-Paper
http://edoc.mpg.de/202057
urn:ISBN:3-540-43864-5
Automata, Languages and Programming : 29th International Colloquium, ICALP 2002, Springer, 901-912 (2002)
en
oai:edoc.mpg.de:2020582012-09-1987:931
Optimal prefix-free codes for unequal letter costs: Dynamic programming with the Monge property
Bradford, Phillip Gnassi
Golin, Mordecai J.
Larmore, Lawrence L.
2002
Article
http://edoc.mpg.de/202058
urn:ISSN:0196-6774
Journal of Algorithms, v.42, 277-303 (2002)
en
oai:edoc.mpg.de:2020592012-09-1987:931
A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons
Berberich, Eric
Eigenwillig, Arno
Hemmer, Michael
Hert, Susan
Mehlhorn, Kurt
Schömer, Elmar
Möhring, Rolf
Raman, Rajeev
We give an exact geometry kernel for conic arcs, algorithms for exact
computation with low-degree algebraic numbers, and an algorithm for
computing the arrangement of conic arcs that immediately leads to
a realization of regularized boolean operations on conic polygons. A conic
polygon, or polygon for short, is anything that can be obtained from
linear or conic halfspaces (= the set of points where a linear or quadratic
function is non-negative) by regularized boolean operations. The algorithm and
its implementation are complete (they can handle all cases), exact (they give
the mathematically correct result), and efficient (they can handle inputs with
several hundred primitives).
Springer
2002
Conference-Paper
http://edoc.mpg.de/202059
urn:ISBN:3-540-44180-8
Algorithms - ESA 2002 : 10th Annual European Symposium, Springer, 174-186 (2002)
en
oai:edoc.mpg.de:2020602012-09-1987:931
Translating a Planar Object to Maximize Point Containment
Agarwal, Pankaj
Hagerup, Torben
Ray, Rahul
Sharir, Micha
Smid, Michiel
Welzl, Emo
Möhring, Rolf
Raman, Rajeev
Let $C$ be a compact set in $\IR^2$ and let $S$ be a set
of $n$ points in $\IR^2$. We consider the problem of computing a
translate of $C$ that contains the maximum number, $\kappa^*$, of points
%denoted by $\kappa^*$,
of $S$.
It is known that this problem can be solved in a time that is
roughly quadratic in $n$.
We show how random-sampling and bucketing techniques
can be used to develop a near-linear-time Monte Carlo algorithm
that computes a placement of $C$ containing
at least $(1-\eps) \kappa^*$ points of $S$, for
given $\eps>0$, with high probability.
Finally, we present a deterministic algorithm that
solves the $\eps$-approximate version of the optimal-placement
problem for convex $m$-gons in $O(n^{1+\delta} + (n/\eps)\log m)$ time,
for arbitrary constant $\delta>0$.
%, for convex $m$-gons.
Springer
2002
Conference-Paper
http://edoc.mpg.de/202060
urn:ISSN:0302-9743
Algorithms - ESA 2002 : 10th Annual European Symposium, Springer, 42-53 (2002)
en
oai:edoc.mpg.de:2020612012-09-1987:931
Lower Bounds & Competitive Algorithms for Online Scheduling of Unit-Size Tasks to Related Machines
Kontogiannis, Spyros
In this paper we study the problem of assigning unit-size tasks to
related machines when only limited online information is provided
to each task. This is a general framework whose special cases are
the classical multiple-choice games for the assignment of
unit-size tasks to identical machines. The latter case was the
subject of intensive research for the last decade. The problem is
intriguing in the sense that the natural extensions of the greedy
oblivious schedulers, which are known to achieve near-optimal
performance in the case of identical machines, are proved to
perform quite poorly in the case of the related machines.
In this work we present a rather surprising lower bound stating
that any oblivious scheduler that assigns an arbitrary number of
tasks to $n$ related machines would need $\Omega\left(\frac{\log
n}{\log\!\log n}\right)$ polls of machine loads per task, in order to
achieve a constant competitive ratio versus the optimum offline
assignment of the same input sequence to these machines. On the
other hand, we prove that the missing information for an oblivious
scheduler to perform almost optimally, is the amount of tasks to
be inserted into the system. In particular, we provide an
oblivious scheduler that only uses $\cal{O}(\log\!\log n)$ polls, along with
the additional information of the size of the input sequence, in
order to achieve a constant competitive ratio vs. the optimum
offline assignment. The philosophy of this scheduler is based on
an interesting exploitation of the {\sc slowfit} concept
([AAFPW97,BFN00,BCK97]; for a survey see
[BY98,Azar98,Sgall98]) for the assignment of the tasks to the
related machines despite the restrictions on the provided online
information, in combination with a layered induction argument for
bounding the tails of the number of tasks passing from slower to
faster machines. We finally use this oblivious scheduler as the
core of an adaptive scheduler that does not demand the knowledge
of the input sequence and yet achieves almost the same
performance.
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.
2002
Conference-Paper
http://edoc.mpg.de/202061
Proceedings of the 34th ACM Symposium on Theory of Computing (STOC-02), ACM, 124-133 (2002)
en
oai:edoc.mpg.de:2020622012-09-1987:931
Computing the threshold for q-gram filters
Kärkkäinen, Juha
Penttonen, Martti
Meineche Schmidt, Erik
A popular and much studied class of filters for approximate string
matching is based on finding common $q$-grams, substrings of length
$q$, between the pattern and the text. A variation of the basic idea uses
\emph{gapped} $q$-grams and has been recently shown to provide
significant improvements in practice. A major difficulty with gapped
$q$-gram filters is the computation of the so-called \emph{threshold}
which defines the filter criterium. We describe the first general
method for computing the threshold for $q$-gram filters. The method is
based on a carefully chosen precise statement of the problem which is
then transformed into a constrained shortest path problem.
In its generic form the method leaves certain parts open
but is applicable to a large variety of $q$-gram filters and may be
extensible even to other classes of filters. We also give a full
algorithm for a specific subclass. For this subclass, the algorithm
has been implemented and used succesfully in an experimental
comparison.
Springer
2002
Conference-Paper
http://edoc.mpg.de/202062
urn:ISBN:3-540-43866-1
Algorithm theory, SWAT 2002 : 8th Scandinavian Workshop on Algorithm Theory, Springer, 348-357 (2002)
en
oai:edoc.mpg.de:2020632012-09-1987:931
Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks
Jansen, Klaus
Porkolab, Lorant
2002
Article
http://edoc.mpg.de/202063
urn:ISSN:0178-4617
Algorithmica, v.32, 507-520 (2002)
en
oai:edoc.mpg.de:2020642012-09-1987:931
A Polyhedral Approach to Surface Reconstruction from Planar Contours.
Althaus, Ernst
Fink, Christian
Cook, William J.
Schulz, Andreas S.
We investigate the problem of reconstruction a surface given its contours on
parallel slices. We present a branch-and-cut algorithm which computes the
surface with the minimal area. This surface is assumed to be the best
reconstruction since a long time. Nevertheless there were no algorithms to
compute this surface. Our experiments show that the running time of our
algorithm is very reasonable and that the computed surfaces are highly similar
to the original surfaces.
Springer
2002
Conference-Paper
http://edoc.mpg.de/202064
urn:ISBN:3-540-43676-6
Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization, Springer, 258-272 (2002)
en
oai:edoc.mpg.de:2020652012-09-1987:931
Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics
Althaus, Ernst
Caprara, Alberto
Lenhof, Hans-Peter
Reinert, Knut
Lengauer, Thomas
Multiple sequence alignment is one of the dominant problems in computational
molecular biology. Numerous scoring functions and methods have been proposed,
most of which result in NP-hard problems. In this paper we propose for the
first time a general formulation for multiple alignment with arbitrary
gap-costs based on an integer linear program (ILP). In addition we describe a
branch-and-cut algorithm to effectively solve the ILP to optimality. We
evaluate the performances of our approach in terms of running time and quality
of the alignments using the BAliBase database of reference alignments. The
results show that our implementation ranks amongst the best programs developed
so far.
Oxford University Press
2002
Conference-Paper
http://edoc.mpg.de/202065
Proceedings of the European Conference on Computational Biology (ECCB 2002), Oxford University Press, S4-S16 (2002)
en
oai:edoc.mpg.de:2020662012-09-1987:931
SCIL - Symbolic Constraints in Integer Linear Programming.
Althaus, Ernst
Bockmayr, Alexander
Elf, Matthias
Kasper, Thomas
Jünger, Michael
Mehlhorn, Kurt
Möhring, Rolf
Raman, Rajeev
We describe a new software system SCIL that introduces symbolic constraints
into branch-and-cut-and-price algorithms for integer linear programs. Symbolic
constraints are known from constraint programming and contribute significantly
to the expressive power, ease of use, and efficiency of constraint programming
systems.
Springer
2002
Conference-Paper
http://edoc.mpg.de/202066
urn:ISBN:3-540-44180-8
Algorithms - ESA 2002 : 10th Annual European Symposium, Springer, 75-87 (2002)
en
oai:edoc.mpg.de:2020672012-09-1987:931
Exploring unkown environments with obstacles
Albers, Susanne
Kursawe, Klaus
Schuierer, Sven
2002
Article
http://edoc.mpg.de/202067
urn:ISSN:0178-4617
Algorithmica, v.32, 123-143 (2002)
en
oai:edoc.mpg.de:2020682012-09-1987:931
On the competitive theory and practice of online list accessing algorithms
Bachrach, Ran
El-Yaniv, Ran
Reinstädtler, Martin
2002
Article
http://edoc.mpg.de/202068
urn:ISSN:0178-4617
Algorithmica, v.32, 201-246 (2002)
en
oai:edoc.mpg.de:2020692012-09-1987:931
Approximation algorithms for maximum two-dimensional pattern matching
Arikati, Srinivasa Rao
Dessmark, Anders
Lingas, Andrzej
Marathe, Madhav V.
2001
Article
http://edoc.mpg.de/202069
urn:ISSN:0304-3975
Theoretical Computer Science, v.255, 51-62 (2001)
en
oai:edoc.mpg.de:2020702012-09-1987:931
On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-Completeness and Approximations
Andreou, Maria
Fotakis, Dimitris
Nikoletseas, Sotiris
Papadopoulou, Vicky
Spirakis, Paul G.
Diks, Krzysztof
Rytter, Wojciech
Hierarchical specifications of graphs have been widely used in many important
applications, such as VLSI design, parallel programming and software
engineering. A well known hierarchical specification model, considered in this
work, is that of Lengauer [9, 10] referred to as L-specifications. In this
paper we discuss a restriction on the L-specifications resulting to graphs
which we call Well-Separated (WS). This class is characterized by a polynomial
time (to the size of the specification of the graph) testable combinatorial
property.
In this work we study the Radiocoloring Problem (RCP) on WS L-specified
hierarchical planar graphs. The optimization version of RCP studied here,
consists in assigning colors to the vertices of a graph, such that any two
vertices of distance at most two get different colors. The objective here is to
minimize the number of colors used. This problem is equivalent to the problem
of vertex coloring the square of a graph $G$, $G^2$, where $G^2$ has the same
vertex set as $G$ and there is an edge between any two vertices of $G^2$ if
their distance in $G$ is at most 2.
We first show that RCP is PSPACE-complete for WS L-specified hierarchical
planar graphs. Second, we present a polynomial time 3-approximation algorithm
as well as a more efficient 4-approximation algorithm for RCP on graphs of this
class.
We note that, the best currently known approximation ratio for the RCP on
ordinary (non-hierarchical) planar graphs of general degree is 2 ([6, 1]). Note
also that the only known results on any kind of coloring problems have been
shown for another special kind of hierarchical graphs (unit disk graphs)
achieving a 6-approximation solution [13].
Springer
2002
Conference-Paper
http://edoc.mpg.de/202070
urn:ISBN:3-540-44040-2
Mathematical Foundations of Computer Science 2002 : 27th International Symposium, MFCS 2002, Springer, 81-92 (2002)
en
oai:edoc.mpg.de:2020712012-09-1987:931
A combinatorial approach to protein docking with flexible side chains
Althaus, Ernst
Kohlbacher, Oliver
Lenhof, Hans-Peter
Müller, Peter
2002
Article
http://edoc.mpg.de/202071
urn:ISSN:1066-5277
Journal of Computational Biology, v.9, 597-612 (2002)
en
oai:edoc.mpg.de:2020722012-09-1987:931
An O(n log n) algorithm for the maximum agreement subtree problem for binary trees
Cole, Richard
Farach-Colton, Martin
Hariharan, Ramesh
Przytycka, Teresa
Thorup, Mikkel
2000
Article
http://edoc.mpg.de/202072
urn:ISSN:0097-5397
SIAM Journal on Computing, v.30, 1385-1404 (2000)
en
oai:edoc.mpg.de:2020732012-09-1987:931
One-Gapped q-Gram Filters for Levenshtein Distance
Burkhardt, Stefan
Kärkkäinen, Juha
Apostolico, Alberto
Takeda, Masayuki
We have recently shown that $q$-gram filters based on gapped $q$-grams
instead of the usual contiguous $q$-grams can provide orders of
magnitude faster and/or more efficient filtering for the Hamming
distance. In this paper, we extend the results for the Levenshtein
distance, which is more problematic for gapped $q$-grams because an
insertion or deletion in a gap affects a $q$-gram while a
replacement does not. To keep this effect under control, we
concentrate on gapped $q$-grams with just one gap. We demostrate with
experiments that the resulting filters provide a significant
improvement over the contiguous $q$-gram filters. We also develop new
techniques for dealing with complex $q$-gram filters.
Springer
2002
Conference-Paper
http://edoc.mpg.de/202073
urn:ISBN:3-540-43862-9
Combinatorial Pattern Matching : 13th Annual Symposium, CPM 2002, Springer, 225-234 (2002)
en
oai:edoc.mpg.de:2020742012-09-1987:931
Generating Functions for Generating Trees
Banderier, Cyril
Bousquet-Mélou, Mireille
Denise, Alain
Flajolet, Philippe
Gardy, Danièle
Gouyou-Beauchamps, Dominique
2002
Article
http://edoc.mpg.de/202074
urn:ISSN:0012-365X
Discrete Mathematics, v.246, 29-55 (2002)
en
oai:edoc.mpg.de:2020752012-09-1987:931
Algorithm Engineering for Parallel Computation
Bader, David
Moret, Bernard
Sanders, Peter
Fleischer, Rudolf
Moret, Bernard
Meineche Schmidt, Erik
The emerging discipline of algorithm engineering has primarily focussed
on transforming pencil-and-paper sequential algorithms into
robust, efficient, well tested, and easily used implementations. As
parallel computing becomes ubiquitous, we need to extend algorithm
engineering techniques to parallel computation. Such an extension
adds significant complications. After a short review of algorithm
engineering achievements for sequential computing, we review the various
complications caused by parallel computing, present some examples of
successful efforts, and give a personal view of possible future research.
Springer
2002
InBook
http://edoc.mpg.de/202075
urn:ISBN:3-540-00346-0
Experimental Algorithmics, 1-23 (2002)
en
oai:edoc.mpg.de:2020762012-09-1987:931
Efficient Collision Detection for Curved Solid Objects
Schömer, Elmar
Reichel, Joachim
Warken, Thomas
Lennerz, Christian
Lee, Kunwoo
Patrikalakis, Nicholas M.
The design-for-assembly technique requires realistic physically based
simulation algorithms and in particular efficient geometric collision
detection routines. Instead of approximating mechanical parts by large
polygonal models, we work with the much smaller original CAD-data directly,
thus avoiding precision and tolerance problems.
We present a generic algorithm, which can decide whether two solids intersect
or not. We identify classes of objects for which this algorithm can be
efficiently specialized, and describe in detail how this specialization is
done. These classes are objects that are bounded by quadric surface patches and
conic arcs, objects that are bounded by natural quadric patches, torus patches,
line segments and circular arcs, and objects that are
bounded by quadric surface patches, segments of quadric intersection curves and
segments of cubic spline curves. We show that all necessary geometric
predicates can be evaluated by finding the roots of univariate polynomials of
degree at most $4$ for the first two classes, and at most $8$ for the third
class.
In order to speed up the intersection tests we
use bounding volume hierarchies. With the help of numerical
optimization techniques we succeed in calculating smallest enclosing spheres
and bounding boxes for a given set of surface patches fulfilling the properties
mentioned above.
ACM
2002
Conference-Paper
http://edoc.mpg.de/202076
urn:ISBN:1-58113-506-8
Proceedings of the Seventh {ACM} Symposium on Solid Modeling and Applications, ACM, 321-328 (2002)
en
oai:edoc.mpg.de:2020772012-09-1987:931
Feasible models of computation: Three-dimensionality and energy consumption
Sanders, Peter
Vollmar, R.
Worsch, T.
2002
Article
http://edoc.mpg.de/202077
urn:ISSN:0169-2968
Fundamenta Informaticae, v.52, 233-248 (2002)
en
oai:edoc.mpg.de:2020782012-09-1987:931
Selfish Traffic Allocation for Server Farms
Czumaj, Artur
Krysta, Piotr
Vöcking, Berthold
ACM
2002
Conference-Paper
http://edoc.mpg.de/202078
Proceedings of the 34th ACM Symposium on Theory of Computing (STOC-02), ACM, 287-296 (2002)
en
oai:edoc.mpg.de:2020792012-09-1987:931
Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems
Csaba, Bela
Krysta, Piotr
Karpinski, Marek
ACM
2002
Conference-Paper
http://edoc.mpg.de/202079
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-02), ACM, 74-83 (2002)
en
oai:edoc.mpg.de:2020802012-09-1987:931
Surface Topography Quantification by Integral and Feature-related Parameters
Wendt, Ulrich
Lange, Katharina
Smid, Michiel
Ray, Rahul
Tönnies, Klaus-Dietz
Using topographical images obtained by confocal laser scanning microscopy, the
topography of brittle fracture
surfaces and wire-eroded surfaces was quantified. The global topometry values
show a significant dependency
on the imaging conditions and on the computing algorithm. An algorithm was
developed and implemented for the
automatic detection and measuring of feature-related parameters in
topographies, which uses methods of
computational geometry. The software was tested using brittle fracture surfaces
of steel.
2002
Article
http://edoc.mpg.de/202080
urn:ISSN:1521-4052
Materialwissenschaft und Werkstofftechnik, v.33, 621-627 (2002)
en
ResultSet_8pEduQ3GZFv_range_100-199