20.03.2025

Two Papers accepted at EvoCOP and CIAC

We are proud to announce to accepted papers: Aishwarya Radhakrishnan and Timo Kötzing wrote Mixed-Binary Problems Optimized with Fast Discrete Solver for the European Conference on Evolutionary Computation in Combinatorial Optimisation (EvoCOP) on 23-25 April in Trieste, Italy. In the paper, the authors combine Population-Based Incremental Learning (PBIL) for discrete optimization algorithm with the Covariance Matrix Adaptation Evolutionary Strategy (CMA-ES) to address the continuous part of a mixed-integer problem. They compare CMA-ES-PBIL with two leading variants of CMA-ES from the literature: CMA-ES with Margin (CMA-ESwM) and CMA-ES with Probability Distribution Model (CMA-ES-PDM). They also conduct run time analysis on some separable and a non-separable benchmark functions and show that their hybrid algorithm significantly outperforms both CMA-ESwM and CMA-ES-PDM.

The second paper Network Creation Games with 2-Neighborhood Maximization was written for the International Conference on Algorithms and Complexity (CIAC) on 10-12 June in Rome, Italy by Merlin de la Haye and Pascal Lenzner with co-authors from Bremen. In social networks, individuals benefit the most from their friends, and contacts where friends can act as direct intermediaries. Only seldomly you interact with strangers, i.e. persons three or more connections apart. In our paper we analyse a game theoretic model where agents what to maximize their two-neighbourhood, i.e. the group of direct neighbours and their neighbours, by building costly edges. We provide insights into structural properties and quality of equilibria, and show tight constant bounds on the diameter of these networks.

Clean Citation Style 005

{ "authors" : [{ "lastname":"Bläsius" , "initial":"T" , "url":"https://hpi.de/friedrich/publications/people/thomas-blaesius.html" , "mail":"thomas.blasius(at)hpi.de" }, { "lastname":"Casel" , "initial":"K" , "url":"https://hpi.de/friedrich/publications/people/katrin-casel.html" , "mail":"katrin.casel(at)hpi.de" }, { "lastname":"Chauhan" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/ankit-chauhan.html" , "mail":"ankit.chauhan(at)hpi.de" }, { "lastname":"Cohen" , "initial":"S" , "url":"https://hpi.de/friedrich/publications/people/sarel-cohen.html" , "mail":"sarel.cohen(at)hpi.de" }, { "lastname":"Cseh" , "initial":"�" , "url":"https://hpi.de/friedrich/publications/people/agnes-cseh.html" , "mail":"agnes.cseh(at)hpi.de" }, { "lastname":"Doskoč" , "initial":"V" , "url":"https://hpi.de/friedrich/publications/people/vanja-doskoc.html" , "mail":"vanja.doskoc(at)hpi.de" }, { "lastname":"Elijazyfer" , "initial":"Z" , "url":"https://hpi.de/friedrich/people/ziena-elijazyfer.html" , "mail":"ziena.elijazyfer(at)hpi.de" }, { "lastname":"Fischbeck" , "initial":"P" , "url":"https://hpi.de/friedrich/publications/people/philipp-fischbeck.html" , "mail":"philipp.fischbeck(at)hpi.de" }, { "lastname":"Friedrich" , "initial":"T" , "url":"https://hpi.de/friedrich/publications/people/tobias-friedrich.html" , "mail":"friedrich(at)hpi.de" }, { "lastname":"Göbel" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/andreas-goebel.html" , "mail":"andreas.goebel(at)hpi.de" }, { "lastname":"Issac" , "initial":"D" , "url":"https://hpi.de/friedrich/publications/people/davis-issac.html" , "mail":"davis.issac(at)hpi.de" }, { "lastname":"Katzmann" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/maximilian-katzmann.html" , "mail":"maximilian.katzmann(at)hpi.de" }, { "lastname":"Khazraei" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/ardalan-khazraei.html" , "mail":"ardalan.khazraei(at)hpi.de" }, { "lastname":"Kötzing" , "initial":"T" , "url":"https://hpi.de/friedrich/publications/people/timo-koetzing.html" , "mail":"timo.koetzing(at)hpi.de" }, { "lastname":"Krejca" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/martin-krejca.html" , "mail":"martin.krejca(at)hpi.de" }, { "lastname":"Krogmann" , "initial":"S" , "url":"https://hpi.de/friedrich/publications/people/simon-krogmann.html" , "mail":"simon.krogmann(at)hpi.de" }, { "lastname":"Krohmer" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/anton-krohmer.html" , "mail":"none" }, { "lastname":"Kumar" , "initial":"N" , "url":"https://hpi.de/friedrich/publications/people/nikhil-kumar.html" , "mail":"nikhil.kumar(at)hpi.de" }, { "lastname":"Lagodzinski" , "initial":"G" , "url":"https://hpi.de/friedrich/publications/people/gregor-lagodzinski.html" , "mail":"gregor.lagodzinski(at)hpi.de" }, { "lastname":"Lenzner" , "initial":"P" , "url":"https://hpi.de/friedrich/publications/people/pascal-lenzner.html" , "mail":"pascal.lenzner(at)hpi.de" }, { "lastname":"Melnichenko" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/anna-melnichenko.html" , "mail":"anna.melnichenko(at)hpi.de" }, { "lastname":"Molitor" , "initial":"L" , "url":"https://hpi.de/friedrich/publications/people/louise-molitor.html" , "mail":"louise.molitor(at)hpi.de" }, { "lastname":"Neubert" , "initial":"S" , "url":"https://hpi.de/friedrich/publications/people/stefan-neubert.html" , "mail":"stefan.neubert(at)hpi.de" }, { "lastname":"Pappik" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/marcus-pappik.html" , "mail":"marcus.pappik(at)hpi.de" }, { "lastname":"Quinzan" , "initial":"F" , "url":"https://hpi.de/friedrich/publications/people/francesco-quinzan.html" , "mail":"francesco.quinzan(at)hpi.de" }, { "lastname":"Rizzo" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/manuel-rizzo.html" , "mail":"manuel.rizzo(at)hpi.de" }, { "lastname":"Rothenberger" , "initial":"R" , "url":"https://hpi.de/friedrich/publications/people/ralf-rothenberger.html" , "mail":"ralf.rothenberger(at)hpi.de" }, { "lastname":"Schirneck" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/martin-schirneck.html" , "mail":"martin.schirneck(at)hpi.de" }, { "lastname":"Seidel" , "initial":"K" , "url":"https://hpi.de/friedrich/publications/people/karen-seidel.html" , "mail":"karen.seidel(at)hpi.de" }, { "lastname":"Sutton" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/andrew-m-sutton.html" , "mail":"none" }, { "lastname":"Weyand" , "initial":"C" , "url":"https://hpi.de/friedrich/publications/people/christopher-weyand.html" , "mail":"none" }]}

Clean Citation Style 005

de la Haye, Merlin; Lenzner, Pascal; Schmand‎, Daniel; Schröder‎, Nicole Network Creation Games with 2-Neighborhood MaximizationInternational Conference on Algorithms and Complexity (CIAC) 2025: 18–34

[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]

@inproceedings{dlHLSS2025-NCGTwoNeighborhood,
  abstract = {Network creation games are well-established for investigating the decentralized formation of communication networks, like the Internet or social networks. In these games, selfish agents that correspond to network nodes strategically create costly edges to maximize their centrality in the formed network. We depart from this by focusing on the simpler objective of maximizing the 2-neighborhood. This seems natural for social networks, as an agent's connection benefit is typically provided by her neighbors and their neighbors but not by strangers further away. For this natural model, we study the existence, the structure and the quality both of Nash equilibria (NE) and greedy equilibria (GE). We give structural results on the existence of degree-2 paths and cycles, and we provide tight constant bounds on the diameter. In contrast to most previous network creation game research, our bounds on the diameter are independent of edge cost \(\alpha\) and the number of agents \(n\). Also, bounding the diameter does not imply bounding the price of anarchy, which calls for other methods. Using them, we obtain non-trivial bounds on the price of anarchy, including a \(\Omega\left(\log\left(\frac{n}{\alpha}\right)\right)\) lower bound for NE, and a tight linear bound for GE for low \(\alpha\). Keywords: Network Creation Games, Social Networks, Structure of Equilibria, Price of Anarchy, Diameter, Network Density},
  author = {de la Haye, Merlin and Lenzner, Pascal and Schmand‎, Daniel and Schröder‎, Nicole},
  booktitle = {International Conference on Algorithms and Complexity (CIAC)},
  editor = {Finocchi, Irene and Georgiadis, Loukas},
  keywords = {CIAC danielschmand merlindelahaye nicoleschroeder pascallenzner year2025},
  pages = {18&ndash;34},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {Network Creation Games with 2-Neighborhood Maximization},
  volume = 15680,
  year = 2025
}