---
_id: '31847'
abstract:
- lang: eng
text: "The famous $k$-Server Problem covers plenty of resource allocation scenarios,
and several variations have been studied extensively for decades. However, to
the best of our knowledge, no research has considered the problem if the servers
are not identical and requests can express which specific servers should serve
them. Therefore, we present a new model generalizing the $k$-Server Problem by
*preferences* of the requests and proceed to study it in a uniform metric space
for deterministic online algorithms (the special case of paging).\r\n\r\nIn our
model, requests can either demand to be answered by any server (*general requests*)
or by a specific one (*specific requests*). If only general requests appear, the
instance is one of the original $k$-Server Problem, and a lower bound for the
competitive ratio of $k$ applies. If only specific requests appear, a solution
with a competitive ratio of $1$ becomes trivial since there is no freedom regarding
the servers' movements. Perhaps counter-intuitively, we show that if both kinds
of requests appear, the lower bound raises to $2k-1$.\r\n\r\nWe study deterministic
online algorithms in uniform metrics and present two algorithms. The first one
has an adaptive competitive ratio dependent on the frequency of specific requests.
It achieves a worst-case competitive ratio of $3k-2$ while it is optimal when
only general or only specific requests appear (competitive ratio of $k$ and $1$,
respectively). The second has a fixed close-to-optimal worst-case competitive
ratio of $2k+14$. For the first algorithm, we show a lower bound of $3k-2$, while
the second algorithm has a lower bound of $2k-1$ when only general requests appear.\r\n
\ \r\nThe two algorithms differ in only one behavioral rule for each server
that significantly influences the competitive ratio. Each server acting according
to the rule allows approaching the worst-case lower bound, while it implies an
increased lower bound for $k$-Server instances. In other words, there is a trade-off
between performing well against instances of the $k$-Server Problem and instances
containing specific requests. We also show that no deterministic online algorithm
can be optimal for both kinds of instances simultaneously."
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Manuel
full_name: Malatyali, Manuel
id: '41265'
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Castenow J, Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. The
k-Server with Preferences Problem. In: Proceedings of the 34th ACM Symposium
on Parallelism in Algorithms and Architectures. Association for Computing
Machinery; 2022:345-356. doi:10.1145/3490148.3538595'
apa: Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., & Meyer auf der
Heide, F. (2022). The k-Server with Preferences Problem. Proceedings of the
34th ACM Symposium on Parallelism in Algorithms and Architectures, 345–356.
https://doi.org/10.1145/3490148.3538595
bibtex: '@inproceedings{Castenow_Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2022,
title={The k-Server with Preferences Problem}, DOI={10.1145/3490148.3538595},
booktitle={Proceedings of the 34th ACM Symposium on Parallelism in Algorithms
and Architectures}, publisher={Association for Computing Machinery}, author={Castenow,
Jannik and Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer
auf der Heide, Friedhelm}, year={2022}, pages={345–356} }'
chicago: Castenow, Jannik, Björn Feldkord, Till Knollmann, Manuel Malatyali, and
Friedhelm Meyer auf der Heide. “The K-Server with Preferences Problem.” In Proceedings
of the 34th ACM Symposium on Parallelism in Algorithms and Architectures,
345–56. Association for Computing Machinery, 2022. https://doi.org/10.1145/3490148.3538595.
ieee: 'J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der
Heide, “The k-Server with Preferences Problem,” in Proceedings of the 34th
ACM Symposium on Parallelism in Algorithms and Architectures, 2022, pp. 345–356,
doi: 10.1145/3490148.3538595.'
mla: Castenow, Jannik, et al. “The K-Server with Preferences Problem.” Proceedings
of the 34th ACM Symposium on Parallelism in Algorithms and Architectures,
Association for Computing Machinery, 2022, pp. 345–56, doi:10.1145/3490148.3538595.
short: 'J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide,
in: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures,
Association for Computing Machinery, 2022, pp. 345–356.'
date_created: 2022-06-10T09:06:42Z
date_updated: 2022-08-02T08:07:30Z
department:
- _id: '63'
doi: 10.1145/3490148.3538595
external_id:
arxiv:
- '2205.11102'
keyword:
- K-Server Problem
- Heterogeneity
- Online Caching
language:
- iso: eng
page: 345-356
project:
- _id: '1'
name: 'SFB 901: SFB 901'
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '5'
name: 'SFB 901 - A1: SFB 901 - Subproject A1'
publication: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and
Architectures
publication_identifier:
isbn:
- '9781450391467'
publisher: Association for Computing Machinery
status: public
title: The k-Server with Preferences Problem
type: conference
user_id: '39241'
year: '2022'
...
---
_id: '2367'
abstract:
- lang: eng
text: One of the most popular fuzzy clustering techniques is the fuzzy K-means algorithm
(also known as fuzzy-c-means or FCM algorithm). In contrast to the K-means and
K-median problem, the underlying fuzzy K-means problem has not been studied from
a theoretical point of view. In particular, there are no algorithms with approximation
guarantees similar to the famous K-means++ algorithm known for the fuzzy K-means
problem. This work initiates the study of the fuzzy K-means problem from an algorithmic
and complexity theoretic perspective. We show that optimal solutions for the fuzzy
K-means problem cannot, in general, be expressed by radicals over the input points.
Surprisingly, this already holds for simple inputs in one-dimensional space. Hence,
one cannot expect to compute optimal solutions exactly. We give the first (1+eps)-approximation
algorithms for the fuzzy K-means problem. First, we present a deterministic approximation
algorithm whose runtime is polynomial in N and linear in the dimension D of the
input set, given that K is constant, i.e. a polynomial time approximation scheme
(PTAS) for fixed K. We achieve this result by showing that for each soft clustering
there exists a hard clustering with similar properties. Second, by using techniques
known from coreset constructions for the K-means problem, we develop a deterministic
approximation algorithm that runs in time almost linear in N but exponential in
the dimension D. We complement these results with a randomized algorithm which
imposes some natural restrictions on the sought solution and whose runtime is
comparable to some of the most efficient approximation algorithms for K-means,
i.e. linear in the number of points and the dimension, but exponential in the
number of clusters.
author:
- first_name: Johannes
full_name: Blömer, Johannes
id: '23'
last_name: Blömer
- first_name: Sascha
full_name: Brauer, Sascha
id: '13291'
last_name: Brauer
- first_name: Kathrin
full_name: Bujna, Kathrin
last_name: Bujna
citation:
ama: 'Blömer J, Brauer S, Bujna K. A Theoretical Analysis of the Fuzzy K-Means Problem.
In: 2016 IEEE 16th International Conference on Data Mining (ICDM). IEEE;
2016:805-810. doi:10.1109/icdm.2016.0094'
apa: 'Blömer, J., Brauer, S., & Bujna, K. (2016). A Theoretical Analysis of
the Fuzzy K-Means Problem. In 2016 IEEE 16th International Conference on Data
Mining (ICDM) (pp. 805–810). Barcelona, Spain: IEEE. https://doi.org/10.1109/icdm.2016.0094'
bibtex: '@inproceedings{Blömer_Brauer_Bujna_2016, title={A Theoretical Analysis
of the Fuzzy K-Means Problem}, DOI={10.1109/icdm.2016.0094},
booktitle={2016 IEEE 16th International Conference on Data Mining (ICDM)}, publisher={IEEE},
author={Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}, year={2016},
pages={805–810} }'
chicago: Blömer, Johannes, Sascha Brauer, and Kathrin Bujna. “A Theoretical Analysis
of the Fuzzy K-Means Problem.” In 2016 IEEE 16th International Conference on
Data Mining (ICDM), 805–10. IEEE, 2016. https://doi.org/10.1109/icdm.2016.0094.
ieee: J. Blömer, S. Brauer, and K. Bujna, “A Theoretical Analysis of the Fuzzy K-Means
Problem,” in 2016 IEEE 16th International Conference on Data Mining (ICDM),
Barcelona, Spain, 2016, pp. 805–810.
mla: Blömer, Johannes, et al. “A Theoretical Analysis of the Fuzzy K-Means Problem.”
2016 IEEE 16th International Conference on Data Mining (ICDM), IEEE, 2016,
pp. 805–10, doi:10.1109/icdm.2016.0094.
short: 'J. Blömer, S. Brauer, K. Bujna, in: 2016 IEEE 16th International Conference
on Data Mining (ICDM), IEEE, 2016, pp. 805–810.'
conference:
end_date: 2016-12-15
location: Barcelona, Spain
name: IEEE 16th International Conference on Data Mining (ICDM)
start_date: 2016-12-12
date_created: 2018-04-17T11:46:07Z
date_updated: 2022-01-06T06:55:58Z
department:
- _id: '64'
doi: 10.1109/icdm.2016.0094
keyword:
- unsolvability by radicals
- clustering
- fuzzy k-means
- probabilistic method
- approximation algorithms
- randomized algorithms
language:
- iso: eng
page: 805-810
publication: 2016 IEEE 16th International Conference on Data Mining (ICDM)
publication_identifier:
isbn:
- '9781509054732'
publication_status: published
publisher: IEEE
status: public
title: A Theoretical Analysis of the Fuzzy K-Means Problem
type: conference
user_id: '25078'
year: '2016'
...
---
_id: '2990'
author:
- first_name: Marcel R.
full_name: Ackermann, Marcel R.
last_name: Ackermann
- first_name: Johannes
full_name: Blömer, Johannes
id: '23'
last_name: Blömer
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
citation:
ama: Ackermann MR, Blömer J, Sohler C. Clustering for Metric and Nonmetric Distance
Measures. ACM Trans Algorithms. 2010;(4):59:1--59:26. doi:10.1145/1824777.1824779
apa: Ackermann, M. R., Blömer, J., & Sohler, C. (2010). Clustering for Metric
and Nonmetric Distance Measures. ACM Trans. Algorithms, (4), 59:1--59:26.
https://doi.org/10.1145/1824777.1824779
bibtex: '@article{Ackermann_Blömer_Sohler_2010, title={Clustering for Metric and
Nonmetric Distance Measures}, DOI={10.1145/1824777.1824779},
number={4}, journal={ACM Trans. Algorithms}, author={Ackermann, Marcel R. and
Blömer, Johannes and Sohler, Christian}, year={2010}, pages={59:1--59:26} }'
chicago: 'Ackermann, Marcel R., Johannes Blömer, and Christian Sohler. “Clustering
for Metric and Nonmetric Distance Measures.” ACM Trans. Algorithms, no.
4 (2010): 59:1--59:26. https://doi.org/10.1145/1824777.1824779.'
ieee: M. R. Ackermann, J. Blömer, and C. Sohler, “Clustering for Metric and Nonmetric
Distance Measures,” ACM Trans. Algorithms, no. 4, pp. 59:1--59:26, 2010.
mla: Ackermann, Marcel R., et al. “Clustering for Metric and Nonmetric Distance
Measures.” ACM Trans. Algorithms, no. 4, 2010, pp. 59:1--59:26, doi:10.1145/1824777.1824779.
short: M.R. Ackermann, J. Blömer, C. Sohler, ACM Trans. Algorithms (2010) 59:1--59:26.
date_created: 2018-06-05T07:52:41Z
date_updated: 2022-01-06T06:58:50Z
department:
- _id: '64'
doi: 10.1145/1824777.1824779
issue: '4'
keyword:
- k-means clustering
- k-median clustering
- Approximation algorithm
- Bregman divergences
- Itakura-Saito divergence
- Kullback-Leibler divergence
- Mahalanobis distance
- random sampling
page: 59:1--59:26
publication: ACM Trans. Algorithms
publication_identifier:
issn:
- 1549-6325
publication_status: published
status: public
title: Clustering for Metric and Nonmetric Distance Measures
type: journal_article
user_id: '25078'
year: '2010'
...
---
_id: '9759'
abstract:
- lang: eng
text: Among various lead-free piezoelectric materials, (K,Na)NbO$_{3}$ is a very
promising candidate. In this study, (K,Na)NbO$_{3}$ ceramics were sintered from
mixed (K,Na)NbO$_{3}$ and NaNbO$_{3}$ powders prepared by hydrothermal reaction.
These two powders were mixed with distilled water in a KNbO$_{3}$/NaNbO$_{3}$
molar ratio of 1. After sintering the mixed powder, the solid solution of (Na,K)NbO$_{3}$
ceramics was obtained. The electrical properties such as the electromechanical
coupling factors k$_{p}$ and k$_{33}$, the mechanical quality factor, Q$_{m}$,
and the piezoelectric constant d$_{33}$ of the sintered (K,Na)NbO$_{3}$ ceramics
were 0.32, 0.48, 71 (radial mode), 118 ((33)mode), and 107 pC/N, respectively.
author:
- first_name: Takafumi
full_name: Maeda, Takafumi
last_name: Maeda
- first_name: Norihito
full_name: Takiguchi, Norihito
last_name: Takiguchi
- first_name: Takeshi
full_name: Morita, Takeshi
last_name: Morita
- first_name: Mutsuo
full_name: Ishikawa, Mutsuo
last_name: Ishikawa
- first_name: Tobias
full_name: Hemsel, Tobias
id: '210'
last_name: Hemsel
citation:
ama: Maeda T, Takiguchi N, Morita T, Ishikawa M, Hemsel T. (K,Na)NbO3 lead-free
piezoelectric ceramics synthesized from hydrothermal powders. Materials Letters.
2010;64(2):125-128. doi:10.1016/j.matlet.2009.10.012
apa: Maeda, T., Takiguchi, N., Morita, T., Ishikawa, M., & Hemsel, T. (2010).
(K,Na)NbO3 lead-free piezoelectric ceramics synthesized from hydrothermal powders.
Materials Letters, 64(2), 125–128. https://doi.org/10.1016/j.matlet.2009.10.012
bibtex: '@article{Maeda_Takiguchi_Morita_Ishikawa_Hemsel_2010, title={(K,Na)NbO3
lead-free piezoelectric ceramics synthesized from hydrothermal powders}, volume={64},
DOI={10.1016/j.matlet.2009.10.012},
number={2}, journal={Materials Letters}, author={Maeda, Takafumi and Takiguchi,
Norihito and Morita, Takeshi and Ishikawa, Mutsuo and Hemsel, Tobias}, year={2010},
pages={125–128} }'
chicago: 'Maeda, Takafumi, Norihito Takiguchi, Takeshi Morita, Mutsuo Ishikawa,
and Tobias Hemsel. “(K,Na)NbO3 Lead-Free Piezoelectric Ceramics Synthesized from
Hydrothermal Powders.” Materials Letters 64, no. 2 (2010): 125–28. https://doi.org/10.1016/j.matlet.2009.10.012.'
ieee: T. Maeda, N. Takiguchi, T. Morita, M. Ishikawa, and T. Hemsel, “(K,Na)NbO3
lead-free piezoelectric ceramics synthesized from hydrothermal powders,” Materials
Letters, vol. 64, no. 2, pp. 125–128, 2010.
mla: Maeda, Takafumi, et al. “(K,Na)NbO3 Lead-Free Piezoelectric Ceramics Synthesized
from Hydrothermal Powders.” Materials Letters, vol. 64, no. 2, 2010, pp.
125–28, doi:10.1016/j.matlet.2009.10.012.
short: T. Maeda, N. Takiguchi, T. Morita, M. Ishikawa, T. Hemsel, Materials Letters
64 (2010) 125–128.
date_created: 2019-05-13T10:21:17Z
date_updated: 2022-01-06T07:04:19Z
department:
- _id: '151'
doi: 10.1016/j.matlet.2009.10.012
intvolume: ' 64'
issue: '2'
keyword:
- Lead-free piezoelectric material
- (K
- Na)NbO$_{3}$ ceramics
- Sintering solid solution
- Piezoelectric properties
language:
- iso: eng
page: 125-128
publication: Materials Letters
publication_identifier:
issn:
- 1948-5719
quality_controlled: '1'
status: public
title: (K,Na)NbO3 lead-free piezoelectric ceramics synthesized from hydrothermal powders
type: journal_article
user_id: '55222'
volume: 64
year: '2010'
...