Search Results

Documents authored by Boehmer, Kimon

Document
DOI: 10.4230/LIPIcs.SWAT.2026.8
Submodular Max-Min Allocation Under Identical Valuations

Authors: Kimon Boehmer

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
In the problem of Submodular Max-Min Allocation, we are given a set of items, a set of players, and monotone submodular valuation functions that represent the satisfaction of a player with a certain subset of items. The goal is to find an allocation of the items to the players that maximizes the lowest satisfaction among all players. We study this problem in the special case where all players have the same valuation function. We devise a greedy algorithm which gives a 0.4-approximation, improving the previously best factor of 10/27 ≈ 0.37 by Uziahu and Feige. Furthermore, we study the integrality gap of the configuration LP when players have identical valuations. By constructing a variable assignment to the dual from a primal integral solution, we give the first constant upper bound on the integrality gap for submodular valuations. Generalizing the result to the case where players' allocations must be independent in k given matroids, we derive a 𝒪(k)-estimation algorithm for max-min allocation subject to k matroid constraints under identical valuations.
Cite as

Kimon Boehmer. Submodular Max-Min Allocation Under Identical Valuations. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{boehmer:LIPIcs.SWAT.2026.8,
  author =	{Boehmer, Kimon},
  title =	{{Submodular Max-Min Allocation Under Identical Valuations}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.8},
  URN =		{urn:nbn:de:0030-drops-260446},
  doi =		{10.4230/LIPIcs.SWAT.2026.8},
  annote =	{Keywords: Submodularity, Approximation algorithms, Allocation, Configuration LP}
}
Artifact
Software
DOI: 10.4230/artifacts.22579
Arcee

Authors: Kimon Boehmer, Lukas Lee George, Fanny Hauser, and Jesse Palarus

Abstract
Cite as

Kimon Boehmer, Lukas Lee George, Fanny Hauser, Jesse Palarus. Arcee (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{Arcee,
   title = {{Arcee}}, 
   author = {Boehmer, Kimon and George, Lukas Lee and Hauser, Fanny and Palarus, Jesse},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:4a1810b816bec954e0780d591b0c79276ac8f285;origin=https://github.com/lucidLuckylee/pace_2024;visit=swh:1:snp:c15056f72ef6b62e3ef8f87b844229391c3a10b8;anchor=swh:1:rev:9269201822ced0770c31bfc3fccb48c45abbfb42}{\texttt{swh:1:dir:4a1810b816bec954e0780d591b0c79276ac8f285}} (visited on 2024-12-05)},
   url = {https://github.com/lucidLuckylee/pace_2024},
   doi = {10.4230/artifacts.22579},
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2024.33
PACE Solver Description: Arcee

Authors: Kimon Boehmer, Lukas Lee George, Fanny Hauser, and Jesse Palarus

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
The 2024 PACE Challenge focused on the One-Sided Crossing Minimization (OCM) problem, which aims to minimize edge crossings in a bipartite graph with a fixed order in one partition and a free order in the other. We describe our OCM solver submission that utilizes various reduction rules for OCM and, for the heuristic track, employs local search approaches as well as techniques to escape local minima. The exact solver uses an ILP formulation and branch & bound to solve an equivalent Feedback Arc Set instance.
Cite as

Kimon Boehmer, Lukas Lee George, Fanny Hauser, and Jesse Palarus. PACE Solver Description: Arcee. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 33:1-33:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boehmer_et_al:LIPIcs.IPEC.2024.33,
  author =	{Boehmer, Kimon and George, Lukas Lee and Hauser, Fanny and Palarus, Jesse},
  title =	{{PACE Solver Description: Arcee}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{33:1--33:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.33},
  URN =		{urn:nbn:de:0030-drops-222595},
  doi =		{10.4230/LIPIcs.IPEC.2024.33},
  annote =	{Keywords: PACE 2024, One-Sided Crossing Minimization, OCM}
}
Document
DOI: 10.4230/LIPIcs.WABI.2024.18
RNA Triplet Repeats: Improved Algorithms for Structure Prediction and Interactions

Authors: Kimon Boehmer, Sarah J. Berkemer, Sebastian Will, and Yann Ponty

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
RNAs composed of Triplet Repeats (TR) have recently attracted much attention in the field of synthetic biology. We study the mimimum free energy (MFE) secondary structures of such RNAs and give improved algorithms to compute the MFE and the partition function. Furthermore, we study the interaction of multiple RNAs and design a new algorithm for computing MFE and partition function for RNA-RNA interactions, improving the previously known factorial running time to exponential. In the case of TR, we show computational hardness but still obtain a parameterized algorithm. Finally, we propose a polynomial-time algorithm for computing interactions from a base set of RNA strands and conduct experiments on the interaction of TR based on this algorithm. For instance, we study the probability that a base pair is formed between two strands with the same triplet pattern, allowing an assessment of a notion of orthogonality between TR.
Cite as

Kimon Boehmer, Sarah J. Berkemer, Sebastian Will, and Yann Ponty. RNA Triplet Repeats: Improved Algorithms for Structure Prediction and Interactions. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boehmer_et_al:LIPIcs.WABI.2024.18,
  author =	{Boehmer, Kimon and Berkemer, Sarah J. and Will, Sebastian and Ponty, Yann},
  title =	{{RNA Triplet Repeats: Improved Algorithms for Structure Prediction and Interactions}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{18:1--18:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.18},
  URN =		{urn:nbn:de:0030-drops-206625},
  doi =		{10.4230/LIPIcs.WABI.2024.18},
  annote =	{Keywords: RNA folding, RNA interactions, triplet repeats, dynamic programming, NP-hardness}
}
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