LIVIVO - The Search Portal for Life Sciences

zur deutschen Oberfläche wechseln
Advanced search

Search results

Result 1 - 10 of total 12

Search options

  1. Book ; Online: A Simple 1.5-Approximation Algorithm for a Wide Range of Max-SMTI Problems

    Csáji, Gergely

    2023  

    Abstract: We give a simple approximation algorithm for a common generalization of many previously studied extensions of the stable matching problem with ties. These generalizations include the existence of critical vertices in the graph, amongst whom we must match ...

    Abstract We give a simple approximation algorithm for a common generalization of many previously studied extensions of the stable matching problem with ties. These generalizations include the existence of critical vertices in the graph, amongst whom we must match as much as possible, free edges, that cannot be blocking edges and $\Delta$-stabilities, which mean that for an edge to block, the improvement should be large enough on one or both sides. We also introduce other notions to generalize these even further, which allows our framework to capture many existing and future applications. We show that our edge duplicating technique allows us to treat these different types of generalizations simultaneously, while also making the algorithm, the proofs and the analysis much simpler and shorter then in previous approaches. In particular, we answer an open question by Askalidis et al. (2013) about the existence of a $\frac{3}{2}$-approximation algorithm for the Max-SMTI problem with free edges. This demonstrates well that this technique can grasp the underlying essence of these problems quite well and have the potential to be able to solve countless future applications as well.
    Keywords Computer Science - Data Structures and Algorithms ; Computer Science - Discrete Mathematics ; Computer Science - Computer Science and Game Theory ; Computer Science - Multiagent Systems
    Subject code 005
    Publishing date 2023-04-05
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  2. Book ; Online: Weakly-Popular and Super-Popular Matchings with Ties and Their Connection to Stable Matchings

    Csáji, Gergely

    2023  

    Abstract: In this paper, we study a slightly different definition of popularity in bipartite graphs $G=(U,W,E)$ with two-sided preferences, when ties are present in the preference lists. This is motivated by the observation that if an agent $u$ is indifferent ... ...

    Abstract In this paper, we study a slightly different definition of popularity in bipartite graphs $G=(U,W,E)$ with two-sided preferences, when ties are present in the preference lists. This is motivated by the observation that if an agent $u$ is indifferent between his original partner $w$ in matching $M$ and his new partner $w'\ne w$ in matching $N$, then he may probably still prefer to stay with his original partner, as change requires effort, so he votes for $M$ in this case, instead of being indifferent. We show that this alternative definition of popularity, which we call weak-popularity allows us to guarantee the existence of such a matching and also to find a weakly-popular matching in polynomial-time that has size at least $\frac{3}{4}$ the size of the maximum weakly popular matching. We also show that this matching is at least $\frac{4}{5}$ times the size of the maximum (weakly) stable matching, so may provide a more desirable solution than the current best (and tight under certain assumptions) $\frac{2}{3}$-approximation for such a stable matching. We also show that unfortunately, finding a maximum size weakly popular matching is NP-hard, even with one-sided ties and that assuming some complexity theoretic assumptions, the $\frac{3}{4}$-approximation bound is tight. Then, we study a more general model than weak-popularity, where for each edge, we can specify independently for both endpoints the size of improvement the endpoint needs to vote in favor of a new matching $N$. We show that even in this more general model, a so-called $\gamma$-popular matching always exists and that the same positive results still hold. Finally, we define an other, stronger variant of popularity, called super-popularity, where even a weak improvement is enough to vote in favor of a new matching. We show that for this case, even the existence problem is NP-hard.
    Keywords Computer Science - Computer Science and Game Theory
    Subject code 005
    Publishing date 2023-10-18
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  3. Book ; Online: Popular and Dominant Matchings with Uncertain, Multilayer and Aggregated Preferences

    Csáji, Gergely

    2023  

    Abstract: We study the Popular Matching problem in multiple models, where the preferences of the agents in the instance may change or may be unknown/uncertain. In particular, we study an Uncertainty model, where each agent has a possible set of preferences, a ... ...

    Abstract We study the Popular Matching problem in multiple models, where the preferences of the agents in the instance may change or may be unknown/uncertain. In particular, we study an Uncertainty model, where each agent has a possible set of preferences, a Multilayer model, where there are layers of preference profiles, a Robust model, where any agent may move some other agents up or down some places in his preference list and an Aggregated Preference model, where votes are summed over multiple instances with different preferences. We study both one-sided and two-sided preferences in bipartite graphs. In the one-sided model, we show that all our problems can be solved in polynomial time by utilizing the structure of popular matchings. We also obtain nice structural results. With two-sided preferences, we show that all four above models lead to NP-hard questions for popular matchings. By utilizing the connection between dominant matchings and stable matchings, we show that in the robust and uncertainty model, a certainly dominant matching in all possible prefernce profiles can be found in polynomial-time, whereas in the multilayer and aggregated models, the problem remains NP-hard for dominant matchings too. We also answer an open question about $d$-robust stable matchings.
    Keywords Computer Science - Computer Science and Game Theory
    Subject code 006
    Publishing date 2023-10-22
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  4. Book ; Online: Optimal Capacity Modification for Many-To-One Matching Problems

    Chen, Jiehua / Csáji, Gergely

    2023  

    Abstract: We consider many-to-one matching problems, where one side consists of students and the other side of schools with capacity constraints. We study how to optimally increase the capacities of the schools so as to obtain a stable and perfect matching (i.e., ... ...

    Abstract We consider many-to-one matching problems, where one side consists of students and the other side of schools with capacity constraints. We study how to optimally increase the capacities of the schools so as to obtain a stable and perfect matching (i.e., every student is matched) or a matching that is stable and Pareto-efficient for the students. We consider two common optimality criteria, one aiming to minimize the sum of capacity increases of all schools (abbrv. as MinSum) and the other aiming to minimize the maximum capacity increase of any school (abbrv. as MinMax). We obtain a complete picture in terms of computational complexity: Except for stable and perfect matchings using the MinMax criteria which is polynomial-time solvable, all three remaining problems are NP-hard. We further investigate the parameterized complexity and approximability and find that achieving stable and Pareto-efficient matchings via minimal capacity increases is much harder than achieving stable and perfect matchings.

    Comment: Extended abstract accepted at AAMAS 2023
    Keywords Computer Science - Computer Science and Game Theory ; Computer Science - Multiagent Systems
    Subject code 005
    Publishing date 2023-02-03
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  5. Book ; Online: Approximating maximum-size properly colored forests

    Bai, Yuhang / Bérczi, Kristóf / Csáji, Gergely / Schwarcz, Tamás

    2024  

    Abstract: In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a properly colored spanning tree, i.e., a spanning tree in which any two adjacent edges have distinct colors. The problem is interesting ... ...

    Abstract In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a properly colored spanning tree, i.e., a spanning tree in which any two adjacent edges have distinct colors. The problem is interesting not only from a graph coloring point of view, but is also closely related to the Degree Bounded Spanning Tree and (1,2)-Traveling Salesman problems, two classical questions that have attracted considerable interest in combinatorial optimization and approximation theory. Previous work on properly colored spanning trees has mainly focused on determining the existence of such a tree and hence has not considered the question from an algorithmic perspective. We propose an optimization version called Maximum-size Properly Colored Forest problem, which aims to find a properly colored forest with as many edges as possible. We consider the problem in different graph classes and for different numbers of colors, and present polynomial-time approximation algorithms as well as inapproximability results for these settings. Our proof technique relies on the sum of matching matroids defined by the color classes, a connection that might be of independent combinatorial interest. We also consider the Maximum-size Properly Colored Tree problem, which asks for the maximum size of a properly colored tree not necessarily spanning all the vertices. We show that the optimum is significantly more difficult to approximate than in the forest case, and provide an approximation algorithm for complete multigraphs.

    Comment: 24 pages, 5 figures
    Keywords Computer Science - Data Structures and Algorithms ; Computer Science - Discrete Mathematics ; Mathematics - Combinatorics
    Subject code 511
    Publishing date 2024-02-01
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  6. Book ; Online: Computational complexity of $k$-stable matchings

    Aziz, Haris / Csáji, Gergely / Cseh, Ágnes

    2023  

    Abstract: We study deviations by a group of agents in the three main types of matching markets: the house allocation, the marriage, and the roommates models. For a given instance, we call a matching $k$-stable if no other matching exists that is more beneficial to ...

    Abstract We study deviations by a group of agents in the three main types of matching markets: the house allocation, the marriage, and the roommates models. For a given instance, we call a matching $k$-stable if no other matching exists that is more beneficial to at least $k$ out of the $n$ agents. The concept generalizes the recently studied majority stability. We prove that whereas the verification of $k$-stability for a given matching is polynomial-time solvable in all three models, the complexity of deciding whether a $k$-stable matching exists depends on $\frac{k}{n}$ and is characteristic to each model.

    Comment: SAGT 2023
    Keywords Computer Science - Discrete Mathematics
    Publishing date 2023-07-07
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  7. Book ; Online: Couples can be tractable

    Csáji, Gergely / Manlove, David / McBride, Iain / Trimble, James

    New algorithms and hardness results for the Hospitals / Residents problem with Couples

    2023  

    Abstract: In this paper we study the {\sc Hospitals / Residents problem with Couples} ({\sc hrc}), where a solution is a stable matching or a report that none exists. We present a novel polynomial-time algorithm that can find a near-feasible stable matching ( ... ...

    Abstract In this paper we study the {\sc Hospitals / Residents problem with Couples} ({\sc hrc}), where a solution is a stable matching or a report that none exists. We present a novel polynomial-time algorithm that can find a near-feasible stable matching (adjusting the hospitals' capacities by at most 1) in an {\sc hrc} instance where the couples' preferences are sub-responsive (i.e., if one member switches to a better hospital, than the couple also improves) and sub-complete (i.e., each pair of hospitals that are individually acceptable to both members are jointly acceptable for the couple) by reducing it to an instance of the {\sc Stable Fixtures} problem. We also present a polynomial-time algorithm for {\sc hrc} in a sub-responsive, sub-complete instance that is a Dual Market, or where all couples are one of several possible types. We show that our algorithm also implies the polynomial-time solvability of a stable b-matching problem, where the underlying graph is a multigraph with loops. We complement our algorithms with several hardness results. We show that {\sc hrc} with sub-responsive and sub-complete couples is NP-hard, even with other strong restrictions. We also show that {\sc hrc} with a Dual Market is NP-hard under several simultaneous restrictions. Finally, we show that the problem of finding a matching with the minimum number of blocking pairs in {\sc hrc} is not approximable within $m^{1-\varepsilon}$, for any $\varepsilon>0$, where $m$ is the total length of the hospitals' preference lists, unless P=NP, even if each couple applies to only one pair of hospitals. Our polynomial-time solvability results greatly expand the class of known tractable instances of {\sc hrc} and provide additional evidence as to why long-standing entry-level labour markets that allow couples such as the National Resident Matching Program remain successful to this day.
    Keywords Computer Science - Data Structures and Algorithms ; Computer Science - Artificial Intelligence ; Computer Science - Computer Science and Game Theory
    Subject code 000
    Publishing date 2023-11-01
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  8. Book ; Online: Hedonic Games With Friends, Enemies, and Neutrals

    Chen, Jiehua / Csáji, Gergely / Roy, Sanjukta / Simola, Sofia

    Resolving Open Questions and Fine-Grained Complexity

    2022  

    Abstract: We investigate verification and existence problems for prominent stability concepts in hedonic games with friends, enemies, and optionally with neutrals [8, 16]. We resolve several (long-standing) open questions [4, 16, 20, 23] and show that for friend- ... ...

    Abstract We investigate verification and existence problems for prominent stability concepts in hedonic games with friends, enemies, and optionally with neutrals [8, 16]. We resolve several (long-standing) open questions [4, 16, 20, 23] and show that for friend-oriented preferences, under the friends and enemies model, it is coNP-complete to verify whether a given agent partition is (strictly) core stable, while under the friends, enemies, and neutrals model, it is NP-complete to determine whether an individual stable partition exists. We further look into natural restricted cases from the literature, such as when the friends and enemies relationships are symmetric, when the initial coalitions have bounded size, when the vertex degree in the friendship graph (resp. the union of friendship and enemy graph) is bounded, or when such graph is acyclic or close to being acyclic. We obtain a complete (parameterized) complexity picture regarding these cases.

    Comment: extended abstract appeared at AAMAS 2023
    Keywords Computer Science - Computer Science and Game Theory ; Computer Science - Multiagent Systems
    Subject code 511
    Publishing date 2022-03-17
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  9. Book ; Online: On the complexity of packing rainbow spanning trees

    Bérczi, Kristóf / Csáji, Gergely / Király, Tamás

    2022  

    Abstract: One of the most important questions in matroid optimization is to find disjoint common bases of two matroids. The significance of the problem is well-illustrated by the long list of conjectures that can be formulated as special cases. B\'erczi and ... ...

    Abstract One of the most important questions in matroid optimization is to find disjoint common bases of two matroids. The significance of the problem is well-illustrated by the long list of conjectures that can be formulated as special cases. B\'erczi and Schwarcz showed that the problem is hard in general, therefore identifying the borderline between tractable and intractable instances is of interest. In the present paper, we study the special case when one of the matroids is a partition matroid while the other one is a graphic matroid. This setting is equivalent to the problem of packing rainbow spanning trees, an extension of the problem of packing arborescences in directed graphs which was answered by Edmonds' seminal result on disjoint arborescences. We complement his result by showing that it is NP-complete to decide whether an edge-colored graph contains two disjoint rainbow spanning trees. Our complexity result holds even for the very special case when the graph is the union of two spanning trees and each color class contains exactly two edges. As a corollary, we give a negative answer to a question on the decomposition of oriented $k$-partition-connected digraphs.

    Comment: 11 pages, 5 figures
    Keywords Mathematics - Combinatorics ; Computer Science - Discrete Mathematics
    Subject code 511
    Publishing date 2022-06-23
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  10. Book ; Online: Manipulating the outcome of stable matching and roommates problems

    Bérczi, Kristóf / Csáji, Gergely / Király, Tamás

    2022  

    Abstract: The stable marriage and stable roommates problems have been extensively studied due to their high applicability in various real-world scenarios. However, it might happen that no stable solution exists, or stable solutions do not meet certain requirements. ...

    Abstract The stable marriage and stable roommates problems have been extensively studied due to their high applicability in various real-world scenarios. However, it might happen that no stable solution exists, or stable solutions do not meet certain requirements. In such cases, one might be interested in modifying the instance so that the existence of a stable outcome with the desired properties is ensured. We focus on three different modifications. In stable roommates problems with all capacities being one, we give a simpler proof to show that removing an agent from each odd cycle of a stable partition is optimal. We further show that the problem becomes NP-complete if the capacities are greater than one, or the deleted agents must belong to a fixed subset of vertices. Motivated by inverse optimization problems, we investigate how to modify the preferences of the agents as little as possible so that a given matching becomes stable. The deviation of the new preferences from the original ones can be measured in various ways; here we concentrate on the $\ell_1$-norm. We show that, assuming the Unique Games Conjecture, the problem does not admit a better than $2$ approximation. By relying on bipartite-submodular functions, we give a polynomial-time algorithm for the bipartite case. We also show that a similar approach leads to a 2-approximation for general graphs. Last, we consider problems where the preferences of agents are not fully prescribed, and the goal is to decide whether the preference lists can be extended so that a stable matching exists. We settle the complexity of several variants, including cases when some of the edges are required to be included or excluded from the solution.

    Comment: 26 pages, 10 figures
    Keywords Computer Science - Computer Science and Game Theory
    Subject code 511
    Publishing date 2022-04-28
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

To top