---
_id: '2425'
abstract:
- lang: eng
text: ' We present instance-specific custom computing machines for the set covering
problem. Four accelerator architectures are developed that implement branch \&
bound in 3-valued logic and many of the deduction techniques found in software
solvers. We use set covering benchmarks from two-level logic minimization and
Steiner triple systems to derive and discuss experimental results. The resulting
raw speedups are in the order of four magnitudes on average. Finally, we propose
a hybrid solver architecture that combines the raw speed of instance-specific
reconfigurable hardware with flexible bounding schemes implemented in software. '
author:
- first_name: Christian
full_name: Plessl, Christian
id: '16153'
last_name: Plessl
orcid: 0000-0001-5728-9982
- first_name: Marco
full_name: Platzner, Marco
id: '398'
last_name: Platzner
citation:
ama: 'Plessl C, Platzner M. Custom Computing Machines for the Set Covering Problem.
In: Proc. Int. Symp. on Field-Programmable Custom Computing Machines (FCCM).
IEEE Computer Society; 2002:163-172. doi:10.1109/FPGA.2002.1106671'
apa: Plessl, C., & Platzner, M. (2002). Custom Computing Machines for the Set
Covering Problem. In Proc. Int. Symp. on Field-Programmable Custom Computing
Machines (FCCM) (pp. 163–172). IEEE Computer Society. https://doi.org/10.1109/FPGA.2002.1106671
bibtex: '@inproceedings{Plessl_Platzner_2002, title={Custom Computing Machines for
the Set Covering Problem}, DOI={10.1109/FPGA.2002.1106671},
booktitle={Proc. Int. Symp. on Field-Programmable Custom Computing Machines (FCCM)},
publisher={IEEE Computer Society}, author={Plessl, Christian and Platzner, Marco},
year={2002}, pages={163–172} }'
chicago: Plessl, Christian, and Marco Platzner. “Custom Computing Machines for the
Set Covering Problem.” In Proc. Int. Symp. on Field-Programmable Custom Computing
Machines (FCCM), 163–72. IEEE Computer Society, 2002. https://doi.org/10.1109/FPGA.2002.1106671.
ieee: C. Plessl and M. Platzner, “Custom Computing Machines for the Set Covering
Problem,” in Proc. Int. Symp. on Field-Programmable Custom Computing Machines
(FCCM), 2002, pp. 163–172.
mla: Plessl, Christian, and Marco Platzner. “Custom Computing Machines for the Set
Covering Problem.” Proc. Int. Symp. on Field-Programmable Custom Computing
Machines (FCCM), IEEE Computer Society, 2002, pp. 163–72, doi:10.1109/FPGA.2002.1106671.
short: 'C. Plessl, M. Platzner, in: Proc. Int. Symp. on Field-Programmable Custom
Computing Machines (FCCM), IEEE Computer Society, 2002, pp. 163–172.'
date_created: 2018-04-17T15:15:44Z
date_updated: 2022-01-06T06:56:13Z
department:
- _id: '518'
- _id: '78'
doi: 10.1109/FPGA.2002.1106671
page: 163-172
publication: Proc. Int. Symp. on Field-Programmable Custom Computing Machines (FCCM)
publisher: IEEE Computer Society
status: public
title: Custom Computing Machines for the Set Covering Problem
type: conference
user_id: '24135'
year: '2002'
...
---
_id: '24336'
abstract:
- lang: eng
text: "We define here a distributed abstract state machine (DASM) [7] of
\r\nthe network or routing layer of mobile ad hoc networks [13]. Such networks
re-\r\nquire routing strategies substantially different from those used in static
commu-\r\nnication networks, since storing and updating large routing tables
\ at mobile \r\nhosts would congest the network with administration packets
\ very fast. In [1], \r\nthe hypercubic location service is presented,
\ which considers a very strong \r\ndefinition of fault-tolerance thereby
\ improving state-of-the-art ad hoc routing \r\nprotocols in several respects.
Our goal in modeling the protocols for the distrib-\r\nuted location service and
the position based routing is twofold. First, we support \r\nthe definition and
\ validation of wireless communication protocols and imple-\r\nmentations
based thereon. Second, we feel that the abstract computation model \r\nnaturally
reflects the layering principle of communication architectures in com-\r\nbination
with an uncompromisingly local view of the application domain. Thus \r\nwe can
identify fundamental semantic concepts, such as concurrency, reactivity \r\nand
\ asynchronism, directly with the related concepts as imposed by the
\ given \r\napplication context. "
author:
- first_name: András
full_name: ' Benczúr, András'
last_name: ' Benczúr'
- first_name: Uwe
full_name: Glässer, Uwe
last_name: Glässer
- first_name: Tamás
full_name: Lukovszki, Tamás
last_name: Lukovszki
citation:
ama: Benczúr A, Glässer U, Lukovszki T. Formal Description of a Distributed Location
Service for Mobile Ad Hoc Networks. Proc of 10th International Workshop on
Abstract State Machines, LNCS. Published online 2002.
apa: Benczúr, A., Glässer, U., & Lukovszki, T. (2002). Formal Description of
a Distributed Location Service for Mobile Ad Hoc Networks. Proc. of 10th International
Workshop on Abstract State Machines, LNCS.
bibtex: '@article{ Benczúr_Glässer_Lukovszki_2002, title={Formal Description of
a Distributed Location Service for Mobile Ad Hoc Networks}, journal={Proc. of
10th International Workshop on Abstract State Machines, LNCS}, author={ Benczúr,
András and Glässer, Uwe and Lukovszki, Tamás}, year={2002} }'
chicago: Benczúr, András, Uwe Glässer, and Tamás Lukovszki. “Formal Description
of a Distributed Location Service for Mobile Ad Hoc Networks.” Proc. of 10th
International Workshop on Abstract State Machines, LNCS, 2002.
ieee: A. Benczúr, U. Glässer, and T. Lukovszki, “Formal Description of a Distributed
Location Service for Mobile Ad Hoc Networks,” Proc. of 10th International Workshop
on Abstract State Machines, LNCS, 2002.
mla: Benczúr, András, et al. “Formal Description of a Distributed Location Service
for Mobile Ad Hoc Networks.” Proc. of 10th International Workshop on Abstract
State Machines, LNCS, 2002.
short: A. Benczúr, U. Glässer, T. Lukovszki, Proc. of 10th International Workshop
on Abstract State Machines, LNCS (2002).
date_created: 2021-09-14T08:51:39Z
date_updated: 2022-01-06T06:56:18Z
ddc:
- '000'
department:
- _id: '63'
file:
- access_level: closed
content_type: application/pdf
creator: koala
date_created: 2021-09-14T09:09:28Z
date_updated: 2021-09-14T09:09:28Z
file_id: '24337'
file_name: asm03.pdf
file_size: 162215
relation: main_file
success: 1
file_date_updated: 2021-09-14T09:09:28Z
has_accepted_license: '1'
language:
- iso: eng
publication: Proc. of 10th International Workshop on Abstract State Machines, LNCS
publication_status: published
status: public
title: Formal Description of a Distributed Location Service for Mobile Ad Hoc Networks
type: journal_article
user_id: '15415'
year: '2002'
...
---
_id: '24338'
author:
- first_name: Matthias
full_name: Grünewald, Matthias
last_name: Grünewald
- first_name: Tamás
full_name: Lukovszki, Tamás
last_name: Lukovszki
- first_name: Christian
full_name: Schindelhauer, Christian
last_name: Schindelhauer
- first_name: Klaus
full_name: Volbert, Klaus
last_name: Volbert
citation:
ama: 'Grünewald M, Lukovszki T, Schindelhauer C, Volbert K. Distributed Maintenance
of Resource Efficient Wireless Network Topologies. In: Proceedings of the 8th
International Euro-Par Conference. ; 2002. doi:10.1007/3-540-45706-2_134'
apa: Grünewald, M., Lukovszki, T., Schindelhauer, C., & Volbert, K. (2002).
Distributed Maintenance of Resource Efficient Wireless Network Topologies. Proceedings
of the 8th International Euro-Par Conference. https://doi.org/10.1007/3-540-45706-2_134
bibtex: '@inproceedings{Grünewald_Lukovszki_Schindelhauer_Volbert_2002, place={Paderborn,
Germany}, title={Distributed Maintenance of Resource Efficient Wireless Network
Topologies}, DOI={10.1007/3-540-45706-2_134},
booktitle={Proceedings of the 8th International Euro-Par Conference}, author={Grünewald,
Matthias and Lukovszki, Tamás and Schindelhauer, Christian and Volbert, Klaus},
year={2002} }'
chicago: Grünewald, Matthias, Tamás Lukovszki, Christian Schindelhauer, and Klaus
Volbert. “Distributed Maintenance of Resource Efficient Wireless Network Topologies.”
In Proceedings of the 8th International Euro-Par Conference. Paderborn,
Germany, 2002. https://doi.org/10.1007/3-540-45706-2_134.
ieee: 'M. Grünewald, T. Lukovszki, C. Schindelhauer, and K. Volbert, “Distributed
Maintenance of Resource Efficient Wireless Network Topologies,” 2002, doi: 10.1007/3-540-45706-2_134.'
mla: Grünewald, Matthias, et al. “Distributed Maintenance of Resource Efficient
Wireless Network Topologies.” Proceedings of the 8th International Euro-Par
Conference, 2002, doi:10.1007/3-540-45706-2_134.
short: 'M. Grünewald, T. Lukovszki, C. Schindelhauer, K. Volbert, in: Proceedings
of the 8th International Euro-Par Conference, Paderborn, Germany, 2002.'
date_created: 2021-09-14T09:15:57Z
date_updated: 2022-01-06T06:56:18Z
department:
- _id: '63'
doi: 10.1007/3-540-45706-2_134
language:
- iso: eng
place: Paderborn, Germany
publication: Proceedings of the 8th International Euro-Par Conference
publication_identifier:
issn:
- 0302-9743
publication_status: published
status: public
title: Distributed Maintenance of Resource Efficient Wireless Network Topologies
type: conference
user_id: '15415'
year: '2002'
...
---
_id: '26412'
author:
- first_name: Klaus
full_name: Volbert, Klaus
last_name: Volbert
citation:
ama: 'Volbert K. A simulation environment for ad hoc networks using sector subdivision.
In: Proceedings 10th Euromicro Workshop on Parallel, Distributed and Network-Based
Processing. ; 2002. doi:10.1109/empdp.2002.994324'
apa: Volbert, K. (2002). A simulation environment for ad hoc networks using sector
subdivision. Proceedings 10th Euromicro Workshop on Parallel, Distributed and
Network-Based Processing. https://doi.org/10.1109/empdp.2002.994324
bibtex: '@inproceedings{Volbert_2002, title={A simulation environment for ad hoc
networks using sector subdivision}, DOI={10.1109/empdp.2002.994324},
booktitle={Proceedings 10th Euromicro Workshop on Parallel, Distributed and Network-based
Processing}, author={Volbert, Klaus}, year={2002} }'
chicago: Volbert, Klaus. “A Simulation Environment for Ad Hoc Networks Using Sector
Subdivision.” In Proceedings 10th Euromicro Workshop on Parallel, Distributed
and Network-Based Processing, 2002. https://doi.org/10.1109/empdp.2002.994324.
ieee: 'K. Volbert, “A simulation environment for ad hoc networks using sector subdivision,”
2002, doi: 10.1109/empdp.2002.994324.'
mla: Volbert, Klaus. “A Simulation Environment for Ad Hoc Networks Using Sector
Subdivision.” Proceedings 10th Euromicro Workshop on Parallel, Distributed
and Network-Based Processing, 2002, doi:10.1109/empdp.2002.994324.
short: 'K. Volbert, in: Proceedings 10th Euromicro Workshop on Parallel, Distributed
and Network-Based Processing, 2002.'
date_created: 2021-10-18T15:45:20Z
date_updated: 2022-01-06T06:57:20Z
department:
- _id: '63'
- _id: '26'
doi: 10.1109/empdp.2002.994324
language:
- iso: eng
publication: Proceedings 10th Euromicro Workshop on Parallel, Distributed and Network-based
Processing
publication_status: published
status: public
title: A simulation environment for ad hoc networks using sector subdivision
type: conference
user_id: '15415'
year: '2002'
...
---
_id: '3241'
author:
- first_name: Heike
full_name: Wehrheim, Heike
id: '573'
last_name: Wehrheim
citation:
ama: Wehrheim H. Relating State-based and Behaviour-oriented Subtyping. Nord
J Comput. 2002;(4):405--435.
apa: Wehrheim, H. (2002). Relating State-based and Behaviour-oriented Subtyping.
Nord. J. Comput., (4), 405--435.
bibtex: '@article{Wehrheim_2002, title={Relating State-based and Behaviour-oriented
Subtyping}, number={4}, journal={Nord. J. Comput.}, author={Wehrheim, Heike},
year={2002}, pages={405--435} }'
chicago: 'Wehrheim, Heike. “Relating State-Based and Behaviour-Oriented Subtyping.”
Nord. J. Comput., no. 4 (2002): 405--435.'
ieee: H. Wehrheim, “Relating State-based and Behaviour-oriented Subtyping,” Nord.
J. Comput., no. 4, pp. 405--435, 2002.
mla: Wehrheim, Heike. “Relating State-Based and Behaviour-Oriented Subtyping.” Nord.
J. Comput., no. 4, 2002, pp. 405--435.
short: H. Wehrheim, Nord. J. Comput. (2002) 405--435.
date_created: 2018-06-14T06:56:20Z
date_updated: 2022-01-06T06:59:07Z
department:
- _id: '77'
issue: '4'
page: 405--435
publication: Nord. J. Comput.
status: public
title: Relating State-based and Behaviour-oriented Subtyping
type: journal_article
user_id: '29719'
year: '2002'
...
---
_id: '3242'
author:
- first_name: Ernst-Rüdiger
full_name: Olderog, Ernst-Rüdiger
last_name: Olderog
- first_name: Heike
full_name: Wehrheim, Heike
id: '573'
last_name: Wehrheim
citation:
ama: 'Olderog E-R, Wehrheim H. Specification and Inheritance in {CSP-OZ}. In: S.
de Boer F, M. Bonsangue M, Graf S, P. de Roever W, eds. Formal Methods for
Components and Objects, First International Symposium, {FMCO} 2002, Leiden, The
Netherlands, November 5-8, 2002, Revised Lectures. Lecture Notes in Computer
Science. ; 2002:361--379. doi:10.1007/978-3-540-39656-7_15'
apa: Olderog, E.-R., & Wehrheim, H. (2002). Specification and Inheritance in
{CSP-OZ}. In F. S. de Boer, M. M. Bonsangue, S. Graf, & W. P. de Roever (Eds.),
Formal Methods for Components and Objects, First International Symposium, {FMCO}
2002, Leiden, The Netherlands, November 5-8, 2002, Revised Lectures (pp. 361--379).
https://doi.org/10.1007/978-3-540-39656-7_15
bibtex: '@inproceedings{Olderog_Wehrheim_2002, series={Lecture Notes in Computer
Science}, title={Specification and Inheritance in {CSP-OZ}}, DOI={10.1007/978-3-540-39656-7_15},
booktitle={Formal Methods for Components and Objects, First International Symposium,
{FMCO} 2002, Leiden, The Netherlands, November 5-8, 2002, Revised Lectures}, author={Olderog,
Ernst-Rüdiger and Wehrheim, Heike}, editor={S. de Boer, Frank and M. Bonsangue,
Marcello and Graf, Susanne and P. de Roever, WillemEditors}, year={2002}, pages={361--379},
collection={Lecture Notes in Computer Science} }'
chicago: Olderog, Ernst-Rüdiger, and Heike Wehrheim. “Specification and Inheritance
in {CSP-OZ}.” In Formal Methods for Components and Objects, First International
Symposium, {FMCO} 2002, Leiden, The Netherlands, November 5-8, 2002, Revised Lectures,
edited by Frank S. de Boer, Marcello M. Bonsangue, Susanne Graf, and Willem P.
de Roever, 361--379. Lecture Notes in Computer Science, 2002. https://doi.org/10.1007/978-3-540-39656-7_15.
ieee: E.-R. Olderog and H. Wehrheim, “Specification and Inheritance in {CSP-OZ},”
in Formal Methods for Components and Objects, First International Symposium,
{FMCO} 2002, Leiden, The Netherlands, November 5-8, 2002, Revised Lectures,
2002, pp. 361--379.
mla: Olderog, Ernst-Rüdiger, and Heike Wehrheim. “Specification and Inheritance
in {CSP-OZ}.” Formal Methods for Components and Objects, First International
Symposium, {FMCO} 2002, Leiden, The Netherlands, November 5-8, 2002, Revised Lectures,
edited by Frank S. de Boer et al., 2002, pp. 361--379, doi:10.1007/978-3-540-39656-7_15.
short: 'E.-R. Olderog, H. Wehrheim, in: F. S. de Boer, M. M. Bonsangue, S. Graf,
W. P. de Roever (Eds.), Formal Methods for Components and Objects, First International
Symposium, {FMCO} 2002, Leiden, The Netherlands, November 5-8, 2002, Revised Lectures,
2002, pp. 361--379.'
date_created: 2018-06-14T07:10:28Z
date_updated: 2022-01-06T06:59:07Z
department:
- _id: '77'
doi: 10.1007/978-3-540-39656-7_15
editor:
- first_name: Frank
full_name: S. de Boer, Frank
last_name: S. de Boer
- first_name: Marcello
full_name: M. Bonsangue, Marcello
last_name: M. Bonsangue
- first_name: Susanne
full_name: Graf, Susanne
last_name: Graf
- first_name: Willem
full_name: P. de Roever, Willem
last_name: P. de Roever
page: 361--379
publication: Formal Methods for Components and Objects, First International Symposium,
{FMCO} 2002, Leiden, The Netherlands, November 5-8, 2002, Revised Lectures
series_title: Lecture Notes in Computer Science
status: public
title: Specification and Inheritance in {CSP-OZ}
type: conference
user_id: '29719'
year: '2002'
...
---
_id: '3243'
author:
- first_name: Heike
full_name: Wehrheim, Heike
id: '573'
last_name: Wehrheim
citation:
ama: 'Wehrheim H. Checking Behavioural Subtypes via Refinement. In: Jacobs B, Rensink
A, eds. Formal Methods for Open Object-Based Distributed Systems V, {IFIP}
{TC6/WG6.1} Fifth International Conference on Formal Methods for Open Object-Based
Distributed Systems {(FMOODS} 2002), March 20-22, 2002, Enschede, The Netherlands.
{IFIP} Conference Proceedings. ; 2002:79--93.'
apa: Wehrheim, H. (2002). Checking Behavioural Subtypes via Refinement. In B. Jacobs
& A. Rensink (Eds.), Formal Methods for Open Object-Based Distributed Systems
V, {IFIP} {TC6/WG6.1} Fifth International Conference on Formal Methods for Open
Object-Based Distributed Systems {(FMOODS} 2002), March 20-22, 2002, Enschede,
The Netherlands (pp. 79--93).
bibtex: '@inproceedings{Wehrheim_2002, series={{IFIP} Conference Proceedings}, title={Checking
Behavioural Subtypes via Refinement}, booktitle={Formal Methods for Open Object-Based
Distributed Systems V, {IFIP} {TC6/WG6.1} Fifth International Conference on Formal
Methods for Open Object-Based Distributed Systems {(FMOODS} 2002), March 20-22,
2002, Enschede, The Netherlands}, author={Wehrheim, Heike}, editor={Jacobs, Bart
and Rensink, ArendEditors}, year={2002}, pages={79--93}, collection={{IFIP} Conference
Proceedings} }'
chicago: Wehrheim, Heike. “Checking Behavioural Subtypes via Refinement.” In Formal
Methods for Open Object-Based Distributed Systems V, {IFIP} {TC6/WG6.1} Fifth
International Conference on Formal Methods for Open Object-Based Distributed Systems
{(FMOODS} 2002), March 20-22, 2002, Enschede, The Netherlands, edited by Bart
Jacobs and Arend Rensink, 79--93. {IFIP} Conference Proceedings, 2002.
ieee: H. Wehrheim, “Checking Behavioural Subtypes via Refinement,” in Formal
Methods for Open Object-Based Distributed Systems V, {IFIP} {TC6/WG6.1} Fifth
International Conference on Formal Methods for Open Object-Based Distributed Systems
{(FMOODS} 2002), March 20-22, 2002, Enschede, The Netherlands, 2002, pp. 79--93.
mla: Wehrheim, Heike. “Checking Behavioural Subtypes via Refinement.” Formal
Methods for Open Object-Based Distributed Systems V, {IFIP} {TC6/WG6.1} Fifth
International Conference on Formal Methods for Open Object-Based Distributed Systems
{(FMOODS} 2002), March 20-22, 2002, Enschede, The Netherlands, edited by Bart
Jacobs and Arend Rensink, 2002, pp. 79--93.
short: 'H. Wehrheim, in: B. Jacobs, A. Rensink (Eds.), Formal Methods for Open Object-Based
Distributed Systems V, {IFIP} {TC6/WG6.1} Fifth International Conference on Formal
Methods for Open Object-Based Distributed Systems {(FMOODS} 2002), March 20-22,
2002, Enschede, The Netherlands, 2002, pp. 79--93.'
date_created: 2018-06-14T07:11:33Z
date_updated: 2022-01-06T06:59:07Z
department:
- _id: '77'
editor:
- first_name: Bart
full_name: Jacobs, Bart
last_name: Jacobs
- first_name: Arend
full_name: Rensink, Arend
last_name: Rensink
page: 79--93
publication: Formal Methods for Open Object-Based Distributed Systems V, {IFIP} {TC6/WG6.1}
Fifth International Conference on Formal Methods for Open Object-Based Distributed
Systems {(FMOODS} 2002), March 20-22, 2002, Enschede, The Netherlands
series_title: '{IFIP} Conference Proceedings'
status: public
title: Checking Behavioural Subtypes via Refinement
type: conference
user_id: '29719'
year: '2002'
...
---
_id: '3034'
author:
- first_name: Andres
full_name: Albanese, Andres
last_name: Albanese
- first_name: Johannes
full_name: Blömer, Johannes
id: '23'
last_name: Blömer
- first_name: Jeff
full_name: Edmonds, Jeff
last_name: Edmonds
- first_name: Michael
full_name: Luby, Michael
last_name: Luby
- first_name: Madhu
full_name: Sudan, Madhu
last_name: Sudan
citation:
ama: Albanese A, Blömer J, Edmonds J, Luby M, Sudan M. Priority encoding transmission.
IEEE Transactions on Information Theory. 2002;42(6):1737-1744. doi:10.1109/18.556670
apa: Albanese, A., Blömer, J., Edmonds, J., Luby, M., & Sudan, M. (2002). Priority
encoding transmission. IEEE Transactions on Information Theory, 42(6),
1737–1744. https://doi.org/10.1109/18.556670
bibtex: '@article{Albanese_Blömer_Edmonds_Luby_Sudan_2002, title={Priority encoding
transmission}, volume={42}, DOI={10.1109/18.556670},
number={6}, journal={IEEE Transactions on Information Theory}, publisher={Institute
of Electrical and Electronics Engineers (IEEE)}, author={Albanese, Andres and
Blömer, Johannes and Edmonds, Jeff and Luby, Michael and Sudan, Madhu}, year={2002},
pages={1737–1744} }'
chicago: 'Albanese, Andres, Johannes Blömer, Jeff Edmonds, Michael Luby, and Madhu
Sudan. “Priority Encoding Transmission.” IEEE Transactions on Information Theory
42, no. 6 (2002): 1737–44. https://doi.org/10.1109/18.556670.'
ieee: A. Albanese, J. Blömer, J. Edmonds, M. Luby, and M. Sudan, “Priority encoding
transmission,” IEEE Transactions on Information Theory, vol. 42, no. 6,
pp. 1737–1744, 2002.
mla: Albanese, Andres, et al. “Priority Encoding Transmission.” IEEE Transactions
on Information Theory, vol. 42, no. 6, Institute of Electrical and Electronics
Engineers (IEEE), 2002, pp. 1737–44, doi:10.1109/18.556670.
short: A. Albanese, J. Blömer, J. Edmonds, M. Luby, M. Sudan, IEEE Transactions
on Information Theory 42 (2002) 1737–1744.
date_created: 2018-06-05T08:36:14Z
date_updated: 2022-01-06T06:58:53Z
ddc:
- '000'
department:
- _id: '64'
doi: 10.1109/18.556670
extern: '1'
file:
- access_level: closed
content_type: application/pdf
creator: feidens
date_created: 2018-06-05T08:37:48Z
date_updated: 2018-06-05T08:37:48Z
file_id: '3035'
file_name: pet.pdf
file_size: 260143
relation: main_file
success: 1
file_date_updated: 2018-06-05T08:37:48Z
has_accepted_license: '1'
intvolume: ' 42'
issue: '6'
page: 1737-1744
publication: IEEE Transactions on Information Theory
publication_identifier:
issn:
- 0018-9448
publication_status: published
publisher: Institute of Electrical and Electronics Engineers (IEEE)
status: public
title: Priority encoding transmission
type: journal_article
user_id: '25078'
volume: 42
year: '2002'
...
---
_id: '3040'
author:
- first_name: A.
full_name: Albanese, A.
last_name: Albanese
- first_name: Johannes
full_name: Blömer, Johannes
id: '23'
last_name: Blömer
- first_name: J.
full_name: Edmonds, J.
last_name: Edmonds
- first_name: M.
full_name: Luby, M.
last_name: Luby
- first_name: M.
full_name: Sudan, M.
last_name: Sudan
citation:
ama: 'Albanese A, Blömer J, Edmonds J, Luby M, Sudan M. Priority encoding transmission.
In: Proceedings 35th Annual Symposium on Foundations of Computer Science.
IEEE Comput. Soc. Press; 2002. doi:10.1109/sfcs.1994.365731'
apa: Albanese, A., Blömer, J., Edmonds, J., Luby, M., & Sudan, M. (2002). Priority
encoding transmission. In Proceedings 35th Annual Symposium on Foundations
of Computer Science. IEEE Comput. Soc. Press. https://doi.org/10.1109/sfcs.1994.365731
bibtex: '@inproceedings{Albanese_Blömer_Edmonds_Luby_Sudan_2002, title={Priority
encoding transmission}, DOI={10.1109/sfcs.1994.365731},
booktitle={Proceedings 35th Annual Symposium on Foundations of Computer Science},
publisher={IEEE Comput. Soc. Press}, author={Albanese, A. and Blömer, Johannes
and Edmonds, J. and Luby, M. and Sudan, M.}, year={2002} }'
chicago: Albanese, A., Johannes Blömer, J. Edmonds, M. Luby, and M. Sudan. “Priority
Encoding Transmission.” In Proceedings 35th Annual Symposium on Foundations
of Computer Science. IEEE Comput. Soc. Press, 2002. https://doi.org/10.1109/sfcs.1994.365731.
ieee: A. Albanese, J. Blömer, J. Edmonds, M. Luby, and M. Sudan, “Priority encoding
transmission,” in Proceedings 35th Annual Symposium on Foundations of Computer
Science, 2002.
mla: Albanese, A., et al. “Priority Encoding Transmission.” Proceedings 35th
Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press,
2002, doi:10.1109/sfcs.1994.365731.
short: 'A. Albanese, J. Blömer, J. Edmonds, M. Luby, M. Sudan, in: Proceedings 35th
Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press,
2002.'
date_created: 2018-06-05T08:43:13Z
date_updated: 2022-01-06T06:58:53Z
department:
- _id: '64'
doi: 10.1109/sfcs.1994.365731
extern: '1'
publication: Proceedings 35th Annual Symposium on Foundations of Computer Science
publication_identifier:
isbn:
- '0818665807'
publication_status: published
publisher: IEEE Comput. Soc. Press
status: public
title: Priority encoding transmission
type: conference
user_id: '25078'
year: '2002'
...
---
_id: '2134'
author:
- first_name: Uriel
full_name: Feige, Uriel
last_name: Feige
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: Feige U, Scheideler C. Improved Bounds for Acyclic Job Shop Scheduling. Combinatorica.
2002;(3):361--399. doi:10.1007/s004930200018
apa: Feige, U., & Scheideler, C. (2002). Improved Bounds for Acyclic Job Shop
Scheduling. Combinatorica, (3), 361--399. https://doi.org/10.1007/s004930200018
bibtex: '@article{Feige_Scheideler_2002, title={Improved Bounds for Acyclic Job
Shop Scheduling}, DOI={10.1007/s004930200018},
number={3}, journal={Combinatorica}, author={Feige, Uriel and Scheideler, Christian},
year={2002}, pages={361--399} }'
chicago: 'Feige, Uriel, and Christian Scheideler. “Improved Bounds for Acyclic Job
Shop Scheduling.” Combinatorica, no. 3 (2002): 361--399. https://doi.org/10.1007/s004930200018.'
ieee: U. Feige and C. Scheideler, “Improved Bounds for Acyclic Job Shop Scheduling,”
Combinatorica, no. 3, pp. 361--399, 2002.
mla: Feige, Uriel, and Christian Scheideler. “Improved Bounds for Acyclic Job Shop
Scheduling.” Combinatorica, no. 3, 2002, pp. 361--399, doi:10.1007/s004930200018.
short: U. Feige, C. Scheideler, Combinatorica (2002) 361--399.
date_created: 2018-04-03T05:43:36Z
date_updated: 2022-01-06T06:54:55Z
department:
- _id: '79'
doi: 10.1007/s004930200018
issue: '3'
page: 361--399
publication: Combinatorica
status: public
title: Improved Bounds for Acyclic Job Shop Scheduling
type: journal_article
user_id: '15504'
year: '2002'
...
---
_id: '2135'
author:
- first_name: Petr
full_name: Kolman, Petr
last_name: Kolman
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Kolman P, Scheideler C. Improved bounds for the unsplittable flow problem.
In: SODA. ACM/SIAM; 2002:184--193.'
apa: Kolman, P., & Scheideler, C. (2002). Improved bounds for the unsplittable
flow problem. In SODA (pp. 184--193). ACM/SIAM.
bibtex: '@inproceedings{Kolman_Scheideler_2002, title={Improved bounds for the unsplittable
flow problem}, booktitle={SODA}, publisher={ACM/SIAM}, author={Kolman, Petr and
Scheideler, Christian}, year={2002}, pages={184--193} }'
chicago: Kolman, Petr, and Christian Scheideler. “Improved Bounds for the Unsplittable
Flow Problem.” In SODA, 184--193. ACM/SIAM, 2002.
ieee: P. Kolman and C. Scheideler, “Improved bounds for the unsplittable flow problem,”
in SODA, 2002, pp. 184--193.
mla: Kolman, Petr, and Christian Scheideler. “Improved Bounds for the Unsplittable
Flow Problem.” SODA, ACM/SIAM, 2002, pp. 184--193.
short: 'P. Kolman, C. Scheideler, in: SODA, ACM/SIAM, 2002, pp. 184--193.'
date_created: 2018-04-03T05:44:11Z
date_updated: 2022-01-06T06:54:55Z
ddc:
- '040'
department:
- _id: '79'
file:
- access_level: open_access
content_type: application/pdf
creator: florida
date_created: 2018-04-12T08:59:58Z
date_updated: 2018-04-12T08:59:58Z
file_id: '2303'
file_name: SODA-02.pdf
file_size: 246604
relation: main_file
file_date_updated: 2018-04-12T08:59:58Z
has_accepted_license: '1'
oa: '1'
page: 184--193
publication: SODA
publisher: ACM/SIAM
status: public
title: Improved bounds for the unsplittable flow problem
type: conference
urn: '21357'
user_id: '15504'
year: '2002'
...
---
_id: '2136'
author:
- first_name: André
full_name: Brinkmann, André
last_name: Brinkmann
- first_name: Kay
full_name: Salzwedel, Kay
last_name: Salzwedel
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Brinkmann A, Salzwedel K, Scheideler C. Compact, adaptive placement schemes
for non-uniform requirements. In: SPAA. ; 2002:53--62.'
apa: Brinkmann, A., Salzwedel, K., & Scheideler, C. (2002). Compact, adaptive
placement schemes for non-uniform requirements. In SPAA (pp. 53--62).
bibtex: '@inproceedings{Brinkmann_Salzwedel_Scheideler_2002, title={Compact, adaptive
placement schemes for non-uniform requirements}, booktitle={SPAA}, author={Brinkmann,
André and Salzwedel, Kay and Scheideler, Christian}, year={2002}, pages={53--62}
}'
chicago: Brinkmann, André, Kay Salzwedel, and Christian Scheideler. “Compact, Adaptive
Placement Schemes for Non-Uniform Requirements.” In SPAA, 53--62, 2002.
ieee: A. Brinkmann, K. Salzwedel, and C. Scheideler, “Compact, adaptive placement
schemes for non-uniform requirements,” in SPAA, 2002, pp. 53--62.
mla: Brinkmann, André, et al. “Compact, Adaptive Placement Schemes for Non-Uniform
Requirements.” SPAA, 2002, pp. 53--62.
short: 'A. Brinkmann, K. Salzwedel, C. Scheideler, in: SPAA, 2002, pp. 53--62.'
date_created: 2018-04-03T05:44:56Z
date_updated: 2022-01-06T06:54:56Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
file:
- access_level: open_access
content_type: application/pdf
creator: florida
date_created: 2018-04-12T09:02:22Z
date_updated: 2018-04-12T09:02:22Z
file_id: '2305'
file_name: BSS-SPAA-02.pdf
file_size: 123373
relation: main_file
file_date_updated: 2018-04-12T09:02:22Z
has_accepted_license: '1'
language:
- iso: eng
oa: '1'
page: 53--62
publication: SPAA
status: public
title: Compact, adaptive placement schemes for non-uniform requirements
type: conference
urn: '21366'
user_id: '14955'
year: '2002'
...
---
_id: '2137'
author:
- first_name: Amitabha
full_name: Bagchi, Amitabha
last_name: Bagchi
- first_name: Amitabh
full_name: Chaudhary, Amitabh
last_name: Chaudhary
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Petr
full_name: Kolman, Petr
last_name: Kolman
citation:
ama: 'Bagchi A, Chaudhary A, Scheideler C, Kolman P. Algorithms for fault-tolerant
routing in circuit switched networks. In: SPAA. ; 2002:265--274.'
apa: Bagchi, A., Chaudhary, A., Scheideler, C., & Kolman, P. (2002). Algorithms
for fault-tolerant routing in circuit switched networks. In SPAA (pp. 265--274).
bibtex: '@inproceedings{Bagchi_Chaudhary_Scheideler_Kolman_2002, title={Algorithms
for fault-tolerant routing in circuit switched networks}, booktitle={SPAA}, author={Bagchi,
Amitabha and Chaudhary, Amitabh and Scheideler, Christian and Kolman, Petr}, year={2002},
pages={265--274} }'
chicago: Bagchi, Amitabha, Amitabh Chaudhary, Christian Scheideler, and Petr Kolman.
“Algorithms for Fault-Tolerant Routing in Circuit Switched Networks.” In SPAA,
265--274, 2002.
ieee: A. Bagchi, A. Chaudhary, C. Scheideler, and P. Kolman, “Algorithms for fault-tolerant
routing in circuit switched networks,” in SPAA, 2002, pp. 265--274.
mla: Bagchi, Amitabha, et al. “Algorithms for Fault-Tolerant Routing in Circuit
Switched Networks.” SPAA, 2002, pp. 265--274.
short: 'A. Bagchi, A. Chaudhary, C. Scheideler, P. Kolman, in: SPAA, 2002, pp. 265--274.'
date_created: 2018-04-03T05:45:44Z
date_updated: 2022-01-06T06:54:57Z
ddc:
- '040'
department:
- _id: '79'
file:
- access_level: open_access
content_type: application/pdf
creator: florida
date_created: 2018-04-12T09:03:44Z
date_updated: 2018-04-12T09:03:44Z
file_id: '2306'
file_name: BCKS-SPAA-02.pdf
file_size: 187124
relation: main_file
file_date_updated: 2018-04-12T09:03:44Z
has_accepted_license: '1'
oa: '1'
page: 265--274
publication: SPAA
status: public
title: Algorithms for fault-tolerant routing in circuit switched networks
type: conference
urn: '21376'
user_id: '15504'
year: '2002'
...
---
_id: '2138'
author:
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Scheideler C. Models and Techniques for Communication in Dynamic Networks.
In: STACS. Vol 2285. Lecture Notes in Computer Science. Springer; 2002:27--49.'
apa: Scheideler, C. (2002). Models and Techniques for Communication in Dynamic Networks.
In STACS (Vol. 2285, pp. 27--49). Springer.
bibtex: '@inproceedings{Scheideler_2002, series={Lecture Notes in Computer Science},
title={Models and Techniques for Communication in Dynamic Networks}, volume={2285},
booktitle={STACS}, publisher={Springer}, author={Scheideler, Christian}, year={2002},
pages={27--49}, collection={Lecture Notes in Computer Science} }'
chicago: Scheideler, Christian. “Models and Techniques for Communication in Dynamic
Networks.” In STACS, 2285:27--49. Lecture Notes in Computer Science. Springer,
2002.
ieee: C. Scheideler, “Models and Techniques for Communication in Dynamic Networks,”
in STACS, 2002, vol. 2285, pp. 27--49.
mla: Scheideler, Christian. “Models and Techniques for Communication in Dynamic
Networks.” STACS, vol. 2285, Springer, 2002, pp. 27--49.
short: 'C. Scheideler, in: STACS, Springer, 2002, pp. 27--49.'
date_created: 2018-04-03T05:46:38Z
date_updated: 2022-01-06T06:54:57Z
ddc:
- '040'
department:
- _id: '79'
file:
- access_level: open_access
content_type: application/pdf
creator: florida
date_created: 2018-04-12T09:01:03Z
date_updated: 2018-04-12T09:01:03Z
file_id: '2304'
file_name: STACS-02.pdf
file_size: 273875
relation: main_file
file_date_updated: 2018-04-12T09:01:03Z
has_accepted_license: '1'
intvolume: ' 2285'
oa: '1'
page: 27--49
publication: STACS
publisher: Springer
series_title: Lecture Notes in Computer Science
status: public
title: Models and Techniques for Communication in Dynamic Networks
type: conference
urn: '21386'
user_id: '15504'
volume: 2285
year: '2002'
...
---
_id: '18853'
author:
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
citation:
ama: Sohler C, Czumaj A. Abstract Combinatorial Programs and Efficient Property
Testers. Proceedings of the 43th Symposium on Foundations of Computer Science
(FOCS). 2002:83-92.
apa: Sohler, C., & Czumaj, A. (2002). Abstract Combinatorial Programs and Efficient
Property Testers. Proceedings of the 43th Symposium on Foundations of Computer
Science (FOCS), 83–92.
bibtex: '@article{Sohler_Czumaj_2002, title={Abstract Combinatorial Programs and
Efficient Property Testers}, journal={Proceedings of the 43th Symposium on Foundations
of Computer Science (FOCS)}, author={Sohler, Christian and Czumaj, Artur}, year={2002},
pages={83–92} }'
chicago: Sohler, Christian, and Artur Czumaj. “Abstract Combinatorial Programs and
Efficient Property Testers.” Proceedings of the 43th Symposium on Foundations
of Computer Science (FOCS), 2002, 83–92.
ieee: C. Sohler and A. Czumaj, “Abstract Combinatorial Programs and Efficient Property
Testers,” Proceedings of the 43th Symposium on Foundations of Computer Science
(FOCS), pp. 83–92, 2002.
mla: Sohler, Christian, and Artur Czumaj. “Abstract Combinatorial Programs and Efficient
Property Testers.” Proceedings of the 43th Symposium on Foundations of Computer
Science (FOCS), 2002, pp. 83–92.
short: C. Sohler, A. Czumaj, Proceedings of the 43th Symposium on Foundations of
Computer Science (FOCS) (2002) 83–92.
date_created: 2020-09-02T12:08:22Z
date_updated: 2022-01-06T06:53:52Z
department:
- _id: '63'
language:
- iso: eng
page: 83-92
publication: Proceedings of the 43th Symposium on Foundations of Computer Science
(FOCS)
status: public
title: Abstract Combinatorial Programs and Efficient Property Testers
type: journal_article
user_id: '15415'
year: '2002'
...
---
_id: '18961'
author:
- first_name: Tamás
full_name: Lukovszki, Tamás
last_name: Lukovszki
- first_name: A.
full_name: Benczúr, A.
last_name: Benczúr
citation:
ama: Lukovszki T, Benczúr A. A Degree O(Log Log n) Fault Tolerant Distributed
Location Service for Geographic Ad-Hoc Routing. Paderborn; 2002.
apa: Lukovszki, T., & Benczúr, A. (2002). A Degree O(log log n) Fault Tolerant
Distributed Location Service for Geographic Ad-Hoc Routing. Paderborn.
bibtex: '@book{Lukovszki_Benczúr_2002, place={Paderborn}, title={A Degree O(log
log n) Fault Tolerant Distributed Location Service for Geographic Ad-Hoc Routing},
author={Lukovszki, Tamás and Benczúr, A.}, year={2002} }'
chicago: Lukovszki, Tamás, and A. Benczúr. A Degree O(Log Log n) Fault Tolerant
Distributed Location Service for Geographic Ad-Hoc Routing. Paderborn, 2002.
ieee: T. Lukovszki and A. Benczúr, A Degree O(log log n) Fault Tolerant Distributed
Location Service for Geographic Ad-Hoc Routing. Paderborn, 2002.
mla: Lukovszki, Tamás, and A. Benczúr. A Degree O(Log Log n) Fault Tolerant Distributed
Location Service for Geographic Ad-Hoc Routing. 2002.
short: T. Lukovszki, A. Benczúr, A Degree O(Log Log n) Fault Tolerant Distributed
Location Service for Geographic Ad-Hoc Routing, Paderborn, 2002.
date_created: 2020-09-03T13:16:48Z
date_updated: 2022-01-06T06:53:55Z
department:
- _id: '63'
language:
- iso: eng
place: Paderborn
status: public
title: A Degree O(log log n) Fault Tolerant Distributed Location Service for Geographic
Ad-Hoc Routing
type: report
user_id: '15415'
year: '2002'
...
---
_id: '1921'
author:
- first_name: Thu
full_name: Ngo-Quynh, Thu
last_name: Ngo-Quynh
- first_name: Holger
full_name: Karl, Holger
id: '126'
last_name: Karl
- first_name: Adam
full_name: Wolisz, Adam
last_name: Wolisz
- first_name: Klaus
full_name: Rebensburg, Klaus
last_name: Rebensburg
citation:
ama: 'Ngo-Quynh T, Karl H, Wolisz A, Rebensburg K. New Scheduling Algorithm for
Providing Proportional Jitter in Differentiated Service Network . In: Proc.
IST Mobile & Wireless Telecommunications Summit 2002. ; 2002.'
apa: Ngo-Quynh, T., Karl, H., Wolisz, A., & Rebensburg, K. (2002). New Scheduling
Algorithm for Providing Proportional Jitter in Differentiated Service Network
. In Proc. IST Mobile & Wireless Telecommunications Summit 2002.
bibtex: '@inproceedings{Ngo-Quynh_Karl_Wolisz_Rebensburg_2002, title={New Scheduling
Algorithm for Providing Proportional Jitter in Differentiated Service Network
}, booktitle={Proc. IST Mobile & Wireless Telecommunications Summit 2002.},
author={Ngo-Quynh, Thu and Karl, Holger and Wolisz, Adam and Rebensburg, Klaus},
year={2002} }'
chicago: Ngo-Quynh, Thu, Holger Karl, Adam Wolisz, and Klaus Rebensburg. “New Scheduling
Algorithm for Providing Proportional Jitter in Differentiated Service Network
.” In Proc. IST Mobile & Wireless Telecommunications Summit 2002.,
2002.
ieee: T. Ngo-Quynh, H. Karl, A. Wolisz, and K. Rebensburg, “New Scheduling Algorithm
for Providing Proportional Jitter in Differentiated Service Network ,” in Proc.
IST Mobile & Wireless Telecommunications Summit 2002., 2002.
mla: Ngo-Quynh, Thu, et al. “New Scheduling Algorithm for Providing Proportional
Jitter in Differentiated Service Network .” Proc. IST Mobile & Wireless
Telecommunications Summit 2002., 2002.
short: 'T. Ngo-Quynh, H. Karl, A. Wolisz, K. Rebensburg, in: Proc. IST Mobile &
Wireless Telecommunications Summit 2002., 2002.'
date_created: 2018-03-28T11:36:45Z
date_updated: 2022-01-06T06:54:00Z
department:
- _id: '75'
publication: Proc. IST Mobile & Wireless Telecommunications Summit 2002.
status: public
title: 'New Scheduling Algorithm for Providing Proportional Jitter in Differentiated
Service Network '
type: conference
user_id: '15572'
year: '2002'
...
---
_id: '18169'
abstract:
- lang: ger
text: Die Implementierung von Algorithmen zur Lösung geometrischer Probleme im Euklidischen
Raum (z.B. Berechnung der konvexen Hülle oder des Durchschnitts zweier Polyeder)
stellt sich oftmals als hochgradig nichttrivial heraus. Ob und unter welchen Voraussetzungen
die verursachenden numerischen Instabilitäten überhaupt ini den Griff zu kriegen
oder vielmehr dem Problem inhärent sind, untersucht diese Arbeit in einem auf
Turing zurückgehenden Rechenmodell. Im Gegensatz zu algebraischen Ansätzen geht
jenes nicht von der Verfügbarkeit exakter Tests auf z.B. Gleichheit reeller Zahlen
aus, sondern berücksichtigt die auf Digitalcomputern tatsächlich realisierbare
Approximation durch rationale Zahlen. In diesem Rahmen werden beweisbar stabile
Algorithmen zum Lösen linearer Gleichungssysteme, zur Matrix-Diagonalisierung
und zur linearen wie nichtlinearen Optimierung präsentiert. Als wichtiges technisches
Hilfsmittel dient ein neuer Berechenbarkeitsbegriff für reguläre unendliche Mengen
reller Zahlen, der sich aus dem systematischen Vergleich verschiedener der Literatur
entnommener ad-hoc Ansätze ergibt.
- lang: eng
text: Quite often, the implementation of well-known algorithms for solving geometric
problems in Euclidean space (such as convex hull computation or intersecting two
polyhedra) turns out to be a highly nontrivial task. Whether and under what prerequisites
the underlying numerical numerical instabilities can be avoided or are rather
inherent to the problem is investigated by the present work in a model of computation
dating back to Alan Turing himself. Other than algebraic approaches, this does
not rely on (volatile) exact tests for, e.g., equality of real numbers but reflects
the property of actual digital computers to only approximate real numbers by rationals.
In this framework, we devise and present provably stable algorithms for solving
systems of linear equations, matrix diagonalization, and lineare as well as non-linear
optimization. As major technical tool, a new notion of computability for regular
infinite sets of real numbers is introduced that arises from formalizing and systematically
comparing several ad-hoc notions found in previous literature.
author:
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
citation:
ama: Ziegler M. Zur Berechenbarkeit reeller geometrischer Probleme. Vol 115.
Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn; 2002.
apa: Ziegler, M. (2002). Zur Berechenbarkeit reeller geometrischer Probleme
(Vol. 115). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn.
bibtex: '@book{Ziegler_2002, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn}, title={Zur Berechenbarkeit reeller geometrischer Probleme}, volume={115},
publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, author={Ziegler,
Martin}, year={2002}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn} }'
chicago: Ziegler, Martin. Zur Berechenbarkeit reeller geometrischer Probleme.
Vol. 115. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2002.
ieee: M. Ziegler, Zur Berechenbarkeit reeller geometrischer Probleme, vol.
115. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2002.
mla: Ziegler, Martin. Zur Berechenbarkeit reeller geometrischer Probleme.
Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2002.
short: M. Ziegler, Zur Berechenbarkeit reeller geometrischer Probleme, Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2002.
date_created: 2020-08-24T11:36:55Z
date_updated: 2022-01-06T06:53:26Z
department:
- _id: '63'
- _id: '26'
intvolume: ' 115'
language:
- iso: ger
publication_identifier:
isbn:
- 3-935433-24-7
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
related_material:
link:
- relation: confirmation
url: http://digital.ub.uni-paderborn.de/ubpb/urn/urn:nbn:de:hbz:466-20020101320
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: Zur Berechenbarkeit reeller geometrischer Probleme
type: dissertation
user_id: '5786'
volume: 115
year: '2002'
...
---
_id: '18176'
author:
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
citation:
ama: Ziegler M. Computability on Regular Subsets of Euclidean Space. Mathematical
Logic Quarterly (MLQ). 2002;48(S1):157-181. doi:10.1002/1521-3870(200210)48:1+<157::aid-malq157>3.0.co;2-4
apa: Ziegler, M. (2002). Computability on Regular Subsets of Euclidean Space. Mathematical
Logic Quarterly (MLQ), 48(S1), 157–181. https://doi.org/10.1002/1521-3870(200210)48:1+<157::aid-malq157>3.0.co;2-4
bibtex: '@article{Ziegler_2002, title={Computability on Regular Subsets of Euclidean
Space}, volume={48}, DOI={10.1002/1521-3870(200210)48:1+<157::aid-malq157>3.0.co;2-4},
number={S1}, journal={Mathematical Logic Quarterly (MLQ)}, author={Ziegler, Martin},
year={2002}, pages={157–181} }'
chicago: 'Ziegler, Martin. “Computability on Regular Subsets of Euclidean Space.”
Mathematical Logic Quarterly (MLQ) 48, no. S1 (2002): 157–81. https://doi.org/10.1002/1521-3870(200210)48:1+<157::aid-malq157>3.0.co;2-4.'
ieee: M. Ziegler, “Computability on Regular Subsets of Euclidean Space,” Mathematical
Logic Quarterly (MLQ), vol. 48, no. S1, pp. 157–181, 2002.
mla: Ziegler, Martin. “Computability on Regular Subsets of Euclidean Space.” Mathematical
Logic Quarterly (MLQ), vol. 48, no. S1, 2002, pp. 157–81, doi:10.1002/1521-3870(200210)48:1+<157::aid-malq157>3.0.co;2-4.
short: M. Ziegler, Mathematical Logic Quarterly (MLQ) 48 (2002) 157–181.
date_created: 2020-08-24T12:05:40Z
date_updated: 2022-01-06T06:53:26Z
department:
- _id: '63'
doi: 10.1002/1521-3870(200210)48:1+<157::aid-malq157>3.0.co;2-4
intvolume: ' 48'
issue: S1
language:
- iso: eng
page: 157-181
publication: Mathematical Logic Quarterly (MLQ)
publication_identifier:
issn:
- 0942-5616
- 1521-3870
publication_status: published
status: public
title: Computability on Regular Subsets of Euclidean Space
type: journal_article
user_id: '15415'
volume: 48
year: '2002'
...
---
_id: '18177'
abstract:
- lang: eng
text: 'Consider the classical point location problem: for a fixed arrangement of
m hyperplanes and its induced partition of d-space report, upon input of some
point, which face it lies in. With sufficient memory, this is easy to solve in
logarithmic time O(log m). But how fast can algorithms (formalized as Linear Decision
Trees) of *minimum* size be? The present work gives lower and upper bounds for
the time complexity of point location under this constraint. They show that, in
addition to m, the maximum number w of walls of a cell turns out to be a crucial
parameter. We also consider a relaxation of the strict minimum-size condition
allowing for constant factor overhead.'
author:
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
- first_name: Valentina
full_name: Damerow, Valentina
last_name: Damerow
- first_name: Lukas
full_name: Finschi, Lukas
last_name: Finschi
citation:
ama: 'Ziegler M, Damerow V, Finschi L. Point Location Algorithms of Minimum Size.
In: Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG’02).
; 2002.'
apa: Ziegler, M., Damerow, V., & Finschi, L. (2002). Point Location Algorithms
of Minimum Size. In Proceedings of the 14th Canadian Conference on Computational
Geometry (CCCG’02).
bibtex: '@inproceedings{Ziegler_Damerow_Finschi_2002, title={Point Location Algorithms
of Minimum Size}, booktitle={Proceedings of the 14th Canadian Conference on Computational
Geometry (CCCG’02)}, author={Ziegler, Martin and Damerow, Valentina and Finschi,
Lukas}, year={2002} }'
chicago: Ziegler, Martin, Valentina Damerow, and Lukas Finschi. “Point Location
Algorithms of Minimum Size.” In Proceedings of the 14th Canadian Conference
on Computational Geometry (CCCG’02), 2002.
ieee: M. Ziegler, V. Damerow, and L. Finschi, “Point Location Algorithms of Minimum
Size,” in Proceedings of the 14th Canadian Conference on Computational Geometry
(CCCG’02), 2002.
mla: Ziegler, Martin, et al. “Point Location Algorithms of Minimum Size.” Proceedings
of the 14th Canadian Conference on Computational Geometry (CCCG’02), 2002.
short: 'M. Ziegler, V. Damerow, L. Finschi, in: Proceedings of the 14th Canadian
Conference on Computational Geometry (CCCG’02), 2002.'
date_created: 2020-08-24T12:09:15Z
date_updated: 2022-01-06T06:53:26Z
department:
- _id: '63'
language:
- iso: eng
publication: Proceedings of the 14th Canadian Conference on Computational Geometry
(CCCG'02)
publication_status: published
status: public
title: Point Location Algorithms of Minimum Size
type: conference
user_id: '15415'
year: '2002'
...