Lauerbach, Antonio - Lehrstuhl für Informatik I

Antonio Lauerbach

Lehrstuhl für Informatik I
Universität Würzburg
Am Hubland

97074 Würzburg

Deutschland

Gebäude: M4

Raum: 01.003

Telefon: +49 931 31-80071

E-Mail: antonio.lauerbach@uni-wuerzburg.de

ORCID: https://orcid.org/0009-0007-9093-3443

Forschungsinteressen

Graphentheorie
Komplexität

Lehre

Wintersemester 2025/26:

Übungen zu Approximationsalgorithmen

Hiwi

SS25: Algorithmische Graphentheorie
WS24/25: Algorithmen & Datenstrukturen
SS24: Graphen und diskrete Optimierung
WS23/24: Algorithmen & Datenstrukturen
SS23: Theoretische Informatik
WS22/23: Algorithmen & Datenstrukturen
SS22: Algorithmische Graphentheorie
WS21/22: Algorithmen & Datenstrukturen

Veröffentlichungen

de-DE

<?xml version="1.0" encoding="UTF-8"?>
<style xmlns="http://purl.org/net/xbiblio/csl" class="in-text" version="1.0" demote-non-dropping-particle="sort-only"
       default-locale="en-US">
    <info>
        <title>BibSonomy – The BibSonomy default CSL style (edited for Wolff)</title>
        <id>http://www.bibsonomy.org/styles/everyAwareWolff.csl</id>
        <link href="http://www.bibsonomy.org/styles/everyAwareWolff.csl" rel="self"/>
        <author>
            <name>Sebastian Böttger</name>
            <email>boettger@cs.uni-kassel.de</email>
        </author>
        <author>
            <name>Andreas Hotho</name>
            <email>hotho@cs.uni-kassel.de</email>
        </author>
        <category citation-format="author-date"/>
        <updated>2014-03-03T14:18:10+00:00</updated>
        <rights license="http://creativecommons.org/licenses/by-sa/3.0/">This work is licensed under a Creative Commons
            Attribution-ShareAlike 3.0 License
        </rights>
    </info>

    <locale xml:lang="en">
        <terms>
            <term name="of">of</term>
        </terms>
    </locale>

    <locale xml:lang="de">
        <terms>
            <term name="of">von</term>
        </terms>
    </locale>

    <macro name="container-contributors">
        <choose>
            <if type="chapter paper-conference" match="any">
                <names variable="editor translator" delimiter=", " suffix="">
                    <name initialize-with=". "/>
                    <label form="short" prefix=" (" suffix=".)" strip-periods="true"/>
                </names>
            </if>
        </choose>
    </macro>

    <macro name="secondary-contributors">
        <choose>
            <if type="chapter paper-conference thesis" match="none">
                <names variable="editor translator" delimiter=", " suffix="">
                    <name delimiter="; " delimiter-precedes-last="always" initialize-with=". "/>
                    <label form="short" prefix=" (" suffix=".)" strip-periods="true"/>
                </names>
            </if>
        </choose>
        <choose>
            <if type="thesis" match="any">
                <text variable="genre"/>
            </if>
        </choose>
    </macro>

    <macro name="author">
        <names variable="author">
            <name name-as-sort-order="none" and="text" sort-separator=" " delimiter=", " delimiter-precedes-last="never">
                <name-part name="given"/>
                <name-part name="family"/>
            </name>
            <substitute>
                <names variable="translator"/>
                <names variable="editor"/>
            </substitute>
        </names>
    </macro>

    <macro name="author-short">
        <names variable="author">
            <name form="short" delimiter=", " initialize-with=". "/>
            <substitute>
                <names variable="editor"/>
                <names variable="translator"/>
                <choose>
                    <if type="bill book graphic legal_case legislation motion_picture report song" match="any">
                        <text variable="title" form="short" font-style="italic"/>
                    </if>
                    <else>
                        <text variable="title" form="short"/>
                    </else>
                </choose>
            </substitute>
        </names>
    </macro>

    <macro name="access">
        <choose>
            <if type="thesis">
                <choose>
                    <if variable="archive">
                        <group>
                            <text term="retrieved" text-case="capitalize-first" suffix=" "/>
                            <text term="from" suffix=" "/>
                            <text variable="archive" suffix="."/>
                            <text variable="archive_location" prefix=" (" suffix=")"/>
                        </group>
                    </if>
                    <else>
                        <group>
                            <text term="retrieved" text-case="capitalize-first" suffix=" "/>
                            <text term="from" suffix=" "/>
                            <text variable="URL"/>
                        </group>
                    </else>
                </choose>
            </if>
            <else>
                <choose>
                    <if variable="DOI">
                        <text variable="DOI" prefix="doi:"/>
                    </if>
                    <else>
                        <choose>
                            <if type="webpage">
                                <group>
                                    <text term="retrieved" text-case="capitalize-first" suffix=" "/>
                                    <date variable="accessed" suffix=", ">
                                        <date-part name="month" suffix=" "/>
                                        <date-part name="day" suffix=", "/>
                                        <date-part name="year"/>
                                    </date>
                                    <group>
                                        <text term="from" suffix=" "/>
                                        <text variable="URL"/>
                                    </group>
                                </group>
                            </if>
                            <else>
                                <group>
                                    <text term="retrieved" text-case="capitalize-first" suffix=" "/>
                                    <text term="from" suffix=" "/>
                                    <text variable="URL"/>
                                </group>
                            </else>
                        </choose>
                    </else>
                </choose>
            </else>
        </choose>
    </macro>

    <macro name="title">
        <choose>
            <if type="report thesis" match="any">
                <text variable="title" font-style="italic"/>
                <group prefix=". Technical Report (" suffix="), ">
                    <text variable="genre"/>
                    <text variable="number" form="long"/>
                </group>
            </if>
            <else-if type="bill book graphic legal_case legislation manuscript motion_picture report song speech" match="any">
                <text variable="title" font-style="italic"/>
            </else-if>
            <else>
                <text variable="title" form="long" suffix="."/>
            </else>
        </choose>
    </macro>

    <macro name="publisher">
        <choose>
            <if type="report thesis" match="any">
                <group delimiter=", " suffix=".">
                    <text variable="publisher" form="long"/>
                    <text variable="publisher-place"/>
                </group>
            </if>
            <else>
                <choose>
                    <if variable="event" match="none">
                        <text variable="genre" suffix=", "/>
                    </if>
                </choose>
                <group delimiter=": ">
                    <text variable="publisher-place"/>
                    <text variable="publisher"/>
                </group>
            </else>
        </choose>
    </macro>

    <macro name="event">
        <choose>
            <if variable="event">
                <choose>
                    <if variable="genre" match="none">
                        <text variable="event" form="long" suffix=". "/>
                    </if>
                    <else>
                        <group delimiter=" " suffix=". ">
                            <text variable="genre" text-case="capitalize-first"/>
                            <text variable="event"/>
                        </group>
                    </else>
                </choose>
            </if>
        </choose>
    </macro>

    <macro name="issued">
        <choose>
            <if variable="issued">
                <group>
                    <date variable="issued">
                        <date-part name="year"/>
                    </date>
                    <choose>
                        <if type="article-journal bill book chapter graphic legal_case legislation motion_picture paper-conference report song" match="none">
                            <date variable="issued">
                                <date-part prefix=", " name="month"/>
                                <date-part prefix=" " name="day"/>
                            </date>
                        </if>
                    </choose>
                </group>
            </if>
            <else>
                <text term="no date" form="short"/>
            </else>
        </choose>
    </macro>

    <macro name="issued-year">
        <choose>
            <if variable="issued">
                <date variable="issued">
                    <date-part name="year"/>
                </date>
            </if>
            <else>
                <text term="no date" form="short"/>
            </else>
        </choose>
    </macro>

    <macro name="edition">
        <choose>
            <if is-numeric="edition">
                <group delimiter=" ">
                    <number variable="edition" form="ordinal"/>
                    <text term="edition" form="short" plural="false" strip-periods="true"/>
                </group>
            </if>
            <else>
                <text variable="edition" suffix=", "/>
            </else>
        </choose>
    </macro>

    <macro name="locators">
        <choose>
            <if type="article-journal article-magazine article-newspaper" match="any">
                <group delimiter="" prefix=" ">
                    <text variable="volume" form="long"/>
                    <text variable="issue" form="long" prefix="(" suffix=")"/>
                </group>
            </if>
            <else-if type="bill book chapter graphic legal_case legislation motion_picture paper-conference report song" match="any">
                <group delimiter=", ">
                    <text macro="edition"/>
                    <group>
                        <text term="volume" form="short" plural="true" text-case="capitalize-first" suffix=". "
                              strip-periods="true"/>
                        <number variable="number-of-volumes" form="numeric" prefix="1-"/>
                    </group>
                    <group>
                        <text term="volume" form="short" text-case="capitalize-first" suffix=". " strip-periods="true"/>
                        <number variable="volume" form="numeric"/>
                    </group>
                </group>
            </else-if>
        </choose>
    </macro>

    <macro name="citation-locator">
        <group>
            <label variable="locator" form="short"/>
            <text variable="locator" prefix=" "/>
        </group>
    </macro>

    <macro name="page">
        <choose>
            <if variable="page">
                <label variable="page" form="short" suffix=" "/>
                <text variable="page" form="long"/>
            </if>
        </choose>
    </macro>

    <macro name="locators-collection">
        <text macro="locators"/>

        <choose>
            <if variable="collection-title">
                <choose>
                    <if type="book paper-conference" match="any">
                        <text term="of" prefix=" " suffix=" "/>
                        <text variable="collection-title" font-style="italic"/>
                    </if>
                </choose>
            </if>
        </choose>
    </macro>

    <macro name="collection">
        <choose>
            <if type="chapter article-magazine article-newspaper entry-encyclopedia entry paper-conference book" match="any">
                <choose>
                    <if variable="container-title">
                        <text term="in" text-case="capitalize-first" suffix=" "/>
                    </if>
                </choose>
            </if>
        </choose>
        
        <group delimiter=", ">
            <choose>
                <if type="chapter article-magazine article-newspaper article-journal entry-encyclopedia entry paper-conference" match="any">
                    <text variable="container-title" font-style="italic"/>
                </if>
            </choose>
            
            <text macro="locators-collection"/>
        </group>
    </macro>

    <citation et-al-min="3" et-al-use-first="1" disambiguate-add-year-suffix="true" disambiguate-add-names="true"
              disambiguate-add-givenname="true" givenname-disambiguation-rule="by-cite" collapse="year">
        <sort>
            <key macro="author"/>
            <key macro="issued-year"/>
            <key variable="page"/>
        </sort>
        <layout prefix="(" suffix=")" delimiter="; ">
            <group delimiter="">
                <text macro="author-short"/>
                <text macro="issued-year" prefix=" "/>
                <text macro="citation-locator"/>
            </group>
        </layout>
    </citation>

    <bibliography entry-spacing="1" line-spacing="1" hanging-indent="false">
        <sort>
            <key macro="author"/>
            <key macro="issued-year" sort="ascending"/>
        </sort>
        
        <layout>
            <group>
                <group delimiter=". " suffix=". ">
                    <text macro="title"/>
                    <text macro="author"/>
                    
                    <group delimiter=", ">
                        <text macro="collection"/>
                        <text macro="container-contributors"/>
                        <text macro="secondary-contributors"/>
                        <text macro="event"/>
                        <text macro="page"/>
                    </group>
                </group>
                
                <group delimiter=", " suffix=". ">
                    <text variable="publisher" form="long"/>
                    <text variable="publisher-place" form="long"/>
                    <text macro="issued"/>
                </group>
            </group>
        </layout>
    </bibliography>
</style>

2025[ to top ]

The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem. Antonio Lauerbach, Kendra Reiter und Marie Schmidt. In SOFSEM 2025: Theory and Practice of Computer Science, Bd. 15539 von Lecture Notes in Computer Science, R. Královič, V. Kůrková (Hrsg.), S. 85–98. Springer Nature Switzerland, Cham, 2025.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
Dial-a-Ride problems have been proposed to model the challenge to consolidate passenger transportation requests with a fleet of shared vehicles. The line-based Dial-a-Ride Problem (liDARP) is a variant where the passengers are transported along a fixed sequence of stops, with the option of taking shortcuts. In this paper we consider the liDARP with the objective function to maximize the number of transported requests. We investigate the complexity of two optimization problems: the liDARP, and the problem to determine the minimum number of turns needed in an optimal liDARP solution, called the MinTurn problem. Based on a number of instance parameters and characteristics, we are able to state the boundary between polynomially solvable and NP-hard instances for both problems. Furthermore, we provide parameterized algorithms that are able to solve both the liDARP and MinTurn problem.

@inproceedings{LauerbachRS25CountTurnsLiDARP, abstract = {Dial-a-Ride problems have been proposed to model the challenge to consolidate passenger transportation requests with a fleet of shared vehicles. The line-based Dial-a-Ride Problem (liDARP) is a variant where the passengers are transported along a fixed sequence of stops, with the option of taking shortcuts. In this paper we consider the liDARP with the objective function to maximize the number of transported requests. We investigate the complexity of two optimization problems: the liDARP, and the problem to determine the minimum number of turns needed in an optimal liDARP solution, called the MinTurn problem. Based on a number of instance parameters and characteristics, we are able to state the boundary between polynomially solvable and NP-hard instances for both problems. Furthermore, we provide parameterized algorithms that are able to solve both the liDARP and MinTurn problem.}, address = {Cham}, author = {Lauerbach, Antonio and Reiter, Kendra and Schmidt, Marie}, booktitle = {SOFSEM 2025: Theory and Practice of Computer Science}, editor = {Královič, Rastislav and Kůrková, Vera}, keywords = {myown}, pages = {85–98}, publisher = {Springer Nature Switzerland}, series = {Lecture Notes in Computer Science}, title = {The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem}, type = {Publication}, volume = 15539, year = 2025 }
Eliminating Majority Illusion. Foivos Fioravantes, Abhiruk Lahiri, Antonio Lauerbach, Lluís Sabater, Marie Diana Sieper und Samuel Wolf. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, von AAMAS ’25, S. 749–757. International Foundation for Autonomous Agents and Multiagent Systems, Detroit, MI, USA, 2025.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
- [ arxiv ]
An opinion illusion refers to a phenomenon in social networks where agents may witness distributions of opinions among their neighbours that do not accurately reflect the true distribution of opinions in the population as a whole. A specific case of this occurs when there are only two possible choices, such as whether to receive the COVID-19 vaccine or vote on EU membership, which is commonly referred to as a majority illusion. In this work, we study the topological properties of social networks that lead to opinion illusions and focus on minimizing the number of agents that need to be influenced to eliminate these illusions. To do so, we propose an initial, but systematic study of the algorithmic behaviour of this problem.We show that the problem is NP-hard even for underlying topologies that are rather restrictive, being planar and of bounded diameter. We then look for exact algorithms that scale well as the input grows (FPT). We argue the in-existence of such algorithms even when the number of vertices that must be influenced is bounded, or when the social network is arranged in a ''path-like'' fashion (has bounded pathwidth). On the positive side, we present an FPT algorithm for networks with a ''star-like'' structure (bounded vertex cover number). Finally, we construct an FPT algorithm for ''tree-like'' networks (bounded treewidth) when the number of vertices that must be influenced is bounded. This algorithm is then used to provide a PTAS for planar graphs.

@inproceedings{FioravantesLLSSW25ElimMajorityIllusion, abstract = {An opinion illusion refers to a phenomenon in social networks where agents may witness distributions of opinions among their neighbours that do not accurately reflect the true distribution of opinions in the population as a whole. A specific case of this occurs when there are only two possible choices, such as whether to receive the COVID-19 vaccine or vote on EU membership, which is commonly referred to as a majority illusion. In this work, we study the topological properties of social networks that lead to opinion illusions and focus on minimizing the number of agents that need to be influenced to eliminate these illusions. To do so, we propose an initial, but systematic study of the algorithmic behaviour of this problem.We show that the problem is NP-hard even for underlying topologies that are rather restrictive, being planar and of bounded diameter. We then look for exact algorithms that scale well as the input grows (FPT). We argue the in-existence of such algorithms even when the number of vertices that must be influenced is bounded, or when the social network is arranged in a ''path-like'' fashion (has bounded pathwidth). On the positive side, we present an FPT algorithm for networks with a ''star-like'' structure (bounded vertex cover number). Finally, we construct an FPT algorithm for ''tree-like'' networks (bounded treewidth) when the number of vertices that must be influenced is bounded. This algorithm is then used to provide a PTAS for planar graphs.}, address = {Richland, SC}, author = {Fioravantes, Foivos and Lahiri, Abhiruk and Lauerbach, Antonio and Sabater, Lluís and Sieper, Marie Diana and Wolf, Samuel}, booktitle = {Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems}, keywords = {networks}, pages = {749–757}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, series = {AAMAS '25}, title = {Eliminating Majority Illusion}, year = 2025 }

Antonio Lauerbach

Hiwi

Bildnachweise