---
_id: '10586'
abstract:
- lang: eng
text: We consider the problem of transforming a given graph G_s into a desired graph
G_t by applying a minimum number of primitives from a particular set of local
graph transformation primitives. These primitives are local in the sense that
each node can apply them based on local knowledge and by affecting only its 1-neighborhood.
Although the specific set of primitives we consider makes it possible to transform
any (weakly) connected graph into any other (weakly) connected graph consisting
of the same nodes, they cannot disconnect the graph or introduce new nodes into
the graph, making them ideal in the context of supervised overlay network transformations.
We prove that computing a minimum sequence of primitive applications (even centralized)
for arbitrary G_s and G_t is NP-hard, which we conjecture to hold for any set
of local graph transformation primitives satisfying the aforementioned properties.
On the other hand, we show that this problem admits a polynomial time algorithm
with a constant approximation ratio.
accept: '1'
author:
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Alexander
full_name: Setzer, Alexander
id: '11108'
last_name: Setzer
citation:
ama: 'Scheideler C, Setzer A. On the Complexity of Local Graph Transformations.
In: *Proceedings of the 46th International Colloquium on Automata, Languages,
and Programming*. Vol 132. LIPIcs. Dagstuhl Publishing; 2019:150:1--150:14.
doi:10.4230/LIPICS.ICALP.2019.150'
apa: 'Scheideler, C., & Setzer, A. (2019). On the Complexity of Local Graph
Transformations. In *Proceedings of the 46th International Colloquium on Automata,
Languages, and Programming* (Vol. 132, pp. 150:1--150:14). Patras, Greece:
Dagstuhl Publishing. https://doi.org/10.4230/LIPICS.ICALP.2019.150'
bibtex: '@inproceedings{Scheideler_Setzer_2019, series={LIPIcs}, title={On the Complexity
of Local Graph Transformations}, volume={132}, DOI={10.4230/LIPICS.ICALP.2019.150},
booktitle={Proceedings of the 46th International Colloquium on Automata, Languages,
and Programming}, publisher={Dagstuhl Publishing}, author={Scheideler, Christian
and Setzer, Alexander}, year={2019}, pages={150:1--150:14}, collection={LIPIcs}
}'
chicago: Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local
Graph Transformations.” In *Proceedings of the 46th International Colloquium
on Automata, Languages, and Programming*, 132:150:1--150:14. LIPIcs. Dagstuhl
Publishing, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.150.
ieee: C. Scheideler and A. Setzer, “On the Complexity of Local Graph Transformations,”
in *Proceedings of the 46th International Colloquium on Automata, Languages,
and Programming*, Patras, Greece, 2019, vol. 132, pp. 150:1--150:14.
mla: Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local Graph
Transformations.” *Proceedings of the 46th International Colloquium on Automata,
Languages, and Programming*, vol. 132, Dagstuhl Publishing, 2019, pp. 150:1--150:14,
doi:10.4230/LIPICS.ICALP.2019.150.
short: 'C. Scheideler, A. Setzer, in: Proceedings of the 46th International Colloquium
on Automata, Languages, and Programming, Dagstuhl Publishing, 2019, pp. 150:1--150:14.'
conference:
end_date: 2019-07-12
location: Patras, Greece
name: ICALP 2019
start_date: 2019-07-09
date_created: 2019-07-08T17:19:01Z
date_updated: 2019-11-25T14:28:43Z
ddc:
- '004'
department:
- _id: '79'
doi: 10.4230/LIPICS.ICALP.2019.150
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2019-08-26T09:21:27Z
date_updated: 2019-08-26T09:21:27Z
file_id: '12955'
file_name: LIPIcs-ICALP-2019-150.pdf
file_size: 537649
relation: main_file
success: 1
file_date_updated: 2019-08-26T09:21:27Z
intvolume: ' 132'
keyword:
- Graphs transformations
- NP-hardness
- approximation algorithms
language:
- iso: eng
page: 150:1--150:14
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subproject A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of the 46th International Colloquium on Automata, Languages,
and Programming
publication_status: published
publisher: Dagstuhl Publishing
series_title: LIPIcs
status: public
title: On the Complexity of Local Graph Transformations
type: conference
user_id: '477'
volume: 132
year: '2019'
...
---
_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: 2019-01-03T13:13:06Z
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'
...