2 Search Results for "Andersen, Frank-Uwe"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.49
Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game

Authors: Antares Chen, Lorenzo Orecchia, and Erasmo Tani

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Despite there being significant work on developing spectral- [Chan et al., 2018; Lau et al., 2023; Kwok et al., 2022], and metric-embedding-based [Louis and Makarychev, 2016] approximation algorithms for hypergraph conductance, little is known regarding the approximability of other hypergraph partitioning objectives. This work proposes algorithms for a general model of hypergraph partitioning that unifies both undirected and directed versions of many well-studied partitioning objectives. The first contribution of this paper introduces polymatroidal cut functions, a large class of cut functions amenable to approximation algorithms via metric embeddings and routing multicommodity flows. We demonstrate a simple O(√{log n})-approximation, where n is the number of vertices in the hypergraph, for these problems by rounding relaxations to metrics of negative-type. The second contribution of this paper generalizes the cut-matching game framework of Khandekar et al. [Khandekar et al., 2007] to tackle polymatroidal cut functions. This yields an almost-linear time O(log n)-approximation algorithm for standard versions of undirected and directed hypergraph partitioning [Kwok et al., 2022]. A technical contribution of our construction is a novel cut-matching game, which greatly relaxes the set of allowed actions by the cut player and allows for the use of approximate s-t maximum flows by the matching player. We believe this to be of independent interest.
Cite as

Antares Chen, Lorenzo Orecchia, and Erasmo Tani. Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2025.49,
  author =	{Chen, Antares and Orecchia, Lorenzo and Tani, Erasmo},
  title =	{{Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.49},
  URN =		{urn:nbn:de:0030-drops-234261},
  doi =		{10.4230/LIPIcs.ICALP.2025.49},
  annote =	{Keywords: Hypergraph Partitioning, Cut Improvement, Cut-Matching Game}
}
Document
DOI: 10.4230/DagSemProc.04411.20
Simulative Performance Evaluation of a Mobile Peer-to-Peer File-Sharing System

Authors: Kurt Tutschku, Tobias Hoßfeld, Hermann de Meer, Jens Oberender, and Frank-Uwe Andersen

Published in: Dagstuhl Seminar Proceedings, Volume 4411, Service Management and Self-Organization in IP-based Networks (2005)

Abstract
Peer-to-Peer (P2P) file-sharing has become the killer application in the wired Internet and might also be highly attractive for mobile networks. In particular since UMTS operators are searching for new applications which do both: a) exploit the potential of the UMTS technology and b) motivate the user to adopt the new technology. In this work we are investigating the performance of an eDonkey-based mobile P2P file-sharing system by means of time-dynamic simulation. Mobile networks differ from wireline networks by the limited capacity of the radio link and the mobility of the users. P2P networks, in contrast, are overlays which consider the transport network in an abstract way. In a mobile environment, the question arises, whether the abstraction can be maintained and what will be the performance impact if there is any. We will show in detail how the mobile access technology (GPRS or UMTS), the churn behavior of mobile users, the file size of mobile specific content, and special infrastructure entities, such as a cache peer, influences the performance of the suggested mobile P2P file-sharing service.
Cite as

Kurt Tutschku, Tobias Hoßfeld, Hermann de Meer, Jens Oberender, and Frank-Uwe Andersen. Simulative Performance Evaluation of a Mobile Peer-to-Peer File-Sharing System. In Service Management and Self-Organization in IP-based Networks. Dagstuhl Seminar Proceedings, Volume 4411, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{tutschku_et_al:DagSemProc.04411.20,
  author =	{Tutschku, Kurt and Ho{\ss}feld, Tobias and Meer, Hermann de and Oberender, Jens and Andersen, Frank-Uwe},
  title =	{{Simulative Performance Evaluation of a Mobile Peer-to-Peer File-Sharing System}},
  booktitle =	{Service Management and Self-Organization in IP-based Networks},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4411},
  editor =	{Matthias Bossardt and Georg Carle and D. Hutchison and Hermann de Meer and Bernhard Plattner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04411.20},
  URN =		{urn:nbn:de:0030-drops-999},
  doi =		{10.4230/DagSemProc.04411.20},
  annote =	{Keywords: peer-to-peer , UMTS , performance evaluation , file-sharing}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2005

  • Refine by Author
  • 1 Andersen, Frank-Uwe
  • 1 Chen, Antares
  • 1 Hoßfeld, Tobias
  • 1 Meer, Hermann de
  • 1 Oberender, Jens
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Theory of computation → Facility location and clustering

  • Refine by Keyword
  • 1 Cut Improvement
  • 1 Cut-Matching Game
  • 1 Hypergraph Partitioning
  • 1 UMTS
  • 1 file-sharing
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact