---
_id: '63053'
author:
- first_name: Carlos
full_name: Hernández, Carlos
last_name: Hernández
- first_name: Angel E.
full_name: Rodriguez-Fernandez, Angel E.
last_name: Rodriguez-Fernandez
- first_name: Lennart
full_name: Schäpermeier, Lennart
last_name: Schäpermeier
- first_name: Oliver
full_name: Cuate, Oliver
last_name: Cuate
- first_name: Heike
full_name: Trautmann, Heike
id: '100740'
last_name: Trautmann
orcid: 0000-0002-9788-8282
- first_name: Oliver
full_name: Schütze, Oliver
last_name: Schütze
citation:
ama: Hernández C, Rodriguez-Fernandez AE, Schäpermeier L, Cuate O, Trautmann H,
Schütze O. An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions
for Multi-Objective Multimodal Optimization. IEEE Transactions on Evolutionary
Computation. Published online 2025:1-1. doi:10.1109/TEVC.2025.3637276
apa: Hernández, C., Rodriguez-Fernandez, A. E., Schäpermeier, L., Cuate, O., Trautmann,
H., & Schütze, O. (2025). An Evolutionary Approach for the Computation of
∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization. IEEE
Transactions on Evolutionary Computation, 1–1. https://doi.org/10.1109/TEVC.2025.3637276
bibtex: '@article{Hernández_Rodriguez-Fernandez_Schäpermeier_Cuate_Trautmann_Schütze_2025,
title={An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions
for Multi-Objective Multimodal Optimization}, DOI={10.1109/TEVC.2025.3637276},
journal={IEEE Transactions on Evolutionary Computation}, author={Hernández, Carlos
and Rodriguez-Fernandez, Angel E. and Schäpermeier, Lennart and Cuate, Oliver
and Trautmann, Heike and Schütze, Oliver}, year={2025}, pages={1–1} }'
chicago: Hernández, Carlos, Angel E. Rodriguez-Fernandez, Lennart Schäpermeier,
Oliver Cuate, Heike Trautmann, and Oliver Schütze. “An Evolutionary Approach for
the Computation of ∈-Locally Optimal Solutions for Multi-Objective Multimodal
Optimization.” IEEE Transactions on Evolutionary Computation, 2025, 1–1.
https://doi.org/10.1109/TEVC.2025.3637276.
ieee: 'C. Hernández, A. E. Rodriguez-Fernandez, L. Schäpermeier, O. Cuate, H. Trautmann,
and O. Schütze, “An Evolutionary Approach for the Computation of ∈-Locally Optimal
Solutions for Multi-Objective Multimodal Optimization,” IEEE Transactions on
Evolutionary Computation, pp. 1–1, 2025, doi: 10.1109/TEVC.2025.3637276.'
mla: Hernández, Carlos, et al. “An Evolutionary Approach for the Computation of
∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization.” IEEE
Transactions on Evolutionary Computation, 2025, pp. 1–1, doi:10.1109/TEVC.2025.3637276.
short: C. Hernández, A.E. Rodriguez-Fernandez, L. Schäpermeier, O. Cuate, H. Trautmann,
O. Schütze, IEEE Transactions on Evolutionary Computation (2025) 1–1.
date_created: 2025-12-12T06:13:06Z
date_updated: 2025-12-12T06:13:51Z
department:
- _id: '819'
doi: 10.1109/TEVC.2025.3637276
keyword:
- Optimization
- Evolutionary computation
- Hands
- Proposals
- Convergence
- Computational efficiency
- Artificial intelligence
- Accuracy
- Approximation algorithms
- Aerospace electronics
- Multi-objective optimization
- evolutionary algorithms
- nearly optimal solutions
- multimodal optimization
- archiving
- continuation
language:
- iso: eng
page: 1-1
publication: IEEE Transactions on Evolutionary Computation
status: public
title: An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions
for Multi-Objective Multimodal Optimization
type: journal_article
user_id: '15504'
year: '2025'
...
---
_id: '56221'
author:
- first_name: Angel E.
full_name: Rodriguez-Fernandez, Angel E.
last_name: Rodriguez-Fernandez
- first_name: Lennart
full_name: Schäpermeier, Lennart
last_name: Schäpermeier
- first_name: Carlos
full_name: Hernández, Carlos
last_name: Hernández
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
- first_name: Heike
full_name: Trautmann, Heike
id: '100740'
last_name: Trautmann
orcid: 0000-0002-9788-8282
- first_name: Oliver
full_name: Schütze, Oliver
last_name: Schütze
citation:
ama: Rodriguez-Fernandez AE, Schäpermeier L, Hernández C, Kerschke P, Trautmann
H, Schütze O. Finding ϵ-Locally Optimal Solutions for Multi-Objective Multimodal
Optimization. IEEE Transactions on Evolutionary Computation. Published
online 2024:1-1. doi:10.1109/TEVC.2024.3458855
apa: Rodriguez-Fernandez, A. E., Schäpermeier, L., Hernández, C., Kerschke, P.,
Trautmann, H., & Schütze, O. (2024). Finding ϵ-Locally Optimal Solutions for
Multi-Objective Multimodal Optimization. IEEE Transactions on Evolutionary
Computation, 1–1. https://doi.org/10.1109/TEVC.2024.3458855
bibtex: '@article{Rodriguez-Fernandez_Schäpermeier_Hernández_Kerschke_Trautmann_Schütze_2024,
title={Finding ϵ-Locally Optimal Solutions for Multi-Objective Multimodal Optimization},
DOI={10.1109/TEVC.2024.3458855},
journal={IEEE Transactions on Evolutionary Computation}, author={Rodriguez-Fernandez,
Angel E. and Schäpermeier, Lennart and Hernández, Carlos and Kerschke, Pascal
and Trautmann, Heike and Schütze, Oliver}, year={2024}, pages={1–1} }'
chicago: Rodriguez-Fernandez, Angel E., Lennart Schäpermeier, Carlos Hernández,
Pascal Kerschke, Heike Trautmann, and Oliver Schütze. “Finding ϵ-Locally Optimal
Solutions for Multi-Objective Multimodal Optimization.” IEEE Transactions on
Evolutionary Computation, 2024, 1–1. https://doi.org/10.1109/TEVC.2024.3458855.
ieee: 'A. E. Rodriguez-Fernandez, L. Schäpermeier, C. Hernández, P. Kerschke, H.
Trautmann, and O. Schütze, “Finding ϵ-Locally Optimal Solutions for Multi-Objective
Multimodal Optimization,” IEEE Transactions on Evolutionary Computation,
pp. 1–1, 2024, doi: 10.1109/TEVC.2024.3458855.'
mla: Rodriguez-Fernandez, Angel E., et al. “Finding ϵ-Locally Optimal Solutions
for Multi-Objective Multimodal Optimization.” IEEE Transactions on Evolutionary
Computation, 2024, pp. 1–1, doi:10.1109/TEVC.2024.3458855.
short: A.E. Rodriguez-Fernandez, L. Schäpermeier, C. Hernández, P. Kerschke, H.
Trautmann, O. Schütze, IEEE Transactions on Evolutionary Computation (2024) 1–1.
date_created: 2024-09-24T08:01:14Z
date_updated: 2024-09-24T08:01:47Z
doi: 10.1109/TEVC.2024.3458855
keyword:
- Optimization
- Evolutionary computation
- Approximation algorithms
- Benchmark testing
- Vectors
- Surveys
- Pareto optimization
- multi-objective optimization
- evolutionary computation
- multimodal optimization
- local solutions
language:
- iso: eng
page: 1-1
publication: IEEE Transactions on Evolutionary Computation
status: public
title: Finding ϵ-Locally Optimal Solutions for Multi-Objective Multimodal Optimization
type: journal_article
user_id: '15504'
year: '2024'
...
---
_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.
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: 2022-01-06T06:50:45Z
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
has_accepted_license: '1'
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: '10003'
abstract:
- lang: ger
text: Die Bestimmung des Frequenzübertragungsverhaltens von Strukturen mit nichtlinearer
Charakteristik ist eine im technischen Bereich vielfach auftretende Aufgabe, z.B.
für die genaue Bestimmung dynamischer Eigenschaften in der Entwurfsphase oder
bei der Parametrierung von Modellen. Die typisch angewandten Verfahren zur Schwingungsmessung
solcher Strukturen legen in der Regel ein lineares Strukturverhalten zu Grunde,
oder sie erfordern einen hohen Zeit- und Messaufwand für die Abbildung des nichtlinearen
Verhaltens; häufig in Verbindung mit einer starken Belastung der zu testenden
Struktur. Die Bestimmung nichtlinearen Strukturverhaltens ist somit oft nicht
effizient realisierbar. In der vorliegenden Arbeit wird ein neuer Ansatz zur Schwingungsanalyse
nichtlinearer Strukturen mit von der Anregungsamplitude abhängigem Übertragungsverhalten
vorgestellt. Dabei liegt ein Schwerpunkt auf der messtechnischen Bestimmung des
nichtlinearen Verhaltens bei deutlich reduziertem Zeit- bzw. Messaufwand. Das
Verfahren basiert auf einer Messmethode, die eine effiziente Bestimmung des nichtlinearen
Kennfeldes der analysierten Struktur mit speziellen multiharmonischen Anregungssignalen
ermöglicht. In Kombination mit einem fortschrittlichen Auswertealgorithmus kann
eine vollständige Beschreibung des dynamischen Verhaltens in Form eines charakteristischen
Diagramms generiert werden. Das Messverfahren wird durch eine Identifikationsroutine
ergänzt, die die erforderliche Anzahl an Messungen nochmals reduzieren kann. Es
ist als Mess-System auf Hard- und Software implementiert; der Funktionsnachweis
erfolgt an verschiedenen Beispielen.
author:
- first_name: Christian
full_name: Sprock, Christian
last_name: Sprock
citation:
ama: Sprock C. Zeiteffiziente Messtechnische Analyse Glatt-Nichtlinearen Schwingverhaltens
Dynamischer Strukturen. Shaker; 2019.
apa: Sprock, C. (2019). Zeiteffiziente messtechnische Analyse glatt-nichtlinearen
Schwingverhaltens dynamischer Strukturen. Shaker.
bibtex: '@book{Sprock_2019, title={Zeiteffiziente messtechnische Analyse glatt-nichtlinearen
Schwingverhaltens dynamischer Strukturen}, publisher={Shaker}, author={Sprock,
Christian}, year={2019} }'
chicago: Sprock, Christian. Zeiteffiziente Messtechnische Analyse Glatt-Nichtlinearen
Schwingverhaltens Dynamischer Strukturen. Shaker, 2019.
ieee: C. Sprock, Zeiteffiziente messtechnische Analyse glatt-nichtlinearen Schwingverhaltens
dynamischer Strukturen. Shaker, 2019.
mla: Sprock, Christian. Zeiteffiziente Messtechnische Analyse Glatt-Nichtlinearen
Schwingverhaltens Dynamischer Strukturen. Shaker, 2019.
short: C. Sprock, Zeiteffiziente Messtechnische Analyse Glatt-Nichtlinearen Schwingverhaltens
Dynamischer Strukturen, Shaker, 2019.
date_created: 2019-05-27T10:33:08Z
date_updated: 2023-09-15T12:25:37Z
department:
- _id: '151'
keyword:
- Schwingungsanalyse
- nichtlineare Strukturdynamik
- Multisinus
- Duffing-Schwinger
- amplitudenabhängige Nichtlinearität
- Peakbending
- Backbone Curve
- Schwingungsmessung
- Frequenzverstimmung
- Autoregression
- Best Linear Approximation
language:
- iso: eng
publisher: Shaker
status: public
title: Zeiteffiziente messtechnische Analyse glatt-nichtlinearen Schwingverhaltens
dynamischer Strukturen
type: dissertation
user_id: '210'
year: '2019'
...
---
_id: '17651'
abstract:
- lang: eng
text: 'Consider mitigating the effects of denial of service or of malicious traffic
in networks by deleting edges. Edge deletion reduces the DoS or the number of
the malicious flows, but it also inadvertently removes some of the desired flows.
To model this important problem, we formulate two problems: (1) remove all the
undesirable flows while minimizing the damage to the desirable ones and (2) balance
removing the undesirable flows and not removing too many of the desirable flows.
We prove these problems are equivalent to important theoretical problems, thereby
being important not only practically but also theoretically, and very hard to
approximate in a general network. We employ reductions to nonetheless approximate
the problem and also provide a greedy approximation. When the network is a tree,
the problems are still MAX SNP-hard, but we provide a greedy-based 2l-approximation
algorithm, where l is the longest desirable flow. We also provide an algorithm,
approximating the first and the second problem within {\$}{\$}2 {\backslash}sqrt{\{}
2{\backslash}left| E {\backslash}right| {\}}{\$}{\$}and {\$}{\$}2 {\backslash}sqrt{\{}2
({\backslash}left| E {\backslash}right| + {\backslash}left| {\backslash}text {\{}undesirable
flows{\}} {\backslash}right| ){\}}{\$}{\$}, respectively, where E is the set of
the edges of the network. We also provide a fixed-parameter tractable (FPT) algorithm.
Finally, if the tree has a root such that every flow in the tree flows on the
path from the root to a leaf, we solve the problem exactly using dynamic programming.'
author:
- first_name: Gleb
full_name: Polevoy, Gleb
id: '83983'
last_name: Polevoy
- first_name: Stojan
full_name: Trajanovski, Stojan
last_name: Trajanovski
- first_name: Paola
full_name: Grosso, Paola
last_name: Grosso
- first_name: Cees
full_name: de Laat, Cees
last_name: de Laat
citation:
ama: 'Polevoy G, Trajanovski S, Grosso P, de Laat C. Removing Undesirable Flows
by Edge Deletion. In: Kim D, Uma RN, Zelikovsky A, eds. Combinatorial Optimization
and Applications. Cham: Springer International Publishing; 2018:217-232.'
apa: 'Polevoy, G., Trajanovski, S., Grosso, P., & de Laat, C. (2018). Removing
Undesirable Flows by Edge Deletion. In D. Kim, R. N. Uma, & A. Zelikovsky
(Eds.), Combinatorial Optimization and Applications (pp. 217–232). Cham:
Springer International Publishing.'
bibtex: '@inproceedings{Polevoy_Trajanovski_Grosso_de Laat_2018, place={Cham}, title={Removing
Undesirable Flows by Edge Deletion}, booktitle={Combinatorial Optimization and
Applications}, publisher={Springer International Publishing}, author={Polevoy,
Gleb and Trajanovski, Stojan and Grosso, Paola and de Laat, Cees}, editor={Kim,
Donghyun and Uma, R. N. and Zelikovsky, AlexanderEditors}, year={2018}, pages={217–232}
}'
chicago: 'Polevoy, Gleb, Stojan Trajanovski, Paola Grosso, and Cees de Laat. “Removing
Undesirable Flows by Edge Deletion.” In Combinatorial Optimization and Applications,
edited by Donghyun Kim, R. N. Uma, and Alexander Zelikovsky, 217–32. Cham: Springer
International Publishing, 2018.'
ieee: G. Polevoy, S. Trajanovski, P. Grosso, and C. de Laat, “Removing Undesirable
Flows by Edge Deletion,” in Combinatorial Optimization and Applications,
2018, pp. 217–232.
mla: Polevoy, Gleb, et al. “Removing Undesirable Flows by Edge Deletion.” Combinatorial
Optimization and Applications, edited by Donghyun Kim et al., Springer International
Publishing, 2018, pp. 217–32.
short: 'G. Polevoy, S. Trajanovski, P. Grosso, C. de Laat, in: D. Kim, R.N. Uma,
A. Zelikovsky (Eds.), Combinatorial Optimization and Applications, Springer International
Publishing, Cham, 2018, pp. 217–232.'
date_created: 2020-08-06T15:19:36Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
editor:
- first_name: Donghyun
full_name: Kim, Donghyun
last_name: Kim
- first_name: R. N.
full_name: Uma, R. N.
last_name: Uma
- first_name: Alexander
full_name: Zelikovsky, Alexander
last_name: Zelikovsky
extern: '1'
keyword:
- flow
- Red-Blue Set Cover
- Positive-Negative Partial Set Cover
- approximation
- tree
- MAX SNP-hard
- root
- leaf
- dynamic programming
- FPT
language:
- iso: eng
page: 217-232
place: Cham
publication: Combinatorial Optimization and Applications
publication_identifier:
isbn:
- 978-3-030-04651-4
publisher: Springer International Publishing
status: public
title: Removing Undesirable Flows by Edge Deletion
type: conference
user_id: '83983'
year: '2018'
...
---
_id: '17652'
author:
- first_name: Gleb
full_name: Polevoy, Gleb
id: '83983'
last_name: Polevoy
- first_name: Stojan
full_name: Trajanovski, Stojan
last_name: Trajanovski
- first_name: Paola
full_name: Grosso, Paola
last_name: Grosso
- first_name: Cees
full_name: de Laat, Cees
last_name: de Laat
citation:
ama: 'Polevoy G, Trajanovski S, Grosso P, de Laat C. Filtering Undesirable Flows
in Networks. In: Combinatorial Optimization and Applications: 11th International
Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part
I. Lecture Notes in Computer Science. Cham: Springer International Publishing;
2017:3-17. doi:10.1007/978-3-319-71150-8_1'
apa: 'Polevoy, G., Trajanovski, S., Grosso, P., & de Laat, C. (2017). Filtering
Undesirable Flows in Networks. In Combinatorial Optimization and Applications:
11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017,
Proceedings, Part I (pp. 3–17). Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-71150-8_1'
bibtex: '@inproceedings{Polevoy_Trajanovski_Grosso_de Laat_2017, place={Cham}, series={Lecture
Notes in Computer Science}, title={Filtering Undesirable Flows in Networks}, DOI={10.1007/978-3-319-71150-8_1},
booktitle={Combinatorial Optimization and Applications: 11th International Conference,
COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I}, publisher={Springer
International Publishing}, author={Polevoy, Gleb and Trajanovski, Stojan and Grosso,
Paola and de Laat, Cees}, year={2017}, pages={3–17}, collection={Lecture Notes
in Computer Science} }'
chicago: 'Polevoy, Gleb, Stojan Trajanovski, Paola Grosso, and Cees de Laat. “Filtering
Undesirable Flows in Networks.” In Combinatorial Optimization and Applications:
11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017,
Proceedings, Part I, 3–17. Lecture Notes in Computer Science. Cham: Springer
International Publishing, 2017. https://doi.org/10.1007/978-3-319-71150-8_1.'
ieee: 'G. Polevoy, S. Trajanovski, P. Grosso, and C. de Laat, “Filtering Undesirable
Flows in Networks,” in Combinatorial Optimization and Applications: 11th International
Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part
I, 2017, pp. 3–17.'
mla: 'Polevoy, Gleb, et al. “Filtering Undesirable Flows in Networks.” Combinatorial
Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai,
China, December 16-18, 2017, Proceedings, Part I, Springer International Publishing,
2017, pp. 3–17, doi:10.1007/978-3-319-71150-8_1.'
short: 'G. Polevoy, S. Trajanovski, P. Grosso, C. de Laat, in: Combinatorial Optimization
and Applications: 11th International Conference, COCOA 2017, Shanghai, China,
December 16-18, 2017, Proceedings, Part I, Springer International Publishing,
Cham, 2017, pp. 3–17.'
date_created: 2020-08-06T15:19:48Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
doi: 10.1007/978-3-319-71150-8_1
extern: '1'
keyword:
- flow
- filter
- MMSA
- set cover
- approximation
- local ratio algorithm
language:
- iso: eng
page: 3-17
place: Cham
publication: 'Combinatorial Optimization and Applications: 11th International Conference,
COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I'
publication_identifier:
isbn:
- 978-3-319-71150-8
publisher: Springer International Publishing
series_title: Lecture Notes in Computer Science
status: public
title: Filtering Undesirable Flows in Networks
type: conference
user_id: '83983'
year: '2017'
...
---
_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: '17657'
abstract:
- lang: eng
text: Inter-datacenter transfers of non-interactive but timely large flows over
a private (managed) network is an important problem faced by many cloud service
providers. The considered flows are non-interactive because they do not explicitly
target the end users. However, most of them must be performed on a timely basis
and are associated with a deadline. We propose to schedule these flows by a centralized
controller, which determines when to transmit each flow and which path to use.
Two scheduling models are presented in this paper. In the first, the controller
also determines the rate of each flow, while in the second bandwidth is assigned
by the network according to the TCP rules. We develop scheduling algorithms for
both models and compare their complexity and performance.
author:
- first_name: R.
full_name: Cohen, R.
last_name: Cohen
- first_name: Gleb
full_name: Polevoy, Gleb
id: '83983'
last_name: Polevoy
citation:
ama: Cohen R, Polevoy G. Inter-Datacenter Scheduling of Large Data Flows. Cloud
Computing, IEEE Transactions on. 2015;PP(99):1-1. doi:10.1109/TCC.2015.2487964
apa: Cohen, R., & Polevoy, G. (2015). Inter-Datacenter Scheduling of Large Data
Flows. Cloud Computing, IEEE Transactions On, PP(99), 1–1. https://doi.org/10.1109/TCC.2015.2487964
bibtex: '@article{Cohen_Polevoy_2015, title={Inter-Datacenter Scheduling of Large
Data Flows}, volume={PP}, DOI={10.1109/TCC.2015.2487964},
number={99}, journal={Cloud Computing, IEEE Transactions on}, author={Cohen, R.
and Polevoy, Gleb}, year={2015}, pages={1–1} }'
chicago: 'Cohen, R., and Gleb Polevoy. “Inter-Datacenter Scheduling of Large Data
Flows.” Cloud Computing, IEEE Transactions On PP, no. 99 (2015): 1–1. https://doi.org/10.1109/TCC.2015.2487964.'
ieee: R. Cohen and G. Polevoy, “Inter-Datacenter Scheduling of Large Data Flows,”
Cloud Computing, IEEE Transactions on, vol. PP, no. 99, pp. 1–1, 2015.
mla: Cohen, R., and Gleb Polevoy. “Inter-Datacenter Scheduling of Large Data Flows.”
Cloud Computing, IEEE Transactions On, vol. PP, no. 99, 2015, pp. 1–1,
doi:10.1109/TCC.2015.2487964.
short: R. Cohen, G. Polevoy, Cloud Computing, IEEE Transactions On PP (2015) 1–1.
date_created: 2020-08-06T15:20:58Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
doi: 10.1109/TCC.2015.2487964
extern: '1'
issue: '99'
keyword:
- Approximation algorithms
- Approximation methods
- Bandwidth
- Cloud computing
- Routing
- Schedules
- Scheduling
language:
- iso: eng
page: 1-1
publication: Cloud Computing, IEEE Transactions on
publication_identifier:
issn:
- 2168-7161
status: public
title: Inter-Datacenter Scheduling of Large Data Flows
type: journal_article
user_id: '83983'
volume: PP
year: '2015'
...
---
_id: '8171'
abstract:
- lang: eng
text: "The polynomial hierarchy plays a central role in classical complexity theory.
Here, we define\r\na quantum generalization of the polynomial hierarchy, and initiate
its study. We show that\r\nnot only are there natural complete problems for the
second level of this quantum hierarchy, but that these problems are in fact hard
to approximate. Using the same techniques, we\r\nalso obtain hardness of approximation
for the class QCMA. Our approach is based on the\r\nuse of dispersers, and is
inspired by the classical results of Umans regarding hardness of approximation
for the second level of the classical polynomial hierarchy [Umans, FOCS 1999].\r\nThe
problems for which we prove hardness of approximation for include, among others,
a\r\nquantum version of the Succinct Set Cover problem, and a variant of the local
Hamiltonian\r\nproblem with hybrid classical-quantum ground states."
article_type: original
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Julia
full_name: Kempe, Julia
last_name: Kempe
citation:
ama: Gharibian S, Kempe J. Hardness of approximation for quantum problems. Quantum
Information & Computation. 2014;14(5-6):517-540.
apa: Gharibian, S., & Kempe, J. (2014). Hardness of approximation for quantum
problems. Quantum Information & Computation, 14(5–6), 517–540.
bibtex: '@article{Gharibian_Kempe_2014, title={Hardness of approximation for quantum
problems}, volume={14}, number={5–6}, journal={Quantum Information & Computation},
author={Gharibian, Sevag and Kempe, Julia}, year={2014}, pages={517–540} }'
chicago: 'Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum
Problems.” Quantum Information & Computation 14, no. 5–6 (2014): 517–40.'
ieee: S. Gharibian and J. Kempe, “Hardness of approximation for quantum problems,”
Quantum Information & Computation, vol. 14, no. 5–6, pp. 517–540, 2014.
mla: Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.”
Quantum Information & Computation, vol. 14, no. 5–6, 2014, pp. 517–40.
short: S. Gharibian, J. Kempe, Quantum Information & Computation 14 (2014) 517–540.
date_created: 2019-03-01T11:56:55Z
date_updated: 2023-02-28T11:02:47Z
department:
- _id: '623'
- _id: '7'
extern: '1'
external_id:
arxiv:
- '1209.1055'
intvolume: ' 14'
issue: 5-6
keyword:
- Hardness of approximation
- polynomial time hierarchy
- succinct set cover
- quantum complexity
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1209.1055
oa: '1'
page: 517-540
publication: Quantum Information & Computation
publication_status: published
status: public
title: Hardness of approximation for quantum problems
type: journal_article
user_id: '71541'
volume: 14
year: '2014'
...
---
_id: '17663'
abstract:
- lang: eng
text: 'In this paper, we define and study a new problem, referred to as the Dependent
Unsplittable Flow Problem (D-UFP). We present and discuss this problem in the
context of large-scale powerful (radar/camera) sensor networks, but we believe
it has important applications on the admission of large flows in other networks
as well. In order to optimize the selection of flows transmitted to the gateway,
D-UFP takes into account possible dependencies between flows. We show that D-UFP
is more difficult than NP-hard problems for which no good approximation is known.
Then, we address two special cases of this problem: the case where all the sensors
have a shared channel and the case where the sensors form a mesh and route to
the gateway over a spanning tree.'
author:
- first_name: R.
full_name: Cohen, R.
last_name: Cohen
- first_name: I.
full_name: Nudelman, I.
last_name: Nudelman
- first_name: Gleb
full_name: Polevoy, Gleb
id: '83983'
last_name: Polevoy
citation:
ama: Cohen R, Nudelman I, Polevoy G. On the Admission of Dependent Flows in Powerful
Sensor Networks. Networking, IEEE/ACM Transactions on. 2013;21(5):1461-1471.
doi:10.1109/TNET.2012.2227792
apa: Cohen, R., Nudelman, I., & Polevoy, G. (2013). On the Admission of Dependent
Flows in Powerful Sensor Networks. Networking, IEEE/ACM Transactions On,
21(5), 1461–1471. https://doi.org/10.1109/TNET.2012.2227792
bibtex: '@article{Cohen_Nudelman_Polevoy_2013, title={On the Admission of Dependent
Flows in Powerful Sensor Networks}, volume={21}, DOI={10.1109/TNET.2012.2227792},
number={5}, journal={Networking, IEEE/ACM Transactions on}, author={Cohen, R.
and Nudelman, I. and Polevoy, Gleb}, year={2013}, pages={1461–1471} }'
chicago: 'Cohen, R., I. Nudelman, and Gleb Polevoy. “On the Admission of Dependent
Flows in Powerful Sensor Networks.” Networking, IEEE/ACM Transactions On
21, no. 5 (2013): 1461–71. https://doi.org/10.1109/TNET.2012.2227792.'
ieee: R. Cohen, I. Nudelman, and G. Polevoy, “On the Admission of Dependent Flows
in Powerful Sensor Networks,” Networking, IEEE/ACM Transactions on, vol.
21, no. 5, pp. 1461–1471, 2013.
mla: Cohen, R., et al. “On the Admission of Dependent Flows in Powerful Sensor Networks.”
Networking, IEEE/ACM Transactions On, vol. 21, no. 5, 2013, pp. 1461–71,
doi:10.1109/TNET.2012.2227792.
short: R. Cohen, I. Nudelman, G. Polevoy, Networking, IEEE/ACM Transactions On 21
(2013) 1461–1471.
date_created: 2020-08-06T15:22:05Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
doi: 10.1109/TNET.2012.2227792
extern: '1'
intvolume: ' 21'
issue: '5'
keyword:
- Approximation algorithms
- Approximation methods
- Bandwidth
- Logic gates
- Radar
- Vectors
- Wireless sensor networks
- Dependent flow scheduling
- sensor networks
language:
- iso: eng
page: 1461-1471
publication: Networking, IEEE/ACM Transactions on
publication_identifier:
issn:
- 1063-6692
status: public
title: On the Admission of Dependent Flows in Powerful Sensor Networks
type: journal_article
user_id: '83983'
volume: 21
year: '2013'
...
---
_id: '46388'
abstract:
- lang: eng
text: Understanding the behaviour of well-known algorithms for classical NP-hard
optimisation problems is still a difficult task. With this paper, we contribute
to this research direction and carry out a feature based comparison of local search
and the well-known Christofides approximation algorithm for the Traveling Salesperson
Problem. We use an evolutionary algorithm approach to construct easy and hard
instances for the Christofides algorithm, where we measure hardness in terms of
approximation ratio. Our results point out important features and lead to hard
and easy instances for this famous algorithm. Furthermore, our cross-comparison
gives new insights on the complementary benefits of the different approaches.
author:
- first_name: Samadhi
full_name: Nallaperuma, Samadhi
last_name: Nallaperuma
- first_name: Markus
full_name: Wagner, Markus
last_name: Wagner
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
- first_name: Bernd
full_name: Bischl, Bernd
last_name: Bischl
- first_name: Olaf
full_name: Mersmann, Olaf
last_name: Mersmann
- first_name: Heike
full_name: Trautmann, Heike
id: '100740'
last_name: Trautmann
orcid: 0000-0002-9788-8282
citation:
ama: 'Nallaperuma S, Wagner M, Neumann F, Bischl B, Mersmann O, Trautmann H. A Feature-Based
Comparison of Local Search and the Christofides Algorithm for the Travelling Salesperson
Problem. In: Proceedings of the Twelfth Workshop on Foundations of Genetic
Algorithms XII. FOGA XII ’13. Association for Computing Machinery; 2013:147–160.
doi:10.1145/2460239.2460253'
apa: Nallaperuma, S., Wagner, M., Neumann, F., Bischl, B., Mersmann, O., & Trautmann,
H. (2013). A Feature-Based Comparison of Local Search and the Christofides Algorithm
for the Travelling Salesperson Problem. Proceedings of the Twelfth Workshop
on Foundations of Genetic Algorithms XII, 147–160. https://doi.org/10.1145/2460239.2460253
bibtex: '@inproceedings{Nallaperuma_Wagner_Neumann_Bischl_Mersmann_Trautmann_2013,
place={New York, NY, USA}, series={FOGA XII ’13}, title={A Feature-Based Comparison
of Local Search and the Christofides Algorithm for the Travelling Salesperson
Problem}, DOI={10.1145/2460239.2460253},
booktitle={Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms
XII}, publisher={Association for Computing Machinery}, author={Nallaperuma, Samadhi
and Wagner, Markus and Neumann, Frank and Bischl, Bernd and Mersmann, Olaf and
Trautmann, Heike}, year={2013}, pages={147–160}, collection={FOGA XII ’13} }'
chicago: 'Nallaperuma, Samadhi, Markus Wagner, Frank Neumann, Bernd Bischl, Olaf
Mersmann, and Heike Trautmann. “A Feature-Based Comparison of Local Search and
the Christofides Algorithm for the Travelling Salesperson Problem.” In Proceedings
of the Twelfth Workshop on Foundations of Genetic Algorithms XII, 147–160.
FOGA XII ’13. New York, NY, USA: Association for Computing Machinery, 2013. https://doi.org/10.1145/2460239.2460253.'
ieee: 'S. Nallaperuma, M. Wagner, F. Neumann, B. Bischl, O. Mersmann, and H. Trautmann,
“A Feature-Based Comparison of Local Search and the Christofides Algorithm for
the Travelling Salesperson Problem,” in Proceedings of the Twelfth Workshop
on Foundations of Genetic Algorithms XII, 2013, pp. 147–160, doi: 10.1145/2460239.2460253.'
mla: Nallaperuma, Samadhi, et al. “A Feature-Based Comparison of Local Search and
the Christofides Algorithm for the Travelling Salesperson Problem.” Proceedings
of the Twelfth Workshop on Foundations of Genetic Algorithms XII, Association
for Computing Machinery, 2013, pp. 147–160, doi:10.1145/2460239.2460253.
short: 'S. Nallaperuma, M. Wagner, F. Neumann, B. Bischl, O. Mersmann, H. Trautmann,
in: Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII,
Association for Computing Machinery, New York, NY, USA, 2013, pp. 147–160.'
date_created: 2023-08-04T15:42:03Z
date_updated: 2023-10-16T13:45:53Z
department:
- _id: '34'
- _id: '819'
doi: 10.1145/2460239.2460253
keyword:
- approximation algorithms
- local search
- traveling salesperson problem
- feature selection
- prediction
- classification
language:
- iso: eng
page: 147–160
place: New York, NY, USA
publication: Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms
XII
publication_identifier:
isbn:
- '9781450319904'
publisher: Association for Computing Machinery
series_title: FOGA XII ’13
status: public
title: A Feature-Based Comparison of Local Search and the Christofides Algorithm for
the Travelling Salesperson Problem
type: conference
user_id: '15504'
year: '2013'
...
---
_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'
...