2020-10-24T16:09:14Zhttp://edoc.mpg.de/ac_ft_oai.ploai:edoc.mpg.de:2018342012-09-1987:931
Conference-Paper
Approximating Energy Efficient Paths in Wireless Multi-hop Networks
English
Springer
Berlin, Germany
2003
2004-06-15
230
241
Budapest, Hungary
2003-09-16
Algorithms - ESA 2003: 11th Annual European Symposium
Lecture Notes in Computer Science
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$.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9141&did=201834&ver=0
S.
Funke
Stefan
D.
Matijevic
Domagoj
P.
Sanders
Peter
G.
Di Battista
Giuseppe
U.
Zwick
Uri
3-540-20064-9
C1256428004B93B8-1EAC93284072E6C4C1256E150042DA25-Matijevic2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018352012-09-1987:931
Conference-Paper
On the Competitive Ratio for Online Facility Location
English
Springer
Berlin, Germany
2003
2004-06-15
637
652
Eindhoven, The Netherlands
2003-06-30
Automata, languages and programming : 30th International Colloquium, ICALP 2003
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9142&did=201835&ver=0
D.
Fotakis
Dimitris
J.C.M.
Baeten
Jos C.M.
J.K.
Lenstra
Jan Karel
J.
Parrow
Joachim
G.J.
Woeginger
Gerhard J.
3-540-40493-7
C1256428004B93B8-6A9C56FA859349F5C1256D030043742D-Fot03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018572012-09-1987:931
Conference-Paper
Space Efficient Hash Tables with Worst Case Constant Access Time
English
Springer
Berlin, Germany
2003
2004-06-11
271
282
Berlin, Germany
2003-02-27
Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003)
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9148&did=201857&ver=0
D.
Fotakis
Dimitris
R.
Pagh
Rasmus
P.
Sanders
Peter
P.G.
Spirakis
Paul G.
H.
Alt
Helmut
M.
Habib
Michel
3-540-00623-0
C1256428004B93B8-6A3318B88A19B993C1256CD800533F95-FPSS03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018692012-09-1987:931
Conference-Paper
Fast Lightweight Suffix Array Construction and Checking
English
Springer
Heidelberg, Germany
2003
2004-08-02
55
69
Morelia, Michoacán, Mexico
2003-06-25
Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9149&did=201869&ver=0
S.
Burkhardt
Stefan
J.
Kärkkäinen
Juha
R.
Baeza-Yates
R.
E.
Chávez
E.
M.
Crochemore
M.
0302-9743
C1256428004B93B8-3E2B1773D0314EDEC1256E8A002B0F6D-Burkhardt2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019802012-09-1987:931
Article
Randomized Pursuit-Evasion in Graphs
English
2003
2004-06-15
225
244
Combinatorics, Probability and Computing
12
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9170&did=201980&ver=0
M.
Adler
Micah
H.
Räcke
Harald
N.
Sivadasan
Naveen
C.
Sohler
Christian
B.
Vöcking
Berthold
0963-5483
C1256428004B93B8-84FD4682AF9079ECC1256EAC0033DB77-Sivadas2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020442012-09-1987:931
Conference-Paper
Smoothed Analysis of Three Combinatorial Problems
English
Springer
Berlin, Germany
2003
2004-06-15
198
207
Bratislava, Slovak Republic
2003-08-25
Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9181&did=202044&ver=0
C.
Banderier
Cyril
R.
Beier
Rene
K.
Mehlhorn
Kurt
B.
Rovan
Branislav
P.
Vojtáš
Peter
3-540-40671-9
C1256428004B93B8-09CF39E77E5072D5C1256E140059E6C7-Beier2003a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311772012-09-1987:931
Conference-Paper
Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems
English
Springer
Berlin, Germany
2004
2005-04-22
122
133
Bergen, Norway
2004-09-14
Algorithms – ESA 2004: 12th Annual European Symposium
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13318&did=231177&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
S.
Albers
Susanne
T.
Radzik
Tomasz
3-540-23025-4
C1256428004B93B8-F7189E64F086B362C1256FB1004BD7DC-Elbassioni2004g
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311782012-09-1987:931
Conference-Paper
Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems
English
Springer
Berlin, Germany
2004
2005-04-21
152
162
New York, NY, USA
2004-06-07
Integer programming and combinatorial optimization : 10th International IPCO Conference
Lecture Notes in Computer Science
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.
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=13319&did=231178&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
L.
Khachiyan
Leonid
D.
Bienstock
Daniel
G.
Nemhauser
George
3-540-22113-1
C1256428004B93B8-A571696CD00A38AEC1256FB1004ACE90-Elbassioni2004e
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311792012-09-1987:931
Conference-Paper
Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections
English
Springer
Berlin, Germany
2004
2005-05-23
488
498
Buenos Aires, Argentina
2004-04-05
LATIN 2004: Theoretical Informatics, 6th Latin American Symposium
Lecture Notes in Computer Science
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$.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13320&did=231179&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
L.
Khachiyan
Leonid
M.
Farach-Colton
Martin
3-540-21258-2
C1256428004B93B8-8FD2B06B5B82875EC1256FB1004A73B8-Elbassioni2004d
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311802012-09-1987:931
Conference-Paper
Generating Paths and Cuts in Multi-pole (Di)graphs
English
Springer
Berlin, Germany
2004
2005-04-26
298
309
Prague, Czech Republic
2004-08-22
Mathematical foundations of computer science 2004 : 29th International Symposium, MFCS 2004
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13321&did=231180&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
L.
Khachiyan
Leonid
K.
Makino
Kazuhisa
J.
Fiala
Jirí
V.
Koubek
Václav
J.
Kratochvíl
Jan
3-540-22823-3
C1256428004B93B8-028218E7F7706A18C1256FB0006AFB8D-Elbassioni2004b
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311812012-09-1987:931
Conference-Paper
An Efficient Implementation of a Joint Generation Algorithm
English
Springer
Berlin, Germany
2004
2005-04-21
114
128
Angra dos Reis, Brazil
2004-05-25
Experimental and efficient algorithms : Third International Workshop, WEA 2004
Lecture Notes in Computer Science
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$.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13322&did=231181&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
L.
Khachiyan
Leonid
C.C.
Ribeiro
Celso C.
S.L.
Martins
Simone L.
3-540-22067-4
C1256428004B93B8-6A93A5BCF0711754C1256FB0006A0E15-Elbassioni2004a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311882012-09-1987:931
Conference-Paper
Engineering an External Memory Minimum Spanning Tree Algorithm
English
Kluwer
Norwell, USA
2004
2005-05-30
195
208
Toulouse, France
2004-08-23
3rd IFIP International Conference on Theoretical Computer Science (TSC2004)
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13323&did=231188&ver=0
R.
Dementiev
Roman
P.
Sanders
Peter
D.
Schultes
Dominik
J.F.
Sibeyn
Jop F.
J.-J.
Lévy
Jean-Jacques
E.W.
Mayr
Ernst W.
J.C.
Mitchell
John C.
1-4020-8140-5
C1256428004B93B8-3C2394B7B7DA31D3C1256FA9004CA46A-DSSS04
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311922012-09-1987:931
Conference-Paper
Algorithms for recognizing coordinates in two variables over UFD's
English
ACM
New York, USA
2004
2005-06-07
135
140
Santander, Spain
2005-02-25
Proceedings of the 2004 International Symposium Symbolic and Algebraic Computation (ISSAC-04)
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13326&did=231192&ver=0
M.
El Kahoui
M'hammed
J.
Gutierrez
Jaime
1-58113-827-X
C1256428004B93B8-09E211DD8F4E6F84C1256FB30050DE55-ElKahoui2004c
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311932012-09-1987:931
Conference-Paper
Scalable Multimedia Disk Scheduling
English
IEEE
Los Alamitos, USA
2004
2005-04-21
498
509
Boston, USA
2004-03-30
20th International Conference on Data Engineering, ICDE 2004
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13327&did=231193&ver=0
K.
Elbassioni
Khaled
M.F.
Mokbel
Mohamed F.
W.G.
Aref
Walid G.
I.
Kamel
Ibrahim
0-7695-2065-0
C1256428004B93B8-49B9CE582EADDFEAC1256FB1004B66A2-Elbassioni2004f
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311942012-09-1987:931
Conference-Paper
Incremental Algorithms for Facility Location and k-Median
English
Springer
Berlin, Germany
2004
2005-04-22
347
358
Bergen, Norway
2004-09-14
Algorithms – ESA 2004: 12th Annual European Symposium
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13328&did=231194&ver=0
D.
Fotakis
Dimitris
S.
Albers
Susanne
T.
Radzik
Tomasz
3-540-23025-4
C1256428004B93B8-BB4F865FF034AAE3C1256FB4004B625B-Fotakis2004a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311992012-09-1987:931
Conference-Paper
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks
English
University of Bologna
Bologna, Italy
2004
2005-02-02
97
111
Boston, USA
2004-08-26
First International Workshop on Algorithms for Wireless and Mobile Networks
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13329&did=231199&ver=0
S.
Funke
Stefan
D.
Matijevic
Domagoj
P.
Sanders
Peter
C1256428004B93B8-E48460D48DE204C1C1256F88003F7310-FMS2004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2312222012-09-1987:931
Article
A simpler linear time 2/3 - eps approximation for maximum weight matching
English
2004
2005-05-30
271
276
Information Processing Letters
91
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=13332&did=231222&ver=0
S.
Pettie
Seth
P.
Sanders
Peter
C1256428004B93B8-8C86AC1B497A2DDEC1256F8800518407-PettieSanders2004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2312242012-09-1987:931
Conference-Paper
Online scheduling with bounded migration
English
Springer
Berlin, Germany
2004
2005-05-23
1111
1122
Turku, Finnland
2004-07-12
Automata, languages and programming : 31st International Colloquium, ICALP 2004
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13333&did=231224&ver=0
P.
Sanders
Peter
N.
Sivadasan
Naveen
M.
Skutella
Martin
J.
Díaz
Josep
J.
Karhumäki
Juhani
A.
Lepistö
Arto
D.
Sannella
Donald
3-540-22849-7
C1256428004B93B8-AA794B91E683A1DEC1256F56004941D7-Sivadasan2004-2
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2312262012-09-1987:931
Conference-Paper
Topology matters: Smoothed competitiveness of metrical task systems
English
Springer
Berlin, Germany
2004
2005-05-23
489
500
Montpellier, France
2004-03-25
21st Annual Symposium on Theoretical Aspects of Computer Science (STACS-04)
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13334&did=231226&ver=0
G.
Schäfer
Guido
N.
Sivadasan
Naveen
V.
Diekert
Volker
M.
Habib
Michel
3-540-21236-1
C1256428004B93B8-7F33404549ADEA5DC1256F560048EE68-Sivadasan2004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2312312012-09-1987:931
Thesis
Controlled Perturbation for Voronoi Diagrams
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-06-17
expertsonly
http://edoc.mpg.de/get.epl?fid=13335&did=231231&ver=0
C.
Klein
Christian
C1256428004B93B8-407186B9B72B2A1DC1256FA2005A295A-Klein2004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2318842012-09-1987:931
Conference-Paper
Scalable Multimedia Disk Scheduling
English
IEEE
Los Alamitos, USA
2004
2005-04-21
498
509
Boston, USA
2004-03-30
20th International Conference on Data Engineering, ICDE 2004
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13485&did=231884&ver=0
K.
Elbassioni
Khaled
M.F.
Mokbel
Mohamed F.
W.G.
Aref
Walid G.
I.
Kamel
Ibrahim
0-7695-2065-0
C1256428004B93B8-49B9CE582EADDFEAC1256FB1004B66A2-Elbassioni2004f
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2319722012-09-1987:931
Article
A simpler linear time 2/3 - eps approximation for maximum weight matching
English
2004
2005-05-30
271
276
Information Processing Letters
91
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=13507&did=231972&ver=0
S.
Pettie
Seth
P.
Sanders
Peter
C1256428004B93B8-8C86AC1B497A2DDEC1256F8800518407-PettieSanders2004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2319842012-09-1987:931
Conference-Paper
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks
English
University of Bologna
Bologna, Italy
2004
2005-02-02
97
111
Boston, USA
2004-08-26
First International Workshop on Algorithms for Wireless and Mobile Networks
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13508&did=231984&ver=0
S.
Funke
Stefan
D.
Matijevic
Domagoj
P.
Sanders
Peter
C1256428004B93B8-E48460D48DE204C1C1256F88003F7310-FMS2004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2319892012-09-1987:931
Conference-Paper
Online scheduling with bounded migration
English
Springer
Berlin, Germany
2004
2005-05-23
1111
1122
Turku, Finnland
2004-07-12
Automata, languages and programming : 31st International Colloquium, ICALP 2004
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13509&did=231989&ver=0
P.
Sanders
Peter
N.
Sivadasan
Naveen
M.
Skutella
Martin
J.
Díaz
Josep
J.
Karhumäki
Juhani
A.
Lepistö
Arto
D.
Sannella
Donald
3-540-22849-7
C1256428004B93B8-AA794B91E683A1DEC1256F56004941D7-Sivadasan2004-2
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2319962012-09-1987:931
Conference-Paper
Incremental Algorithms for Facility Location and k-Median
English
Springer
Berlin, Germany
2004
2005-04-22
347
358
Bergen, Norway
2004-09-14
Algorithms – ESA 2004: 12th Annual European Symposium
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13510&did=231996&ver=0
D.
Fotakis
Dimitris
S.
Albers
Susanne
T.
Radzik
Tomasz
3-540-23025-4
C1256428004B93B8-BB4F865FF034AAE3C1256FB4004B625B-Fotakis2004a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2320002012-09-1987:931
Conference-Paper
Algorithms for recognizing coordinates in two variables over UFD's
English
ACM
New York, USA
2004
2005-06-07
135
140
Santander, Spain
2005-02-25
Proceedings of the 2004 International Symposium Symbolic and Algebraic Computation (ISSAC-04)
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13512&did=232000&ver=0
M.
El Kahoui
M'hammed
J.
Gutierrez
Jaime
1-58113-827-X
C1256428004B93B8-09E211DD8F4E6F84C1256FB30050DE55-ElKahoui2004c
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2320082012-09-1987:931
Conference-Paper
Engineering an External Memory Minimum Spanning Tree Algorithm
English
Kluwer
Norwell, USA
2004
2005-05-30
195
208
Toulouse, France
2004-08-23
3rd IFIP International Conference on Theoretical Computer Science (TSC2004)
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13516&did=232008&ver=0
R.
Dementiev
Roman
P.
Sanders
Peter
D.
Schultes
Dominik
J.F.
Sibeyn
Jop F.
J.-J.
Lévy
Jean-Jacques
E.W.
Mayr
Ernst W.
J.C.
Mitchell
John C.
1-4020-8140-5
C1256428004B93B8-3C2394B7B7DA31D3C1256FA9004CA46A-DSSS04
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2320242012-09-1987:931
Conference-Paper
Topology matters: Smoothed competitiveness of metrical task systems
English
Springer
Berlin, Germany
2004
2005-05-23
489
500
Montpellier, France
2004-03-25
21st Annual Symposium on Theoretical Aspects of Computer Science (STACS-04)
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13517&did=232024&ver=0
G.
Schäfer
Guido
N.
Sivadasan
Naveen
V.
Diekert
Volker
M.
Habib
Michel
3-540-21236-1
C1256428004B93B8-7F33404549ADEA5DC1256F560048EE68-Sivadasan2004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2320262012-09-1987:931
Conference-Paper
An Efficient Implementation of a Joint Generation Algorithm
English
Springer
Berlin, Germany
2004
2005-04-21
114
128
Angra dos Reis, Brazil
2004-05-25
Experimental and efficient algorithms : Third International Workshop, WEA 2004
Lecture Notes in Computer Science
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$.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13518&did=232026&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
L.
Khachiyan
Leonid
C.C.
Ribeiro
Celso C.
S.L.
Martins
Simone L.
3-540-22067-4
C1256428004B93B8-6A93A5BCF0711754C1256FB0006A0E15-Elbassioni2004a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2320272012-09-1987:931
Conference-Paper
Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections
English
Springer
Berlin, Germany
2004
2005-05-23
488
498
Buenos Aires, Argentina
2004-04-05
LATIN 2004: Theoretical Informatics, 6th Latin American Symposium
Lecture Notes in Computer Science
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$.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13519&did=232027&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
L.
Khachiyan
Leonid
M.
Farach-Colton
Martin
3-540-21258-2
C1256428004B93B8-8FD2B06B5B82875EC1256FB1004A73B8-Elbassioni2004d
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2320302012-09-1987:931
Conference-Paper
Generating Paths and Cuts in Multi-pole (Di)graphs
English
Springer
Berlin, Germany
2004
2005-04-26
298
309
Prague, Czech Republic
2004-08-22
Mathematical foundations of computer science 2004 : 29th International Symposium, MFCS 2004
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13521&did=232030&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
L.
Khachiyan
Leonid
K.
Makino
Kazuhisa
J.
Fiala
Jirí
V.
Koubek
Václav
J.
Kratochvíl
Jan
3-540-22823-3
C1256428004B93B8-028218E7F7706A18C1256FB0006AFB8D-Elbassioni2004b
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2320362012-09-1987:931
Conference-Paper
Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems
English
Springer
Berlin, Germany
2004
2005-04-22
122
133
Bergen, Norway
2004-09-14
Algorithms – ESA 2004: 12th Annual European Symposium
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13525&did=232036&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
S.
Albers
Susanne
T.
Radzik
Tomasz
3-540-23025-4
C1256428004B93B8-F7189E64F086B362C1256FB1004BD7DC-Elbassioni2004g
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2320522012-09-1987:931
Thesis
Controlled Perturbation for Voronoi Diagrams
English
Universität des Saarlandes
Saarbrücken, Saarland
2004
2005-06-17
expertsonly
http://edoc.mpg.de/get.epl?fid=13526&did=232052&ver=0
C.
Klein
Christian
C1256428004B93B8-407186B9B72B2A1DC1256FA2005A295A-Klein2004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2378732012-09-1987:931
Report
On the Hadwiger's conjecture for graph products
English
Max-Planck-Institut für Informatik
Saarbrücken
2004
2004-1-006
Max-Planck-Institut für Informatik <Saarbrücken>: Research Report
Max-Planck-Institut für Informatik <Saarbrücken>
expertsonly
10 p.
http://edoc.mpg.de/get.epl?fid=14944&did=237873&ver=0
L. S.
Chandran
L. Sunil
N.
Sivadasan
Naveen
MPI-I-2004-1-006
MPI für Informatik
Discrete Optimization Group
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2378752012-09-1987:931
Report
A comparison of polynomial evaluation schemes
English
Max-Planck-Institut für Informatik
Saarbrücken
2004-06
2004-1-005
Max-Planck-Institut für Informatik <Saarbrücken>: Research Report
Becker
Max-Planck-Institut für Informatik <Saarbrücken>
16 p.
http://edoc.mpg.de/get.epl?fid=14946&did=237875&ver=0
S.
Schmitt
Susanne
L.
Fousse
Laurent
MPI-I-2004-1-005
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2378772012-09-1987:931
Report
On scheduling with bounded migration
English
Max-Planck-Institut für Informatik
Saarbrücken
2004-05
2004-1-004
Max-Planck-Institut für Informatik <Saarbrücken>: Research Report
Max-Planck-Institut für Informatik <Saarbrücken>
expertsonly
22 p.
http://edoc.mpg.de/get.epl?fid=14947&did=237877&ver=0
N.
Sivadasan
Naveen
P.
Sanders
Peter
M.
Skutella
Martin
MPI-I-2004-1-004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2378782012-09-1987:931
Report
On algorithms for online topological ordering and sorting
English
Max-Planck-Institut für Informatik
Saarbrücken
2004-02
2004-1-003
Max-Planck-Institut für Informatik <Saarbrücken>: Research Report
Max-Planck-Institut für Informatik <Saarbrücken>
expertsonly
12 p.
http://edoc.mpg.de/get.epl?fid=14948&did=237878&ver=0
I.
Katriel
Irit
MPI-I-2004-1-003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2378802012-09-1987:931
Report
A simpler linear time 2/3-epsilon approximation
English
Max-Planck-Institut für Informatik
Saarbrücken
2004-01
2004-1-002
Max-Planck-Institut für Informatik <Saarbrücken>: Research Report
Max-Planck-Institut für Informatik <Saarbrücken>
expertsonly
7 p.
http://edoc.mpg.de/get.epl?fid=14949&did=237880&ver=0
P.
Sanders
Peter
S.
Pettie
Seth
MPI-I-2004-1-002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2378812012-09-1987:931
Report
Filtering algorithms for the Same and UsedBy constraints
English
Max-Planck-Institut für Informatik
Saarbrücken
2004-01
2004-1-001
Max-Planck-Institut für Informatik <Saarbrücken>: Research Report
Max-Planck-Institut für Informatik <Saarbrücken>
expertsonly
33 p.
http://edoc.mpg.de/get.epl?fid=14950&did=237881&ver=0
N.
Beldiceanu
Nicolas
I.
Katriel
Irit
S.
Thiel
Sven
MPI-I-2004-1-001
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791222012-09-1987:931
Thesis
Earliest Arrival Flows with Multiple Sources
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-03-09
2005-05-01
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.
expertsonly
http://edoc.mpg.de/get.epl?fid=22482&did=279122&ver=0
I.
Rauf
Imran
C1256428004B93B8-81CC2A37110C3F80C1256FC500531D3E-RaufDiss04
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791342012-09-1987:931
Conference-Paper
The diamond operator - Implementation of exact real algebraic numbers
English
Springer
Berlin, Germany
2005
2006-06-13
355
366
Kalamata, Greece
2005-09-12
Computer Algebra in Scientific Computing, 8th International Workshop, CASC 2005
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=22483&did=279134&ver=0
S.
Schmitt
Susanne
V.G.
Ganzha
Victor G.
E.W.
Mayr
Ernst W.
E.V.
Vorozhtsov
Evgenii V.
3-540-28966-6
C1256428004B93B8-0BF8BC50D43BC010C1256FB2003F191A-Schmitt2005
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791412012-09-1987:931
Conference-Paper
Implementing Minimum Cycle Basis Algorithms
English
Springer
Berlin, Germany
2005
2006-06-13
32
43
Santorini, Greece
2005-05-10
Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=22484&did=279141&ver=0
K.
Mehlhorn
Kurt
D.
Michail
Dimitrios
S.
Nikoletseas
Sotiris
3-540-25920-1
C1256428004B93B8-AC9540F47424F880C1256FD400450006-MM05
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791522012-09-1987:931
Article
Energy efficient communication in ad hoc networks from user's and designer's perspective
English
2005
2006-06-19
15
26
ACM SIGMOBILE Mobile Computing and Communications Review
9
Automatic journal name synchronization
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=22485&did=279152&ver=0
A.
Kesselmann
Alexander
D.
Kowalski
Dariusz
M.
Segal
Michael
C1256428004B93B8-560E8651AB0437ADC1256FC4006B17C5-KKS
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791532012-09-1987:931
Thesis
Deterministic Random Walks on Infinite Grids
English
Friedrich-Schiller-Universität Jena
Saarbrücken, Saarland
2005
2006-04-20
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$.
expertsonly
http://edoc.mpg.de/get.epl?fid=22486&did=279153&ver=0
T.
Friedrich
Tobias
C1256428004B93B8-F340345DBC6308A4C125714300488CC3-Friedrich2005
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791582012-09-1987:931
Conference-Paper
A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs
English
Springer
Berlin, Germany
2005
2006-06-13
654
665
Stuttgart, Germany
2005-03-24
STACS 2005 : 22nd Annual Symposium on Theoretical Aspects of Computer Science
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=22487&did=279158&ver=0
T.
Kavitha
Telikepalli
K.
Mehlhorn
Kurt
V.
Diekert
Volker
B.
Durand
Bruno
3-540-24998-2
C1256428004B93B8-3DB3C11B363B1328C1256FBD005C3154-KM2005
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791622012-09-1987:931
Conference-Paper
Controlled Perturbation for Delaunay Triangulations
English
SIAM
Philadelphia, USA
2005
2006-06-13
1047
1056
Vancouver, Canada
2005-01-23
Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=22489&did=279162&ver=0
http://edoc.mpg.de/get.epl?fid=22488&did=279162&ver=0
S.
Funke
Stefan
C.
Klein
Christian
K.
Mehlhorn
Kurt
S.
Schmitt
Susanne
0-89871-585-7
C1256428004B93B8-51E79341608E6746C1256FA2005B7772-FKMS2005
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791702012-09-1987:931
Article
D-resultant and subresultants
$D$-resultant and subresultants
English
2005
2006-06-13
2193
2199
Proceedings of the Amercian Mathematical Society
133
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=22490&did=279170&ver=0
M.
El Kahoui
M'hammed
C1256428004B93B8-66FD31BB0D07D450C1256FB300514F17-ElKahoui2005b
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791712012-09-1987:931
Article
UFDs with commuting linearly independent locally nilpotent derivations
English
2005
2006-06-12
446
452
Journal of Algebra
289
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=22491&did=279171&ver=0
M.
El Kahoui
M'hammed
C1256428004B93B8-0034CE3CDD980BBCC1256FB3005196C9-ElKahoui2005c
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791742012-09-1987:931
Conference-Paper
Angel, Devil, and King
English
Springer
Berlin, Germany
2005
2005-11-17
925
934
Kunming, China
2005-08-16
Computing and Combinatorics : 11th Annual International Conference, COCOON 2005
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=22493&did=279174&ver=0
M.
Kutz
Martin
A.
Pór
Attila
L.
Wang
Lusheng
3-540-28061-8
C1256428004B93B8-3298060186D9451DC12570500030FB39-Kutz05
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791762012-09-1987:931
Conference-Paper
Energy-Aware Stage Illumination
English
ACM
New York, USA
2005
2005-11-16
336
346
Pisa, Italy
2005-06-06
Proceedings of the 21st Annual Symposium on Computational Geometry : (SCG05)
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=22494&did=279176&ver=0
F.
Eisenbrand
Friedrich
S.
Funke
Stefan
A.
Karrenbauer
Andreas
D.
Matijevic
Domagoj
1-58113-991-8
C1256428004B93B8-A30CE0AA99BB3B12C1256FB2004BD871-EFKM2005
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791772012-09-1987:931
Conference-Paper
A Descartes algorithm for polynomials with bit-stream coefficients
English
Springer
Berlin, Germany
2005
2006-04-04
138
149
Kalamata, Greece
2005-09-12
Computer Algebra in Scientific Computing : 8th International Workshop, CASC 2005
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=22495&did=279177&ver=0
A.
Eigenwillig
Arno
L.
Kettner
Lutz
W.
Krandick
Werner
K.
Mehlhorn
Kurt
S.
Schmitt
Susanne
N.
Wolpert
Nicola
V.G.
Ganzha
Viktor G.
E.W.
Mayr
Ernst W.
E.V.
Vorozhtsov
Evenii V.
3-540-28966-6
C1256428004B93B8-41C2916F50A109F2C1257092003B5C82-Eigenwillig2005
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791832012-09-1987:931
Conference-Paper
Better External Memory Suffix Array Construction
English
SIAM
Philadelphia, USA
2005
2006-06-16
86
97
Vancouver, British Columbia, Canada
2005-01-22
Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO 2005)
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.
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=22496&did=279183&ver=0
R.
Dementiev
Roman
J.
Kärkkäinen
Juha
J.
Mehnert
Jens
P.
Sanders
Peter
C.
Demetrescu
Camil
R.
Sedgewick
Robert
R.
Tamassia
Roberto
0-89871-596-2
C1256428004B93B8-3A3C24F177ACF9B2C1256FAC0057E187-DKMS05
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791892012-09-1987:931
Conference-Paper
EXACUS: Efficient and exact algorithms for curves and surfaces
English
Springer
Berlin, Germany
2005
2006-01-13
155
166
Palma de Mallorca, Spain
2005-10-03
13th Annual European Symposium on Algorithms (ESA 2005)
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=22497&did=279189&ver=0
E.
Berberich
Eric
A.
Eigenwillig
Arno
M.
Hemmer
Michael
S.
Hert
Susan
L.
Kettner
Lutz
K.
Mehlhorn
Kurt
J.
Reichel
Joachim
S.
Schmitt
Susanne
E.
Schömer
Elmar
N.
Wolpert
Nicola
G.S.
Brodal
Gerth S.
S.
Leonardi
Stefano
3-540-29118-0
C1256428004B93B8-D9CE0617730DAB73C1257050002DEDED-Berberich05
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791952012-09-1987:931
Conference-Paper
New Constructions of (alpha, beta)-Spanners and Purely Additive Spanners
English
SIAM
Philadelphia, USA
2005
2006-06-13
672
681
Vancouver, Canada
2005-01-23
Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=22498&did=279195&ver=0
S.
Baswana
Surender
T.
Kavitha
Telikepalli
K.
Mehlhorn
Kurt
S.
Pettie
Seth
0-89871-585-7
C1256428004B93B8-0AA8BBA59356C31EC1256FB90040183D-BaswanaEtal2005
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791962012-09-1987:931
Conference-Paper
All-pairs nearly 2-approximate shortest paths in $O(n^2 \mathrm polylog n)$ time
English
Springer
Berlin, Germany
2005
2005-08-01
666
679
Stuttgart, Germany
2005-03-08
STACS 2005 : 22nd Annual Symposium on Theoretical Aspects of Computer Science
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=22499&did=279196&ver=0
S.
Baswana
Surender
V.
Goyal
Vishrut
S.
Sen
Sandeep
V.
Diekert
Volker
B.
Durand
Bruno
3-540-24998-2
C1256428004B93B8-CDE770BF7CC4479FC1256FBE0037715A-BGS2005
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2791992012-09-1987:931
Conference-Paper
Why Spectral Retrieval Works
English
ACM
New York, USA
2005
2006-03-20
11
18
Salvador, Brazil
2005-08-15
Proceedings of SIGIR 2005 (SIGIR-05) : the Twenty-Eighth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval
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.
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=22500&did=279199&ver=0
H.
Bast
Holger
D.
Majumdar
Debapriyo
G.
Marchionini
Gary
A.
Moffat
Alistair
J.
Tait
John
R.
Baeza-Yates
Ricardo
N.
Ziviani
Nivio
1-58113-881-4
C1256428004B93B8-ADC0E49B750350FBC1256FE3003F05CA-bastmajumdar05sigir
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2792032012-09-1987:931
Conference-Paper
Pareto-optimality in house allocation problems
English
Springer
Berlin, Germany
2005
2006-06-13
3
15
Hong Kong, China
2004-12-20
Algorithms and Computation: 15th International Symposium, ISAAC 2004
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=22502&did=279203&ver=0
D.
Abraham
David
K.
Mehlhorn
Kurt
R.
Fleischer
Rudolf
G.
Trippen
G.
3-540-24131-0
C1256428004B93B8-01196620C777D8F5C1256FC40039D825-ACMM04
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2792042012-09-1987:931
Conference-Paper
Popular Matchings
English
SIAM
Philadelphia, USA
2005
2006-06-13
424
432
Vancouver, Canada
2005-01-23
Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=22503&did=279204&ver=0
D.
Abraham
David
R.
Irving
Robert
K.
Mehlhorn
Kurt
K.
Telikepalli
Kavitha
0-89871-585-7
C1256428004B93B8-463863EBA0A07CEEC1256FC400392258-AIKM05
MPI für Informatik
Algorithms and Complexity Group
2006
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3143612012-09-1987:931
Conference-Paper
(Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram
English
School of Computing, Queen's University
Kingston, Ontario, K7L 3N6, Canada
2006
2007-04-23
23
26
Kingston, Canada
2006-08-14
18th Canadian Conference on Computational Geometry
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35730&did=314361&ver=0
S.
Funke
Stefan
T.
Malamatos
Theocharis
D.
Matijevic
Domagoj
N.
Wolpert
Nicola
D.
Rappaport
David
C1256428004B93B8-07FA7E47F576294BC12571D500640CD3-FMMW2006
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3143672012-09-1987:931
Article
New bounds for the Descartes method
English
2006
2007-04-26
49
66
Journal of Symbolic Computation
41
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=35732&did=314367&ver=0
W.
Krandick
Werner
K.
Mehlhorn
Kurt
C1256428004B93B8-8291BD2AF8984049C12571C50041D379-mehlhorn06e
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3144032012-09-1987:931
Conference-Paper
Generating Randomized Roundings with Cardinality Constraints and Derandomizations
English
Springer
Berlin, Germany
2006
2007-04-26
571
583
Marseille, France
2006-02-23
STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35747&did=314403&ver=0
B.
Doerr
Benjamin
B.
Durand
Bruno
W.
Thomas
Wolfgang
3-540-32301-5
C1256428004B93B8-482118BCAB9812F7C125727A004F8EA3-DoerrStacs2006
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3144052012-09-1987:931
Conference-Paper
IO-Top-k: Index-Access Optimized Top-k Query Processing
English
ACM
New York, USA
2006
2007-04-16
475
486
Seoul, Korea
2006-09-12
Proceedings of the 32nd International Conference on Very Large Data Bases, VLDB 2006
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.
Doppeltes Papier: D1 & D2
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=35748&did=314405&ver=0
H.
Bast
Holger
D.
Majumdar
Debapriyo
R.
Schenkel
Ralf
M.
Theobald
Martin
G.
Weikum
Gerhard
U.
Dayal
Umeshwar
K.-Y.
Whang
Kyu-Young
D. B.
Lomet
David B.
G.
Alonso
Gustavo
G. M.
Lohman
Guy M.
M. L.
Kersten
Martin L.
S. K.
Cha
Sang Kyun
Y.-K.
Kim
Young-Kuk
1-59593-385-9
C1256428004B93B8-A4369BF160083CD6C1257188004AA310-BastMSTW2006a
MPI für Informatik
Algorithms and Complexity Group
MPI für Informatik
Databases and Information Systems Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3144202012-09-1987:931
Conference-Paper
Output-Sensitive Autocompletion Search
English
Springer
Berlin, Germany
2006
2007-02-05
150
162
Glasgow, GB
2006-10-11
String Processing and Information Retrieval : 13th International Conference, SPIRE 2006
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35753&did=314420&ver=0
H.
Bast
Holger
C.W.
Mortensen
Christian Worm
I.
Weber
Ingmar
F.
Crestani
Fabio
P.
Ferragina
Paolo
M.
Sanderson
Mark
978-3-540-45774-9
C1256428004B93B8-773F504BAB365AA0C12571880037A8F6-bastetal06spire
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3144252012-09-1987:931
Thesis
Sampling Rooted 3-Connected Planar Graphs in Deterministic Polynomial Time
English
Humboldt-Universität zu Berlin
Saarbrücken, Saarland
2006
2007-03-08
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.
expertsonly
http://edoc.mpg.de/get.epl?fid=35756&did=314425&ver=0
http://edoc.mpg.de/get.epl?fid=35757&did=314425&ver=0
D.
Johannsen
Daniel
C1256428004B93B8-9D944E28E89076EAC1257298005A5922-Johannsen2006a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3144272012-09-1987:931
Conference-Paper
Type Less, Find More: Fast Autocompletion Search with a Succinct Index
English
ACM
New York, USA
2006
2007-02-10
364
371
Seattle, USA
2006-08-06
SIGIR 2006: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35758&did=314427&ver=0
H.
Bast
Holger
I.
Weber
Ingmar
E.N.
Efthimiadis
Efthimis N.
S.
Dumais
Susan
D.
Hawking
David
K.
Järvellin
Kalervo
1-59593-369-7
C1256428004B93B8-8B5BAB9D35C4812FC12571880036EB8B-bastweber06sigir
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3144302012-09-1987:931
Conference-Paper
The Space Complexity of Pass-Efficient Algorithms for Clustering
English
ACM / Siam
New York, USA
2006
2007-04-16
1157
1166
Miami, USA
2007-02-21
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'06
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35760&did=314430&ver=0
K.L.
Chang
Kevin L.
R.
Kannan
Ravi
0-89871-605-5
C1256428004B93B8-42E27E9B111F2537C1257289003D2F0F-Chang2006
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
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.
oai:edoc.mpg.de:3144322012-09-1987:931
Conference-Paper
A New Approximation Algorithm for Multidimensional Rectangle Tiling
English
Springer
Berlin, Germany
2006
2007-04-25
712
721
Kolkata, India
2006-12-18
Algorithms and Computation : 17th International Symposium, ISAAC 2006
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35762&did=314432&ver=0
K.
Paluch
Katarzyna
T.
Asano
Tetsuo
978-3-540-49694-6
C1256428004B93B8-267A7891DC5BE6ADC12572A3005639C8-Paluch2006
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3144432012-09-1987:931
Conference-Paper
Unbiased Matrix Rounding
English
Springer
Berlin, Germany
2006
2007-04-11
102
112
Riga, Latvia
2006-07-06
Algorithm theory - SWAT 2006 : 10th Scandinavian Workshop on Algorithm Theory
Lecture Notes in Computer Science
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.
No
notspecified
published
http://edoc.mpg.de/get.epl?fid=35766&did=314443&ver=0
B.
Doerr
Benjamin
T.
Friedrich
Tobias
C.
Klein
Christian
R.
Osbild
Ralf
L.
Arge
Lars
R.
Freivalds
Rusins
978-3-540-35753-7
C1256428004B93B8-13A774E39EDED496C12571430049FD2C-DFKO06
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3144482012-09-1987:931
Article
Deterministic Rendezvous in Graphs
English
2006
2007-02-05
69
96
Algorithmica
46
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=35769&did=314448&ver=0
A.
Dessmark
Anders
P.
Fraigniaud
Pierre
D.
Kowalski
Dariusz
A.
Pelc
Andrzej
0178-4617
C1256428004B93B8-1CA3F3D4360A47C3C12572790065619B-DFKP2006
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3144512012-09-1987:931
Article
Algorithmic methods for investigating equilibria in epidemic modeling
English
2006
2007-02-10
1157
1173
Journal of Symbolic Computation
41
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=35770&did=314451&ver=0
C.
Brown
Christopher
M.
El Kahoui
M'hammed
D.
Novotni
Dominik
A.
Weber
Andreas
C1256428004B93B8-DF5D51E72306F1EDC1256FB30052107F-ElKahoui2005d
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3144522012-09-1987:931
Conference-Paper
Hole Detection or: "How Much Geometry Hides in Connectivity?"
English
ACM
New York, USA
2006
2007-04-16
377
385
Sedona, Arizona, USA
2006-06-05
Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35771&did=314452&ver=0
S.
Funke
Stefan
C.
Klein
Christian
N.
Amenta
Nina
O.
Cheong
Otfried
1-59593-340-9
C1256428004B93B8-501E6A40DCBD9F35C125725E004D389A-FK2006
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3144612012-09-1987:931
Article
Exact, Efficient and Complete Arrangement Computation for Cubic Curves
English
2006
2007-02-10
36
73
Computational Geometry
35
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}.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=35773&did=314461&ver=0
A.
Eigenwillig
Arno
L.
Kettner
Lutz
E.
Schömer
Elmar
N.
Wolpert
Nicola
0925-7721
C1256428004B93B8-9FBA65AC1148D2AEC1257176004AA8EE-eksw-eecaccc-06
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
Copyright © 2005 Elsevier B.V. All rights reserved.
This article has been published in Computational Geometry 35(1-2), August 2006,
Pages 36-73.
oai:edoc.mpg.de:3144652012-09-1987:931
Conference-Paper
Speeding Up Evolutionary Algorithms Through Restricted Mutation Operators
English
Springer
Berlin, Germany
2006
2007-04-26
978
987
Reykjavik, Iceland
2006-09-09
Parallel Problem Solving from Nature - PPSN IX, 9th International Conference
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35777&did=314465&ver=0
B.
Doerr
Benjamin
N.
Hebbinghaus
Nils
F.
Neumann
Frank
T.P.
Runarsson
Thomas Ph.
H.G.
Beyer
Hans G.
E.
Burke
Edmund
J.J.
Merelo-Guervós
Juan J.
L.D.
Whitley
L. Darrell
X.
Yao
Xin
978-3-540-38990-3
C1256428004B93B8-3D7F17130E081DC3C125725A005FBED0-Hebbinghaus2006
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3144922012-09-1987:931
Conference-Paper
Deterministic Random Walks on the Two-Dimensional Grid
English
Springer
Berlin, Germany
2006
2007-04-25
474
483
Kolkata, India
2006-12-18
Algorithms and Computation : 17th International Symposium, ISAAC 2006
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35789&did=314492&ver=0
B.
Doerr
Benjamin
T.
Friedrich
Tobias
T.
Asano
Tetsuo
978-3-540-49694-6
C1256428004B93B8-2E93A9601DA3F2C0C125722E004854E8-DF2006
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3145042012-09-1987:931
Conference-Paper
Unbiased Rounding of Rational Matrices
English
Springer
Berlin, Germany
2006
2007-03-17
200
211
Kolkata, India
2006-12-13
FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science: 26th International Conference
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35796&did=314504&ver=0
http://edoc.mpg.de/get.epl?fid=35795&did=314504&ver=0
B.
Doerr
Benjamin
C.
Klein
Christian
S.
Arun-Kumar
S.
N.
Garg
Naveen
978-3-540-49994-7
C1256428004B93B8-1FFC886090FF93A5C1257230004364EF-unbiasmatr2006
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3145312012-09-1987:931
Conference-Paper
A computational study of external memory BFS algorithms
English
ACM / Siam
New York, USA
2006
2007-04-16
601
610
Miami, USA
2006-01-22
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'06
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35807&did=314531&ver=0
D.
Ajwani
Deepak
R.
Dementiev
Roman
U.
Meyer
Ulrich
0-89871-605-5
C1256428004B93B8-2A7F571896C92254C125709A00333161-Ajwani06
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3145422012-09-1987:931
Conference-Paper
Almost Tight Recursion Tree Bounds for the Descartes Method
English
ACM
New York, USA
2006
2007-04-27
71
78
Genova, Italy
2006-07-09
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation
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.
The title on the printed proceedings volume is "...and Algebraic Computations",
but according to (i) grammar, (ii) previous proceedings volumes, and (iii) the
ACM Digital Library, the final "s" is wrong and should be deleted.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35811&did=314542&ver=0
A.
Eigenwillig
Arno
V.
Sharma
Vikram
C.K.
Yap
Chee K.
J.-G.
Dumas
Jean-Guillaume
1-59593-276-3
C1256428004B93B8-6E09CB7FBE62EA64C12571B20040A5D4-Eigenwillig2006a
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
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
oai:edoc.mpg.de:3145512012-09-1987:931
Thesis
A Goal-Directed Shortest Path Algorithm Using Precomputed Cluster Distances
English
Universität des Saarlandes
Saarbrücken, Saarland
2006
2007-02-01
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.
expertsonly
http://edoc.mpg.de/get.epl?fid=35816&did=314551&ver=0
http://edoc.mpg.de/get.epl?fid=35817&did=314551&ver=0
J.
Maue
Jens
C1256428004B93B8-FFC0D298CAFCE682C1257194003A9277-Maue2006
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3145532012-09-1987:931
PhD-Thesis
Combinatorial Approaches to Trunk Packing
English
Universität des Saarlandes
Saarbrücken, Saarland
2006-07-10
2007-03-01
expertsonly
http://edoc.mpg.de/get.epl?fid=35819&did=314553&ver=0
J.
Reichel
Joachim
C1256428004B93B8-BE8C52976440BC5AC12572210046683C-DissReichel06
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3145672012-09-1987:931
Thesis
Analysis of Real Algebraic Plane Curves
English
Universität des Saarlandes
Saarbrücken, Saarland
2006
2007-02-27
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.
expertsonly
http://edoc.mpg.de/get.epl?fid=35826&did=314567&ver=0
M.
Kerber
Michael
C1256428004B93B8-1BC96C578F66A025C125722E00476676-Kerber2006
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3146062012-09-1987:931
Article
Discrepancy of Symmetric Products of Hypergraphs
English
2006
2007-02-14
1
12
The Electronic Journal of Combinatorics
13
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)$.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35842&did=314606&ver=0
B.
Doerr
Benjamin
M.
Gnewuch
Michael
N.
Hebbinghaus
Nils
1077-8926
C1256428004B93B8-FA607DDFBCE27DC9C125722E005BABA9-SymHyp2006
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3146292012-09-1987:931
PhD-Thesis
Minimum Cycle Basis, Algorithms & Applications
English
Universität des Saarlandes
Saarbrücken, Saarland
2006-11-16
2006-11-24
expertsonly
http://edoc.mpg.de/get.epl?fid=35851&did=314629&ver=0
D.
Michail
Dimitrios
C1256428004B93B8-379FF01F95D006F5C1257230005263A1-Michail2006
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3146412012-09-1987:931
Conference-Paper
The Interval Liar Game
English
Springer
Berlin, Germany
2006
2007-04-25
318
327
Kolkata, India
2006-12-18
Algorithms and Computation : 17th International Symposium, ISAAC 2006
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35853&did=314641&ver=0
B.
Doerr
Benjamin
J.
Lengler
Johannes
D.
Steurer
Daniel
T.
Asano
Tetsuo
978-3-540-49694-6
C1256428004B93B8-5C3C2CF999724474C12572300043ED40-IntLiar2006
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3146512012-09-1987:931
Conference-Paper
Computing Steiner Minimal Trees in Hamming Metric
English
ACM / Siam
New York, USA
2006
2007-04-16
172
181
Miami, USA
2006-01-22
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'06
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=35859&did=314651&ver=0
E.
Althaus
Ernst
R.
Naujoks
Rouven
0-89871-605-5
C1256428004B93B8-C521C75A9A165EDBC12572810057422C-Naujoks2006
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3146692012-09-1987:931
Conference-Paper
An O(n^2.75) algorithm for online topological ordering
An O($n^2.75$) algorithm for online topological ordering
English
Springer
Berlin, Germany
2006
2007-03-07
53
64
Riga, Latvia
2006-07-06
Algorithm theory - SWAT 2006 : 10th Scandinavian Workshop on Algorithm Theory
Lecture Notes in Computer Science
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.
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=35870&did=314669&ver=0
D.
Ajwani
Deepak
T.
Friedrich
Tobias
U.
Meyer
Ulrich
L.
Arge
Lars
R.
Freivalds
Rusins
978-3-540-35753-7
C1256428004B93B8-9A704547B66D15AAC12571430049F8F6-AFM06
MPI für Informatik
Algorithms and Complexity Group
2007
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3444042012-09-1987:931
Article
A Method for Obtaining Randomized Algorithms with Small Tail Probabilities
English
1996
2008-01-18
543
547
Algorithmica
16
We study strategies for converting randomized algorithms of the Las Vegas type
into randomized algorithms with small tail probabilities.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=40520&did=344404&ver=0
H.
Alt
Helmut
L.
Guibas
L.
K.
Mehlhorn
Kurt
R.M.
Karp
Richard M.
A.
Wigderson
A.
0178-4617
C1256428004B93B8-09A84E84CF6C02CCC1256466004E8640-AltGuibasMehlhornKarp96
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3444292012-09-1987:931
Conference-Paper
From Algorithms to Working Programs: On the Use of Program Checking in LEDA
English
Springer
Berlin, Germany
1998
2006-10-04
84
93
Brno, Czech Republic
Mathematical foundations of computer science (MFCS-98) : 23rd international symposium
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=40531&did=344429&ver=0
K.
Mehlhorn
Kurt
S.
Näher
Stefan
L.
Brim
Lubos
J.
Gruska
Jozef
J.
Zlatuska
Jirí
3-540-64827-5
C1256428004B93B8-9786581BFEADC37CC12567440049D8FD-MehlhornNäher98
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3444322012-09-1987:931
Article
Average-Case Complexity of Shortest-Paths Problems in the Vertex-Potential Model
English
2000
2006-08-30
33
46
Random Structures & Algorithms
16
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=40535&did=344432&ver=0
C.
Cooper
Colin
A.M.
Frieze
Alan M.
K.
Mehlhorn
Kurt
V.
Priebe
Volker
1042-9832
C1256428004B93B8-3661E3997B3C672A4125684E0045AF9E-CooperFriezeMehlhornPriebe00
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3444342012-09-1987:931
Conference-Paper
LEDA-SM : Extending LEDA to Secondary Memory
English
Springer
Berlin, Germany
1999
2006-11-09
228
242
London, UK
1999-07-19
Algorithm engineering (WAE-99) : 3rd International Workshop, WAE'99
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=40538&did=344434&ver=0
http://edoc.mpg.de/get.epl?fid=40537&did=344434&ver=0
A.
Crauser
Andreas
K.
Mehlhorn
Kurt
J.S.
Vitter
Jeffrey S.
C.D.
Zaroliagis
Christos D.
3-540-66427-0
C1256428004B93B8-30D55511C943CF0DC1256888005051DC-Crauser1999a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3444372012-09-1987:931
Article
A correctness certificate for the Stoer-Wagner min-cut algorithm
English
1999
2008-01-04
251
254
Information Processing Letters
70
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=40542&did=344437&ver=0
http://edoc.mpg.de/get.epl?fid=40541&did=344437&ver=0
S.R.
Arikati
Srinivasa Rao
K.
Mehlhorn
Kurt
C1256428004B93B8-E77DC5FAFF8CE44EC12568AB00367ABD-Arikati-Mehlhorn
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3444412012-09-1987:931
Conference-Paper
Geometric Computing with CGAL and LEDA
English
Vanderbilt University Press
Nashville, USA
2000
2006-06-20
277
286
Saint-Malo, France
Curve and surface design, Saint-Malo 1999
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=40545&did=344441&ver=0
K.
Mehlhorn
Kurt
S.
Schirra
Stefan
P.-J.
Laurent
Pierre-Jean
P.
Sablonnière
Paul
L.L.
Schumaker
Larry L.
0-8265-1356-1
C1256428004B93B8-05A2008707A0E4E8C12568B000396C7E-Schirra1999
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3444482012-09-1987:931
Conference-Paper
LOOK - a Lazy Object-Oriented Kernel for Geometric Computation
English
ACM
New York, USA
2000
2006-06-13
156
165
Hong Kong, China
2000-06-12
Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00)
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=40551&did=344448&ver=0
S.
Funke
Stefan
K.
Mehlhorn
Kurt
1-58113-224-7
C1256428004B93B8-DF4B8280AAF46A9DC12569D700604A45-fm-lalokfgc-00
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3444512012-09-1987:931
Conference-Paper
A Polynomial-Time Fragment of Dominance Constraints
English
Morgan Kaufmann
San Francisco, USA
2000
2008-01-22
368
375
Hong-Kong
Proceedings of the 38th Annual Meeting of the Association of Computational Linguistics (ACL-00)
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.
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=40554&did=344451&ver=0
http://edoc.mpg.de/get.epl?fid=40555&did=344451&ver=0
A.
Koller
Alexander
K.
Mehlhorn
Kurt
J.
Niehren
Joachim
1-558-60729-3
C1256428004B93B8-5D11991BA7D77D47C12569DC003C0D17-Koller-et-al:dominance-constraints
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3444532012-09-1987:931
Conference-Paper
Implementation of $O(nm \log n)$ weighted matchings: The power of data structures
English
Springer
New York, USA
2000
2006-06-20
23
38
Saarbrücken, Germany
4th International Workshop on Algorithm Engineering
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=40558&did=344453&ver=0
K.
Mehlhorn
Kurt
G.
Schäfer
Guido
S.
Näher
Stefan
D.
Wagner
Dorothea
3-540-42512-8
C1256428004B93B8-A809B85C8F4F8B27C12569DC003DF0A4-Mehlhorn-Schaefer:WeightedMatchings
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3444562012-09-1987:931
Article
Traveling Salesman-Based Curve Reconstruction in Polynomial Time
English
2001
2006-11-09
27
66
SIAM Journal on Computing
31
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=40561&did=344456&ver=0
http://edoc.mpg.de/get.epl?fid=40562&did=344456&ver=0
E.
Althaus
Ernst
K.
Mehlhorn
Kurt
0097-5397
C1256428004B93B8-7C04B324978725EFC1256A8E0064302F-AltMeh2001j
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3444572012-09-1987:931
Conference-Paper
CNOP - {A} Package for Constrained Network Optimization
English
Springer
Berlin, Germany
2001
2006-11-09
17
31
Washington, DC, USA
2001-01-05
Algorithm engineering and experimentation (ALENEX-01) :Third International Workshop ALENEX 2001 ; revised papers
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=40563&did=344457&ver=0
http://edoc.mpg.de/get.epl?fid=40564&did=344457&ver=0
K.
Mehlhorn
Kurt
M.
Ziegelmann
Mark
A.L.
Buchsbaum
Adam L.
J.
Snoeyink
Jack
3-540-42560-8
C1256428004B93B8-4E7833E07426E66AC1256A940043E402-MehlhornZiegelmann2001
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3445052012-09-1987:931
Article
Introduction
English
1994
2008-03-05
295
295
Journal of Symbolic Computation
17
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=40631&did=344505&ver=0
K.
Mehlhorn
Kurt
S.
Näher
Stefan
J.
Nievergelt
Jurg
0747-7171
C1256428004B93B8-659422E04BB0418CC125705400327DEF-Mehlhorn94g
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3445562012-09-1987:931
Conference-Paper
The 'almost all' theory of subrecursive degrees is decidable
English
Springer
Berlin, Germany
1974
2007-01-09
317
325
Saarbrücken, Germany
1974-07-29
Automata, languages and programming : 2nd colloquium (ICALP-74)
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=40647&did=344556&ver=0
K.
Mehlhorn
Kurt
J.
Loeckx
Jacques
3-540-06841-4
C1256428004B93B8-C7A57ECB57F1B837C12571400043FB06-Mehlhorn74
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3445572012-09-1987:931
Article
Monotone Switching Circuits and Boolean Matrix Product
English
1976
2006-11-30
99
111
Computing
16
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=40648&did=344557&ver=0
K.
Mehlhorn
Kurt
Z.
Galil
Zvi
0010-485X (printed version)
C1256428004B93B8-21414D3E9446C0B9C125714000474E8D-Mehlhorn76j
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:3445582012-09-1987:931
Article
An Improved Lower Bound on the Formula Complexity of Context-Free Recognition
English
1976
2008-02-28
523
524
Elektronische Informationsverarbeitung und Kybernetik
12
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=40649&did=344558&ver=0
K.
Mehlhorn
Kurt
C1256428004B93B8-B7336C0700B7EF4EC1257140004E0BE1-Mehlhorn76b
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
ResultSet_4BZZ5ITX96W_range_100-199