@inproceedings{31847, abstract = {{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). In 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$. We 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. The 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 = {{Castenow, Jannik and Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures}}, isbn = {{9781450391467}}, keywords = {{K-Server Problem, Heterogeneity, Online Caching}}, pages = {{345--356}}, publisher = {{Association for Computing Machinery}}, title = {{{The k-Server with Preferences Problem}}}, doi = {{10.1145/3490148.3538595}}, year = {{2022}}, } @inproceedings{2367, abstract = {{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 = {{Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}}, booktitle = {{2016 IEEE 16th International Conference on Data Mining (ICDM)}}, isbn = {{9781509054732}}, keywords = {{unsolvability by radicals, clustering, fuzzy k-means, probabilistic method, approximation algorithms, randomized algorithms}}, location = {{Barcelona, Spain}}, pages = {{805--810}}, publisher = {{IEEE}}, title = {{{A Theoretical Analysis of the Fuzzy K-Means Problem}}}, doi = {{10.1109/icdm.2016.0094}}, year = {{2016}}, } @article{2990, author = {{Ackermann, Marcel R. and Blömer, Johannes and Sohler, Christian}}, issn = {{1549-6325}}, journal = {{ACM Trans. Algorithms}}, keywords = {{k-means clustering, k-median clustering, Approximation algorithm, Bregman divergences, Itakura-Saito divergence, Kullback-Leibler divergence, Mahalanobis distance, random sampling}}, number = {{4}}, pages = {{59:1----59:26}}, title = {{{Clustering for Metric and Nonmetric Distance Measures}}}, doi = {{10.1145/1824777.1824779}}, year = {{2010}}, } @article{9759, abstract = {{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 = {{Maeda, Takafumi and Takiguchi, Norihito and Morita, Takeshi and Ishikawa, Mutsuo and Hemsel, Tobias}}, issn = {{1948-5719}}, journal = {{Materials Letters}}, keywords = {{Lead-free piezoelectric material, (K, Na)NbO$_{3}$ ceramics, Sintering solid solution, Piezoelectric properties}}, number = {{2}}, pages = {{125--128}}, title = {{{(K,Na)NbO3 lead-free piezoelectric ceramics synthesized from hydrothermal powders}}}, doi = {{10.1016/j.matlet.2009.10.012}}, volume = {{64}}, year = {{2010}}, }