2023 [ nach oben ]

Cseh, Ágnes; Führlich, Pascal; Lenzner, Pascal The Swiss GambitAutonomous Agents and Multi-Agent Systems (AAMAS) 2023
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
In each round of a Swiss-system tournament, players of similar score are paired against each other. An intentional early loss therefore might lead to weaker opponents in later rounds and thus to a better final tournament result a phenomenon known as the Swiss Gambit. To the best of our knowledge it is an open question whether this strategy can actually work. This paper provides answers based on an empirical agent-based analysis for the most prominent application area of the Swiss-system format, namely chess tournaments. We simulate realistic tournaments by employing the official FIDE pairing system for computing the player pairings in each round. We show that even though gambits are widely possible in Swiss-system chess tournaments, profiting from them requires a high degree of predictability of match results. Moreover, even if a Swiss Gambit succeeds, the obtained improvement in the final ranking is limited. Our experiments prove that counting on a Swiss Gambit is indeed a lot more of a risky gambit than a reliable strategy to improve the final rank.
@inproceedings{cseh2023swiss, abstract = {In each round of a Swiss-system tournament, players of similar score are paired against each other. An intentional early loss therefore might lead to weaker opponents in later rounds and thus to a better final tournament result a phenomenon known as the Swiss Gambit. To the best of our knowledge it is an open question whether this strategy can actually work. This paper provides answers based on an empirical agent-based analysis for the most prominent application area of the Swiss-system format, namely chess tournaments. We simulate realistic tournaments by employing the official FIDE pairing system for computing the player pairings in each round. We show that even though gambits are widely possible in Swiss-system chess tournaments, profiting from them requires a high degree of predictability of match results. Moreover, even if a Swiss Gambit succeeds, the obtained improvement in the final ranking is limited. Our experiments prove that counting on a Swiss Gambit is indeed a lot more of a risky gambit than a reliable strategy to improve the final rank.}, author = {Cseh, Ágnes and Führlich, Pascal and Lenzner, Pascal}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {agnescseh aamas year2023 pascallenzner}, title = {The Swiss Gambit}, year = 2023 }

2022 [ nach oben ]

Cseh, Ágnes; Peters, Jannik Three-Dimensional Popular Matching with Cyclic PreferencesAutonomous Agents and Multi-Agent Systems (AAMAS) 2022: 77–87
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Two actively researched problem settings in matchings under preferences are popular matchings and the three-dimensional stable matching problem with cyclic preferences. In this paper, we apply the optimality notion of the first topic to the input characteristics of the second one. We investigate the connection between stability, popularity, and their strict variants, strong stability and strong popularity in three-dimensional instances with cyclic preferences. Furthermore, we also derive results on the complexity of these problems when the preferences are derived from master lists.
@inproceedings{cseh2022threedimensional, abstract = {Two actively researched problem settings in matchings under preferences are popular matchings and the three-dimensional stable matching problem with cyclic preferences. In this paper, we apply the optimality notion of the first topic to the input characteristics of the second one. We investigate the connection between stability, popularity, and their strict variants, strong stability and strong popularity in three-dimensional instances with cyclic preferences. Furthermore, we also derive results on the complexity of these problems when the preferences are derived from master lists.}, author = {Cseh, Ágnes and Peters, Jannik}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {jannikpeters agnescseh aamas year2022}, pages = {77–87}, title = {Three-Dimensional Popular Matching with Cyclic Preferences}, year = 2022 }

Cseh, Ágnes; Friedrich, Tobias; Peters, Jannik Pareto Optimal and Popular House Allocation with Lower and Upper QuotasAutonomous Agents and Multi-Agent Systems (AAMAS) 2022: 300–308
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
In the house allocation problem with lower and upper quotas, we are given a set of applicants and a set of projects. Each applicant has a strictly ordered preference list over the projects, while the projects are equipped with a lower and an upper quota. A feasible matching assigns the applicants to the projects in such a way that a project is either matched to no applicant or to a number of applicants between its lower and upper quota. In this model we study two classic optimality concepts: Pareto optimality and popularity. We show that finding a popular matching is hard even if the maximum lower quota is 2 and that finding a perfect Pareto optimal matching, verifying Pareto optimality, and verifying popularity are all NP-complete even if the maximum lower quota is 3. We complement the last three negative results by showing that the problems become polynomial-time solvable when the maximum lower quota is 2, thereby answering two open questions of Cechlárová and Fleiner. Finally, we also study the parameterized complexity of all four mentioned problems.
@inproceedings{cseh2022pareto, abstract = {In the house allocation problem with lower and upper quotas, we are given a set of applicants and a set of projects. Each applicant has a strictly ordered preference list over the projects, while the projects are equipped with a lower and an upper quota. A feasible matching assigns the applicants to the projects in such a way that a project is either matched to no applicant or to a number of applicants between its lower and upper quota. In this model we study two classic optimality concepts: Pareto optimality and popularity. We show that finding a popular matching is hard even if the maximum lower quota is 2 and that finding a perfect Pareto optimal matching, verifying Pareto optimality, and verifying popularity are all NP-complete even if the maximum lower quota is 3. We complement the last three negative results by showing that the problems become polynomial-time solvable when the maximum lower quota is 2, thereby answering two open questions of Cechlárová and Fleiner. Finally, we also study the parameterized complexity of all four mentioned problems.}, author = {Cseh, Ágnes and Friedrich, Tobias and Peters, Jannik}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {jannikpeters agnescseh tobiasfriedrich aamas year2022}, pages = {300–308}, title = {Pareto Optimal and Popular House Allocation with Lower and Upper Quotas}, year = 2022 }

Führlich, Pascal; Cseh, Ágnes; Lenzner, Pascal Improving Ranking Quality and Fairness in Swiss-System Chess TournamentsACM Conference on Economics and Computation (EC) 2022: 1101–1102
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The International Chess Federation (FIDE) imposes a voluminous and complex set of player pairing criteria in Swiss-system chess tournaments and endorses computer programs that are able to calculate the prescribed pairings. The purpose of these formalities is to ensure that players are paired fairly during the tournament and that the final ranking corresponds to the players' true strength order. We contest the official FIDE player pairing routine by presenting alternative pairing rules. These can be enforced by computing maximum weight matchings in a carefully designed graph. We demonstrate by extensive experiments that a tournament format using our mechanism (1) yields fairer pairings in the rounds of the tournament and (2) produces a final ranking that reflects the players' true strengths better than the state-of-the-art FIDE pairing system.
@inproceedings{fuhrlich2022improving, abstract = {The International Chess Federation (FIDE) imposes a voluminous and complex set of player pairing criteria in Swiss-system chess tournaments and endorses computer programs that are able to calculate the prescribed pairings. The purpose of these formalities is to ensure that players are paired fairly during the tournament and that the final ranking corresponds to the players' true strength order. We contest the official FIDE player pairing routine by presenting alternative pairing rules. These can be enforced by computing maximum weight matchings in a carefully designed graph. We demonstrate by extensive experiments that a tournament format using our mechanism (1) yields fairer pairings in the rounds of the tournament and (2) produces a final ranking that reflects the players' true strengths better than the state-of-the-art FIDE pairing system.}, author = {Führlich, Pascal and Cseh, Ágnes and Lenzner, Pascal}, booktitle = {ACM Conference on Economics and Computation (EC)}, keywords = {agnescseh year2022 ec pascallenzner}, pages = {1101 – 1102}, publisher = {ACM}, title = {Improving Ranking Quality and Fairness in Swiss-System Chess Tournaments}, year = 2022 }

2021 [ nach oben ]

Cseh, Ágnes; Juhos, Attila Pairwise Preferences in the Stable Marriage ProblemACM Transactions on Economics and Computation (TEAC) 2021: 1–28
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability—weak, strong and super-stability—under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determine the complexity of all cases not yet known, and thus give an exact boundary in terms of preference structure between tractable and intractable cases.
@article{cseh2021pairwise, abstract = {We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability—weak, strong and super-stability—under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determine the complexity of all cases not yet known, and thus give an exact boundary in terms of preference structure between tractable and intractable cases.}, author = {Cseh, Ágnes and Juhos, Attila}, journal = {ACM Transactions on Economics and Computation (TEAC)}, keywords = {sys:relevantfor:ae agnescseh}, number = 1, pages = {1–28}, publisher = {ACM New York, NY, USA}, title = {Pairwise Preferences in the Stable Marriage Problem}, volume = 9, year = 2021 }

Cseh, Ágnes; Kavitha, Telikepalli Popular matchings in complete graphsAlgorithmica 2021: 1–31
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Our input is a complete graph \(G = (V,E)\) on n vertices where each vertex has a strict ranking of all other vertices in \(G\). The goal is to construct a matching in \(G\) that is "globally stable" or popular. A matching \(M\) is popular if \(M\) does not lose a head-to-head election against any matching \(M'\): here each vertex casts a vote for the matching in \(\{M,M'\}\) where it gets a better assignment. Popular matchings need not exist in the given instance \(G\) and the popular matching problem is to decide whether one exists or not. The popular matching problem in \(G\) is easy to solve for odd \(n\). Surprisingly, the problem becomes NP-hard for even n, as we show here.
@article{cseh2021popular, abstract = {Our input is a complete graph \(G = (V,E)\) on n vertices where each vertex has a strict ranking of all other vertices in \(G\). The goal is to construct a matching in \(G\) that is "globally stable" or popular. A matching \(M\) is popular if \(M\) does not lose a head-to-head election against any matching \(M'\): here each vertex casts a vote for the matching in \(\{M,M'\}\) where it gets a better assignment. Popular matchings need not exist in the given instance \(G\) and the popular matching problem is to decide whether one exists or not. The popular matching problem in \(G\) is easy to solve for odd \(n\). Surprisingly, the problem becomes NP-hard for even n, as we show here.}, author = {Cseh, Ágnes and Kavitha, Telikepalli}, journal = {Algorithmica}, keywords = {sys:relevantfor:ae agnescseh}, pages = {1–31}, publisher = {Springer}, title = {Popular matchings in complete graphs}, year = 2021 }

Andersson, Tommy; Cseh, Ágnes; Ehlers, Lars; Erlanson, Albin Organizing time exchanges: Lessons from matching marketsAmerican Economic Journal: Microeconomics 2021: 338–73
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
This paper considers time exchanges via a common platform (e.g. , markets for exchanging time units, positions at education institutions, and tuition waivers). There are several problems associated with such markets, e.g., imbalanced outcomes, coordination problems, and inefficiencies. We model time exchanges as matching markets and construct a non-manipulable mec hanism that selects an individually rational and balanced allocation that maximizes exchanges among the participating agents (and those allocations are efficient). This mechanism works on a preference domain whereby agents classify the goods provided by other participating agents as either unacceptable or acceptable, and for goods classified as acceptable, agents have specific upper quotas representing their maximum needs.
@article{andersson2021organizing, abstract = {This paper considers time exchanges via a common platform (e.g. , markets for exchanging time units, positions at education institutions, and tuition waivers). There are several problems associated with such markets, e.g., imbalanced outcomes, coordination problems, and inefficiencies. We model time exchanges as matching markets and construct a non-manipulable mec hanism that selects an individually rational and balanced allocation that maximizes exchanges among the participating agents (and those allocations are efficient). This mechanism works on a preference domain whereby agents classify the goods provided by other participating agents as either unacceptable or acceptable, and for goods classified as acceptable, agents have specific upper quotas representing their maximum needs.}, author = {Andersson, Tommy and Cseh, Ágnes and Ehlers, Lars and Erlanson, Albin}, journal = {American Economic Journal: Microeconomics}, keywords = {sys:relevantfor:ae agnescseh}, number = 1, pages = {338–73}, title = {Organizing time exchanges: Lessons from matching markets}, volume = 13, year = 2021 }

Aziz, Haris; Cseh, Agnes; Dickerson, John; McElfresh, Duncan Optimal Kidney Exchange with ImmunosuppressantsConference on Artificial Intelligence (AAAI) 2021: 21–29
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Algorithms for exchange of kidneys is one of the key successful applications in market design, artificial intelligence, and operations research. Potent immunosuppressant drugs suppress the body's ability to reject a transplanted organ up to the point that a transplant across blood- or tissue-type incompatibility becomes possible. In contrast to the standard kidney exchange problem, we consider a setting that also involves the decision about which recipients receive from the limited supply of immunosuppressants that make them compatible with originally incompatible kidneys. We firstly present a general computational framework to model this problem. Our main contribution is a range of efficient algorithms that provide flexibility in terms of meeting meaningful objectives. Motivated by the current reality of kidney exchanges using sophisticated mathematical-programming-based clearing algorithms, we then present a general but scalable approach to optimal clearing with immunosuppression; we validate our approach on realistic data from a large fielded exchange.
@inproceedings{haris2021optimal, abstract = {Algorithms for exchange of kidneys is one of the key successful applications in market design, artificial intelligence, and operations research. Potent immunosuppressant drugs suppress the body's ability to reject a transplanted organ up to the point that a transplant across blood- or tissue-type incompatibility becomes possible. In contrast to the standard kidney exchange problem, we consider a setting that also involves the decision about which recipients receive from the limited supply of immunosuppressants that make them compatible with originally incompatible kidneys. We firstly present a general computational framework to model this problem. Our main contribution is a range of efficient algorithms that provide flexibility in terms of meeting meaningful objectives. Motivated by the current reality of kidney exchanges using sophisticated mathematical-programming-based clearing algorithms, we then present a general but scalable approach to optimal clearing with immunosuppression; we validate our approach on realistic data from a large fielded exchange.}, author = {Aziz, Haris and Cseh, Agnes and Dickerson, John and McElfresh, Duncan}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {johndickerson harisaziz agnescseh aaai duncanmcelfresh year2021}, pages = {21-29}, title = {Optimal Kidney Exchange with Immunosuppressants}, year = 2021 }

Aziz, Haris; Chan, Hau; Cseh, Ágnes; Li, Bo; Ramezani, Fahimeh; Wang, Chenhao Multi-Robot Task Allocation—Complexity and ApproximationAutonomous Agents and Multiagent Systems (AAMAS) 2021: 133–141
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations as well as polynomial-time algorithms for the general setting and important restricted settings.
@inproceedings{aziz2021multirobot, abstract = {Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations as well as polynomial-time algorithms for the general setting and important restricted settings.}, author = {Aziz, Haris and Chan, Hau and Cseh, Ágnes and Li, Bo and Ramezani, Fahimeh and Wang, Chenhao}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {chenhaowang hauchan fahimehramezani boli harisaziz agnescseh aamas year2021}, pages = {133-141}, title = {Multi-Robot Task Allocation—Complexity and Approximation}, year = 2021 }

Kraiczy, Sonja; Cseh, Ágnes; Manlove, David On Weakly and Strongly Popular RankingsAutonomous Agents and Multiagent Systems (AAMAS) 2021: 1563–1565
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Van Zuylen et al. introduced the notion of a popular ranking in a voting context, where each voter submits a strictly-ordered list of all candidates. A popular ranking pi of the candidates is at least as good as any other ranking sigma in the following sense: if we compare pi to sigma, at least half of all voters will always weakly prefer pi. Whether a voter prefers one ranking to another is calculated based on the Kendall distance. A more traditional definition of popularity---as applied to popular matchings, a well-established topic in computational social choice---is stricter, because it requires at least half of the voters who are not indifferent between pi and sigma to prefer pi. In this paper, we derive structural and algorithmic results in both settings, also improving upon the results by van Zylen et al. We also point out connections to the famous open problem of finding a Kemeny consensus with 3 voters.
@inproceedings{kraiczy2021weakly, abstract = {Van Zuylen et al. introduced the notion of a popular ranking in a voting context, where each voter submits a strictly-ordered list of all candidates. A popular ranking pi of the candidates is at least as good as any other ranking sigma in the following sense: if we compare pi to sigma, at least half of all voters will always weakly prefer pi. Whether a voter prefers one ranking to another is calculated based on the Kendall distance. A more traditional definition of popularity—as applied to popular matchings, a well-established topic in computational social choice—is stricter, because it requires at least half of the voters who are not indifferent between pi and sigma to prefer pi. In this paper, we derive structural and algorithmic results in both settings, also improving upon the results by van Zylen et al. We also point out connections to the famous open problem of finding a Kemeny consensus with 3 voters.}, author = {Kraiczy, Sonja and Cseh, Ágnes and Manlove, David}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {davidfmanlove sonjakraiczy agnescseh aamas year2021}, pages = {1563-1565}, title = {On Weakly and Strongly Popular Rankings}, year = 2021 }

2020 [ nach oben ]

Cseh, Ágnes; Fleiner, Tamás The Complexity of Cake Cutting with Unequal SharesACM Transactions on Algorithms 2020: 1–21
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this article, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands, which delivers a proportional solution in fewer queries than all known proto- cols. By giving a matching lower bound, we then show that our protocol is asymptotically the fastest possible. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.
@article{CF20, abstract = {An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this article, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands, which delivers a proportional solution in fewer queries than all known proto- cols. By giving a matching lower bound, we then show that our protocol is asymptotically the fastest possible. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.}, address = {New York, NY, USA}, author = {Cseh, Ágnes and Fleiner, Tamás}, journal = {ACM Transactions on Algorithms}, keywords = {talg sys:relevantfor:ae tamasfleiner agnescseh year2020}, month = {jun}, number = 3, pages = {1-21}, publisher = {Association for Computing Machinery}, title = {The Complexity of Cake Cutting with Unequal Shares}, volume = 16, year = 2020 }

Cseh, Ágnes; Heeger, Klaus The stable marriage problem with ties and restricted edgesDiscrete Optimization 2020: 100571
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In the stable marriage problem, a set of men and a set of women are given, each of whom has a strictly ordered preference list over the acceptable agents in the opposite class. A matching is called stable if it is not blocked by any pair of agents, who mutually prefer each other to their respective partner. Ties in the preferences allow for three different definitions for a stable matching: weak, strong and super-stability. Besides this, acceptable pairs in the instance can be restricted in their ability of blocking a matching or being part of it, which again generates three categories of restrictions on acceptable pairs. Forced pairs must be in a stable matching, forbidden pairs must not appear in it, and lastly, free pairs cannot block any matching. Our computational complexity study targets the existence of a stable solution for each of the three stability definitions, in the presence of each of the three types of restricted pairs. We solve all cases that were still open. As a byproduct, we also derive that the maximum size weakly stable matching problem is hard even in very dense graphs, which may be of independent interest.
@article{CSEH2020100571, abstract = {In the stable marriage problem, a set of men and a set of women are given, each of whom has a strictly ordered preference list over the acceptable agents in the opposite class. A matching is called stable if it is not blocked by any pair of agents, who mutually prefer each other to their respective partner. Ties in the preferences allow for three different definitions for a stable matching: weak, strong and super-stability. Besides this, acceptable pairs in the instance can be restricted in their ability of blocking a matching or being part of it, which again generates three categories of restrictions on acceptable pairs. Forced pairs must be in a stable matching, forbidden pairs must not appear in it, and lastly, free pairs cannot block any matching. Our computational complexity study targets the existence of a stable solution for each of the three stability definitions, in the presence of each of the three types of restricted pairs. We solve all cases that were still open. As a byproduct, we also derive that the maximum size weakly stable matching problem is hard even in very dense graphs, which may be of independent interest.}, author = {Cseh, Ágnes and Heeger, Klaus}, journal = {Discrete Optimization}, keywords = {sys:relevantfor:ae klausheeger agnescseh do year2020}, pages = 100571, title = {The stable marriage problem with ties and restricted edges}, volume = 36, year = 2020 }

2019 [ nach oben ]

Cseh, Ágnes; Matuschke, Jannik New and Simple Algorithms for Stable Flow ProblemsAlgorithmica 2019: 2557–2591
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Stable flows generalize the well-known concept of stable matchings to markets in which transactions may involve several agents, forwarding flow from one to another. An instance of the problem consists of a capacitated directed network in which vertices express their preferences over their incident edges. A network flow is stable if there is no group of vertices that all could benefit from rerouting the flow along a walk. Fleiner (Algorithms 7:1-14, 2014) established that a stable flow always exists by reducing it to the stable allocation problem. We present an augmenting path algorithm for computing a stable flow, the first algorithm that achieves polynomial running time for this problem without using stable allocations as a black-box subroutine. We further consider the problem of finding a stable flow such that the flow value on every edge is within a given interval. For this problem, we present an elegant graph transformation and based on this, we devise a simple and fast algorithm, which also can be used to find a solution to the stable marriage problem with forced and forbidden edges. Finally, we study the stable multicommodity flow model introduced by Király and Pap (Algorithms 6:161-168, 2013). The original model is highly involved and allows for commodity-dependent preference lists at the vertices and commodity-specific edge capacities. We present several graph-based reductions that show equivalence to a significantly simpler model. We further show that it is NP-complete to decide whether an integral solution exists.
@article{cseh2019simple, abstract = {Stable flows generalize the well-known concept of stable matchings to markets in which transactions may involve several agents, forwarding flow from one to another. An instance of the problem consists of a capacitated directed network in which vertices express their preferences over their incident edges. A network flow is stable if there is no group of vertices that all could benefit from rerouting the flow along a walk. Fleiner (Algorithms 7:1-14, 2014) established that a stable flow always exists by reducing it to the stable allocation problem. We present an augmenting path algorithm for computing a stable flow, the first algorithm that achieves polynomial running time for this problem without using stable allocations as a black-box subroutine. We further consider the problem of finding a stable flow such that the flow value on every edge is within a given interval. For this problem, we present an elegant graph transformation and based on this, we devise a simple and fast algorithm, which also can be used to find a solution to the stable marriage problem with forced and forbidden edges. Finally, we study the stable multicommodity flow model introduced by Király and Pap (Algorithms 6:161-168, 2013). The original model is highly involved and allows for commodity-dependent preference lists at the vertices and commodity-specific edge capacities. We present several graph-based reductions that show equivalence to a significantly simpler model. We further show that it is NP-complete to decide whether an integral solution exists.}, author = {Cseh, Ágnes and Matuschke, Jannik}, journal = {Algorithmica}, keywords = {algorithmica sys:relevantfor:ae jannikmatuschke year2019 agnescseh}, pages = {2557-2591}, title = {New and Simple Algorithms for Stable Flow Problems}, year = 2019 }

Cechlárová, Katarína; Cseh, Ágnes; Manlove, David Selected open problems in Matching Under PreferencesBulletin of the European Association for Theoretical Computer Science 2019: 14–38
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
The House Allocation problem, the Stable Marriage problem and the Stable Roommates problem are three fundamental problems in the area of matching under preferences. These problems have been studied for decades under a range of optimality criteria, but despite much progress, some challenging questions remain open. The purpose of this article is to present a range of key open questions for each of these problems, which will hopefully stimulate further research activity in this area.
@article{cechlarova2019selected, abstract = {The House Allocation problem, the Stable Marriage problem and the Stable Roommates problem are three fundamental problems in the area of matching under preferences. These problems have been studied for decades under a range of optimality criteria, but despite much progress, some challenging questions remain open. The purpose of this article is to present a range of key open questions for each of these problems, which will hopefully stimulate further research activity in this area.}, author = {Cechlárová, Katarína and Cseh, Ágnes and Manlove, David}, journal = {Bulletin of the European Association for Theoretical Computer Science}, keywords = {sys:relevantfor:ae year2019 agnescseh eatcs katarinacechlarova davidmanlove}, pages = {14-38}, title = {Selected open problems in Matching Under Preferences}, year = 2019 }

Cseh, Ágnes; Skutella, Martin Paths to stable allocationsInternational Journal of Game Theory 2019: 835–862
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The stable allocation problem is one of the broadest extensions of the well-known stable marriage problem. In an allocation problem, edges of a bipartite graph have capacities and vertices have quotas to fill. Here we investigate the case of uncoordinated processes in stable allocation instances. In this setting, a feasible allocation is given and the aim is to reach a stable allocation by raising the value of the allocation along blocking edges and reducing it on worse edges if needed. Do such myopic changes lead to a stable solution? In our present work, we analyze both better and best response dynamics from an algorithmic point of view. With the help of two deterministic algorithms we show that random procedures reach a stable solution with probability one for all rational input data in both cases. Surprisingly, while there is a polynomial path to stability when better response strategies are played (even for irrational input data), the more intuitive best response steps may require exponential time. We also study the special case of correlated markets. There, random best response strategies lead to a stable allocation in expected polynomial time.
@article{cseh2019paths, abstract = {The stable allocation problem is one of the broadest extensions of the well-known stable marriage problem. In an allocation problem, edges of a bipartite graph have capacities and vertices have quotas to fill. Here we investigate the case of uncoordinated processes in stable allocation instances. In this setting, a feasible allocation is given and the aim is to reach a stable allocation by raising the value of the allocation along blocking edges and reducing it on worse edges if needed. Do such myopic changes lead to a stable solution? In our present work, we analyze both better and best response dynamics from an algorithmic point of view. With the help of two deterministic algorithms we show that random procedures reach a stable solution with probability one for all rational input data in both cases. Surprisingly, while there is a polynomial path to stability when better response strategies are played (even for irrational input data), the more intuitive best response steps may require exponential time. We also study the special case of correlated markets. There, random best response strategies lead to a stable allocation in expected polynomial time.}, author = {Cseh, Ágnes and Skutella, Martin}, journal = {International Journal of Game Theory}, keywords = {sys:relevantfor:ae year2019 agnescseh ijgt martinskutella}, pages = {835-862}, title = {Paths to stable allocations}, year = 2019 }

Cseh, Ágnes; Irving, Robert W.; Manlove, David F. The Stable Roommates Problem with Short ListsTheory of Computing Systems 2019: 128–149
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We consider two variants of the classical Stable Roommates problem with Incomplete (but strictly ordered) preference lists (sri) that are degree constrained, i.e., preference lists are of bounded length. The first variant, egald-sri, involves finding an egalitarian stable matching in solvable instances of sri with preference lists of length at most \(d\). We show that this problem is NP-hard even if \(d = 3\). On the positive side we give a \(\frac{2d+3}{7}\)-approximation algorithm for \(d \in \{3,4,5\}\) which improves on the known bound of 2 for the unbounded preference list case. In the second variant of sri, called d-srti, preference lists can include ties and are of length at most d. We show that the problem of deciding whether an instance of d-srti admits a stable matching is NP-complete even if \(d = 3\). We also consider the "most stable" version of this problem and prove a strong inapproximability bound for the \(d = 3\) case. However for \(d = 2\) we show that the latter problem can be solved in polynomial time.
@article{cseh2019stable, abstract = {We consider two variants of the classical Stable Roommates problem with Incomplete (but strictly ordered) preference lists (sri) that are degree constrained, i.e., preference lists are of bounded length. The first variant, egald-sri, involves finding an egalitarian stable matching in solvable instances of sri with preference lists of length at most \(d\). We show that this problem is NP-hard even if \(d = 3\). On the positive side we give a \(\frac{2d+3}{7}\)-approximation algorithm for \(d \in \{3,4,5\}\) which improves on the known bound of 2 for the unbounded preference list case. In the second variant of sri, called d-srti, preference lists can include ties and are of length at most d. We show that the problem of deciding whether an instance of d-srti admits a stable matching is NP-complete even if \(d = 3\). We also consider the "most stable" version of this problem and prove a strong inapproximability bound for the \(d = 3\) case. However for \(d = 2\) we show that the latter problem can be solved in polynomial time.}, author = {Cseh, Ágnes and Irving, Robert W. and Manlove, David F.}, journal = {Theory of Computing Systems}, keywords = {davidfmanlove sys:relevantfor:ae year2019 agnescseh tocs robertwirving}, pages = {128-149}, title = {The Stable Roommates Problem with Short Lists}, year = 2019 }

Cseh, Ágnes; Juhos, Attila Pairwise Preferences in the Stable Marriage ProblemSymposium Theoretical Aspects of Computer Science (STACS) 2019: 21:1–21:16
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability - weak, strong and super-stability - under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determine the complexity of all cases not yet known, and thus give an exact boundary in terms of preference structure between tractable and intractable cases.
@inproceedings{cseh2019pairwise, abstract = {We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability - weak, strong and super-stability - under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determine the complexity of all cases not yet known, and thus give an exact boundary in terms of preference structure between tractable and intractable cases.}, author = {Cseh, Ágnes and Juhos, Attila}, booktitle = {Symposium Theoretical Aspects of Computer Science (STACS)}, keywords = {sys:relevantfor:ae attilajuhos year2019 stacs agnescseh}, pages = {21:1-21:16}, title = {Pairwise Preferences in the Stable Marriage Problem}, year = 2019 }

2018 [ nach oben ]

Arulselvan, Ashwin; Cseh, Ágnes; Groß, Martin; Manlove, David F.; Matuschke, Jannik Matchings with Lower Quotas: Algorithms and ComplexityAlgorithmica 2018: 185–208
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph \(G = (A \cup P, E)\) with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in \(P\) are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (WMLQ), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of WMLQ from the viewpoints of classical polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NP-hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota \(u_{\max}\) as basis, and we prove that this dependence is necessary unless FPT=W[1]. The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee \(u_{\max}+1\), which is asymptotically best possible unless \(P=NP\). Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas.
@article{arulselvan2018matchings, abstract = {We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph \(G = (A \cup P, E)\) with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in \(P\) are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (WMLQ), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of WMLQ from the viewpoints of classical polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NP-hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota \(u_{\max}\) as basis, and we prove that this dependence is necessary unless FPT=W[1]. The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee \(u_{\max}+1\), which is asymptotically best possible unless \(P=NP\). Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas.}, author = {Arulselvan, Ashwin and Cseh, Ágnes and Groß, Martin and Manlove, David F. and Matuschke, Jannik}, journal = {Algorithmica}, keywords = {davidfmanlove algorithmica sys:relevantfor:ae martingross jannikmatuschke year2018 ashwinarulselvan agnescseh}, pages = {185-208}, title = {Matchings with Lower Quotas: Algorithms and Complexity}, year = 2018 }

Cseh, Ágnes; Kavitha, Telikepalli Popular edges and dominant matchingsMathematical Programming 2018: 209–229
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Given a bipartite graph \(G=(A \cup B, E)\) with strict preference lists and given an edge \(e^* \in E\), we ask if there exists a popular matching in \(G\) that contains \(e^*\). We call this the popular edge problem. A matching \(M\) is popular if there is no matching \(M'\) such that the vertices that prefer \(M'\) to \(M\) outnumber those that prefer \(M\) to \(M'\). It is known that every stable matching is popular; however \(G\) may have no stable matching with the edge \(e^*\). In this paper we identify another natural subclass of popular matchings called "dominant matchings" and show that if there is a popular matching that contains the edge \(e^*\), then there is either a stable matching that contains \(e^*\) or a dominant matching that contains \(e^*\). This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an \(\mathcal{O(n^3)\) algorithm to find a popular matching containing a given set of edges or report that none exists, where \(n=|A|+|B|\).
@article{cseh2018popular, abstract = {Given a bipartite graph \(G=(A \cup B, E)\) with strict preference lists and given an edge \(e^* \in E\), we ask if there exists a popular matching in \(G\) that contains \(e^*\). We call this the popular edge problem. A matching \(M\) is popular if there is no matching \(M'\) such that the vertices that prefer \(M'\) to \(M\) outnumber those that prefer \(M\) to \(M'\). It is known that every stable matching is popular; however \(G\) may have no stable matching with the edge \(e^*\). In this paper we identify another natural subclass of popular matchings called "dominant matchings" and show that if there is a popular matching that contains the edge \(e^*\), then there is either a stable matching that contains \(e^*\) or a dominant matching that contains \(e^*\). This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an \(\mathcal{O}(n^3)\) algorithm to find a popular matching containing a given set of edges or report that none exists, where \(n=|A|+|B|\).}, author = {Cseh, Ágnes and Kavitha, Telikepalli}, journal = {Mathematical Programming}, keywords = {telikepallikavitha sys:relevantfor:ae mp year2018 agnescseh}, pages = {209-229}, title = {Popular edges and dominant matchings}, year = 2018 }

Cseh, Ágnes; Kavitha, Telikepalli Popular Matchings in Complete GraphsFoundations of Software Technology and Theoretical Computer Science (FSTTCS) 2018: 17:1–17:14
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Our input is a complete graph \(G = (V,E)\) on n vertices where each vertex has a strict ranking of all other vertices in \(G\). The goal is to construct a matching in \(G\) that is "globally stable" or popular. A matching \(M\) is popular if \(M\) does not lose a head-to-head election against any matching \(M'\): here each vertex casts a vote for the matching in \(\{M,M'\}\) where it gets a better assignment. Popular matchings need not exist in the given instance \(G\) and the popular matching problem is to decide whether one exists or not. The popular matching problem in \(G\) is easy to solve for odd \(n\). Surprisingly, the problem becomes NP-hard for even n, as we show here.
@inproceedings{cseh2018popular, abstract = {Our input is a complete graph \(G = (V,E)\) on n vertices where each vertex has a strict ranking of all other vertices in \(G\). The goal is to construct a matching in \(G\) that is "globally stable" or popular. A matching \(M\) is popular if \(M\) does not lose a head-to-head election against any matching \(M'\): here each vertex casts a vote for the matching in \(\{M,M'\}\) where it gets a better assignment. Popular matchings need not exist in the given instance \(G\) and the popular matching problem is to decide whether one exists or not. The popular matching problem in \(G\) is easy to solve for odd \(n\). Surprisingly, the problem becomes NP-hard for even n, as we show here.}, author = {Cseh, Ágnes and Kavitha, Telikepalli}, booktitle = {Foundations of Software Technology and Theoretical Computer Science (FSTTCS)}, keywords = {telikepallikavitha sys:relevantfor:ae fsttcs year2018 agnescseh}, pages = {17:1-17:14}, title = {Popular Matchings in Complete Graphs}, year = 2018 }

Cseh, Ágnes; Fleiner, Tamás The Complexity of Cake Cutting with Unequal SharesSymposium Algorithmic Game Theory (SAGT) 2018: 19–30
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this paper, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands that delivers a proportional solution in fewer queries than all known algorithms. Then we show that our protocol is asymptotically the fastest possible by giving a matching lower bound. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.
@inproceedings{cseh2018complexity, abstract = {An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this paper, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands that delivers a proportional solution in fewer queries than all known algorithms. Then we show that our protocol is asymptotically the fastest possible by giving a matching lower bound. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.}, author = {Cseh, Ágnes and Fleiner, Tamás}, booktitle = {Symposium Algorithmic Game Theory (SAGT)}, keywords = {sys:relevantfor:ae year2018 tamasfleiner bestpaper agnescseh sagt}, pages = {19-30}, title = {The Complexity of Cake Cutting with Unequal Shares}, year = 2018 }

2017 [ nach oben ]

Cseh, Ágnes; Huang, Chien-Chung; Kavitha, Telikepalli Popular Matchings with Two-Sided Preferences and One-Sided TiesSIAM Journal on Discrete Mathematics 2017: 367–379
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We are given a bipartite graph \(G = (A \cup B, E)\) where each vertex has a preference list ranking its neighbors: In particular, every \(a \in A\) ranks its neighbors in a strict order of preference, whereas the preference list of any \(b \in B\) may contain ties. A matching \(M\) is popular if there is no matching \(M'\) such that the number of vertices that prefer \(M'\) to \(M\) exceeds the number of vertices that prefer \(M\) to \(M'\). We show that the problem of deciding whether \(G\) admits a popular matching or not is NP-hard. This is the case even when every \(b \in B\) either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each \(b \in B\) puts all its neighbors into a single tie. That is, all neighbors of \(b\) are tied in \(b\)'s list and \(b\) desires to be matched to any of them. Our main result is an \(\mathcal{O(n^2)\) algorithm (where \(n = |A \cup B|)\) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in \(B\) have no preferences and do not care whether they are matched or not.
@article{cseh2017popular, abstract = {We are given a bipartite graph \(G = (A \cup B, E)\) where each vertex has a preference list ranking its neighbors: In particular, every \(a \in A\) ranks its neighbors in a strict order of preference, whereas the preference list of any \(b \in B\) may contain ties. A matching \(M\) is popular if there is no matching \(M'\) such that the number of vertices that prefer \(M'\) to \(M\) exceeds the number of vertices that prefer \(M\) to \(M'\). We show that the problem of deciding whether \(G\) admits a popular matching or not is NP-hard. This is the case even when every \(b \in B\) either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each \(b \in B\) puts all its neighbors into a single tie. That is, all neighbors of \(b\) are tied in \(b\)'s list and \(b\) desires to be matched to any of them. Our main result is an \(\mathcal{O}(n^2)\) algorithm (where \(n = |A \cup B|)\) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in \(B\) have no preferences and do not care whether they are matched or not.}, author = {Cseh, Ágnes and Huang, Chien{-}Chung and Kavitha, Telikepalli}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {telikepallikavitha sys:relevantfor:ae sidma year2017 chien-chunghuang agnescseh}, pages = {367-379}, title = {Popular Matchings with Two-Sided Preferences and One-Sided Ties}, year = 2017 }

Cseh, Ágnes; Matuschke, Jannik New and Simple Algorithms for Stable Flow ProblemsWorkshop Graph-Theoretic Concepts in Computer Science (WG) 2017: 206–219
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
Stable flows generalize the well-known concept of stable matchings to markets in which transactions may involve several agents, forwarding flow from one to another. An instance of the problem consists of a capacitated directed network, in which vertices express their preferences over their incident edges. A network flow is stable if there is no group of vertices that all could benefit from rerouting the flow along a walk. Fleiner [13] established that a stable flow always exists by reducing it to the stable allocation problem. We present an augmenting-path algorithm for computing a stable flow, the first algorithm that achieves polynomial running time for this problem without using stable allocation as a black-box subroutine. We further consider the problem of finding a stable flow such that the flow value on every edge is within a given interval. For this problem, we present an elegant graph transformation and based on this, we devise a simple and fast algorithm, which also can be used to find a solution to the stable marriage problem with forced and forbidden edges. Finally, we study the highly complex stable multicommodity flow model by Király and Pap [24]. We present several graph-based reductions that show equivalence to a significantly simpler model. We further show that it is NP-complete to decide whether an integral solution exists.
@inproceedings{cseh2017simple, abstract = {Stable flows generalize the well-known concept of stable matchings to markets in which transactions may involve several agents, forwarding flow from one to another. An instance of the problem consists of a capacitated directed network, in which vertices express their preferences over their incident edges. A network flow is stable if there is no group of vertices that all could benefit from rerouting the flow along a walk. Fleiner [13] established that a stable flow always exists by reducing it to the stable allocation problem. We present an augmenting-path algorithm for computing a stable flow, the first algorithm that achieves polynomial running time for this problem without using stable allocation as a black-box subroutine. We further consider the problem of finding a stable flow such that the flow value on every edge is within a given interval. For this problem, we present an elegant graph transformation and based on this, we devise a simple and fast algorithm, which also can be used to find a solution to the stable marriage problem with forced and forbidden edges. Finally, we study the highly complex stable multicommodity flow model by Király and Pap [24]. We present several graph-based reductions that show equivalence to a significantly simpler model. We further show that it is NP-complete to decide whether an integral solution exists.}, author = {Cseh, Ágnes and Matuschke, Jannik}, booktitle = {Workshop Graph-Theoretic Concepts in Computer Science (WG)}, keywords = {sys:relevantfor:ae jannikmatuschke year2017 agnescseh wg}, pages = {206-219}, title = {New and Simple Algorithms for Stable Flow Problems}, year = 2017 }

2016 [ nach oben ]

Cseh, Ágnes Marriages are made in calculationBulletin of the European Association for Theoretical Computer Science 2016: 180–183
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Butterflies in the stomach, racing heart and sweaty hands. . . is he really the one? The mathematician simply sits down to the computer and calculates it quickly. On the side she makes important discoveries that come handy in various other fields of life, such as job applications.
@article{cseh2016marriages, abstract = {Butterflies in the stomach, racing heart and sweaty hands. . . is he really the one? The mathematician simply sits down to the computer and calculates it quickly. On the side she makes important discoveries that come handy in various other fields of life, such as job applications.}, author = {Cseh, Ágnes}, journal = {Bulletin of the European Association for Theoretical Computer Science}, keywords = {sys:relevantfor:ae year2016 agnescseh eatcs}, pages = {180-183}, title = {Marriages are made in calculation}, year = 2016 }

Cseh, Ágnes; Manlove, David F. Stable Marriage and Roommates problems with restricted edges: Complexity and approximabilityDiscrete Optimization 2016: 62–89
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In the Stable Marriage and Roommates problems, a set of agents is given, each of them having a strictly ordered preference list over some or all of the other agents. A matching is a set of disjoint pairs of mutually acceptable agents. If any two agents mutually prefer each other to their partner, then they block the matching, otherwise, the matching is said to be stable. We investigate the complexity of finding a solution satisfying additional constraints on restricted pairs of agents. Restricted pairs can be either forced or forbidden. A stable solution must contain all of the forced pairs, while it must contain none of the forbidden pairs. Dias et al. (2003) gave a polynomial-time algorithm to decide whether such a solution exists in the presence of restricted edges. If the answer is no, one might look for a solution close to optimal. Since optimality in this context means that the matching is stable and satisfies all constraints on restricted pairs, there are two ways of relaxing the constraints by permitting a solution to: (1) be blocked by as few as possible pairs, or (2) violate as few as possible constraints n restricted pairs. Our main theorems prove that for the (bipartite) Stable Marriage problem, case (1) leads to -hardness and inapproximability results, whilst case (2) can be solved in polynomial time. For non-bipartite Stable Roommates instances, case (2) yields an hard but (under some cardinality assumptions)-approximable problem. In the case of hard problems, we also discuss polynomially solvable special cases, arising from restrictions on the lengths of the preference lists, or upper bounds on the numbers of restricted pairs.
@article{cseh2016stable, abstract = {In the Stable Marriage and Roommates problems, a set of agents is given, each of them having a strictly ordered preference list over some or all of the other agents. A matching is a set of disjoint pairs of mutually acceptable agents. If any two agents mutually prefer each other to their partner, then they block the matching, otherwise, the matching is said to be stable. We investigate the complexity of finding a solution satisfying additional constraints on restricted pairs of agents. Restricted pairs can be either forced or forbidden. A stable solution must contain all of the forced pairs, while it must contain none of the forbidden pairs. Dias et al. (2003) gave a polynomial-time algorithm to decide whether such a solution exists in the presence of restricted edges. If the answer is no, one might look for a solution close to optimal. Since optimality in this context means that the matching is stable and satisfies all constraints on restricted pairs, there are two ways of relaxing the constraints by permitting a solution to: (1) be blocked by as few as possible pairs, or (2) violate as few as possible constraints n restricted pairs. Our main theorems prove that for the (bipartite) Stable Marriage problem, case (1) leads to -hardness and inapproximability results, whilst case (2) can be solved in polynomial time. For non-bipartite Stable Roommates instances, case (2) yields an hard but (under some cardinality assumptions)-approximable problem. In the case of hard problems, we also discuss polynomially solvable special cases, arising from restrictions on the lengths of the preference lists, or upper bounds on the numbers of restricted pairs.}, author = {Cseh, Ágnes and Manlove, David F.}, journal = {Discrete Optimization}, keywords = {davidfmanlove sys:relevantfor:ae year2016 agnescseh do}, pages = {62-89}, title = {Stable Marriage and Roommates problems with restricted edges: Complexity and approximability}, year = 2016 }

Cseh, Ágnes; Dean, Brian C. Improved algorithmic results for unsplittable stable allocation problemsJournal of Combinatorial Optimization 2016: 657–671
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The stable allocation problem is a many-to-many generalization of the well-known stable marriage problem, where we seek a bipartite assignment between, say, jobs (of varying sizes) and machines (of varying capacities) that is "stable" based on a set of underlying preference lists submitted by the jobs and machines. Building on the initial work of Dean et al. (The unsplittable stable marriage problem, 2006), we study a natural "unsplittable" variant of this problem, where each assigned job must be fully assigned to a single machine. Such unsplittable bipartite assignment problems generally tend to be NP-hard, including previously-proposed variants of the unsplittable stable allocation problem (McDermid and Manlove in J Comb Optim 19(3): 279–303, 2010). Our main result is to show that under an alternative model of stability, the unsplittable stable allocation problem becomes solvable in polynomial time; although this model is less likely to admit feasible solutions than the model proposed in McDermid and Manlove (J Comb Optim 19(3): 279–303, McDermid and Manlove 2010), we show that in the event there is no feasible solution, our approach computes a solution of minimal total congestion (overfilling of all machines collectively beyond their capacities). We also describe a technique for rounding the solution of a stable allocation problem to produce "relaxed" unsplit solutions that are only mildly infeasible, where each machine is overcongested by at most a single job.
@article{cseh2016improved, abstract = {The stable allocation problem is a many-to-many generalization of the well-known stable marriage problem, where we seek a bipartite assignment between, say, jobs (of varying sizes) and machines (of varying capacities) that is "stable" based on a set of underlying preference lists submitted by the jobs and machines. Building on the initial work of Dean et al. (The unsplittable stable marriage problem, 2006), we study a natural "unsplittable" variant of this problem, where each assigned job must be fully assigned to a single machine. Such unsplittable bipartite assignment problems generally tend to be NP-hard, including previously-proposed variants of the unsplittable stable allocation problem (McDermid and Manlove in J Comb Optim 19(3): 279–303, 2010). Our main result is to show that under an alternative model of stability, the unsplittable stable allocation problem becomes solvable in polynomial time; although this model is less likely to admit feasible solutions than the model proposed in McDermid and Manlove (J Comb Optim 19(3): 279–303, McDermid and Manlove 2010), we show that in the event there is no feasible solution, our approach computes a solution of minimal total congestion (overfilling of all machines collectively beyond their capacities). We also describe a technique for rounding the solution of a stable allocation problem to produce "relaxed" unsplit solutions that are only mildly infeasible, where each machine is overcongested by at most a single job.}, author = {Cseh, Ágnes and Dean, Brian C.}, journal = {Journal of Combinatorial Optimization}, keywords = {sys:relevantfor:ae jco year2016 agnescseh briancdean}, pages = {657-671}, title = {Improved algorithmic results for unsplittable stable allocation problems}, year = 2016 }

Cseh, Ágnes; Kavitha, Telikepalli Popular Edges and Dominant MatchingsInternational Conference on Integer Programming and Combinatorial Optimization (IPCO) 2016: 138–151
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
Given a bipartite graph \(G=(A \cup B, E)\) with strict preference lists and given an edge \(e^* \in E\), we ask if there exists a popular matching in G that contains \(e^*\). We call this the popular edge problem. A matching \(M\) is popular if there is no matching \(M'\) such that the vertices that prefer \(M'\) to \(M\) outnumber those that prefer \(M\) to \(M'\). It is known that every stable matching is popular; however G may have no stable matching with the edge \(e^*\). In this paper we identify another natural subclass of popular matchings called “dominant matchings” and show that if there is a popular matching that contains the edge \(e^*\), then there is either a stable matching that contains \(e^*\) or a dominant matching that contains \(e^*\). This allows us to design a linear time algorithm for the popular edge problem. When preference lists are complete, we show an \(\mathcal{O(n^3)\) algorithm to find a popular matching containing a given set of edges or report that none exists, where \(n=|A|+|B|\).
@inproceedings{cseh2016popular, abstract = {Given a bipartite graph \(G=(A \cup B, E)\) with strict preference lists and given an edge \(e^* \in E\), we ask if there exists a popular matching in G that contains \(e^*\). We call this the popular edge problem. A matching \(M\) is popular if there is no matching \(M'\) such that the vertices that prefer \(M'\) to \(M\) outnumber those that prefer \(M\) to \(M'\). It is known that every stable matching is popular; however G may have no stable matching with the edge \(e^*\). In this paper we identify another natural subclass of popular matchings called “dominant matchings” and show that if there is a popular matching that contains the edge \(e^*\), then there is either a stable matching that contains \(e^*\) or a dominant matching that contains \(e^*\). This allows us to design a linear time algorithm for the popular edge problem. When preference lists are complete, we show an \(\mathcal{O}(n^3)\) algorithm to find a popular matching containing a given set of edges or report that none exists, where \(n=|A|+|B|\).}, author = {Cseh, Ágnes and Kavitha, Telikepalli}, booktitle = {International Conference on Integer Programming and Combinatorial Optimization (IPCO)}, keywords = {telikepallikavitha sys:relevantfor:ae ipco year2016 agnescseh}, pages = {138-151}, title = {Popular Edges and Dominant Matchings}, year = 2016 }

Cseh, Ágnes; Irving, Robert W.; Manlove, David F. The Stable Roommates Problem with Short ListsSymposium Algorithmic Game Theory (SAGT) 2016: 207–219
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
We consider two variants of the classical Stable Roommates problem with Incomplete (but strictly ordered) preference lists (sri) that are degree constrained, i.e., preference lists are of bounded length. The first variant, egal d-sri, involves finding an egalitarian stable matching in solvable instances of sri with preference lists of length at most d. We show that this problem is NP-hard even if \($d=3$\). On the positive side we give a \(\frac{2d+3}{7}\)-approximation algorithm for \(d \in\{3,4,5\}\) which improves on the known bound of 2 for the unbounded preference list case. In the second variant of sri, called d-srti, preference lists can include ties and are of length at most d. We show that the problem of deciding whether an instance of d-srti admits a stable matching is NP-complete even if \($d=3$\). We also consider the “most stable” version of this problem and prove a strong inapproximability bound for the \($d=3$\) case. However for \($d=2$\) we show that the latter problem can be solved in polynomial time.
@inproceedings{cseh2016stable, abstract = {We consider two variants of the classical Stable Roommates problem with Incomplete (but strictly ordered) preference lists (sri) that are degree constrained, i.e., preference lists are of bounded length. The first variant, egal d-sri, involves finding an egalitarian stable matching in solvable instances of sri with preference lists of length at most d. We show that this problem is NP-hard even if $d=3$. On the positive side we give a \(\frac{2d+3}{7}\)-approximation algorithm for \(d \in\{3,4,5\}\) which improves on the known bound of 2 for the unbounded preference list case. In the second variant of sri, called d-srti, preference lists can include ties and are of length at most d. We show that the problem of deciding whether an instance of d-srti admits a stable matching is NP-complete even if $d=3$. We also consider the “most stable” version of this problem and prove a strong inapproximability bound for the $d=3$ case. However for $d=2$ we show that the latter problem can be solved in polynomial time.}, author = {Cseh, Ágnes and Irving, Robert W. and Manlove, David F.}, booktitle = {Symposium Algorithmic Game Theory (SAGT)}, keywords = {davidfmanlove sys:relevantfor:ae year2016 agnescseh robertwirving sagt}, pages = {207-219}, title = {The Stable Roommates Problem with Short Lists}, year = 2016 }

2015 [ nach oben ]

Cseh, Ágnes; Huang, Chien-Chung; Kavitha, Telikepalli Popular Matchings with Two-Sided Preferences and One-Sided TiesInternational Colloquium on Automata, Languages and Programming (ICALP) 2015: 367–379
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
We are given a bipartite graph \($G=(A \cup B, E)$\) where each vertex has a preference list ranking its neighbors: in particular, every \($a \in A$\) ranks its neighbors in a strict order of preference, whereas the preference lists of \($b \in B$\) may contain ties. A matching \($M$\) is popular if there is no matching \($M'$\) such that the number of vertices that prefer \($M'$\) to \($M$\) exceeds the number that prefer \($M$\) to \($M'$\). We show that the problem of deciding whether \($G$\) admits a popular matching or not is NP-hard. This is the case even when every \($b \in B$\) either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each \($b \in B$\) puts all its neighbors into a single tie. That is, all neighbors of \($b$\) are tied in \($b’s$\) list and and b desires to be matched to any of them. Our main result is an \($\mathcal{O(n^2)$\) algorithm (where \($n=|A \cup B|$\)) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in \($B$\) have no preferences and do not care whether they are matched or not.
@inproceedings{cseh2015popular, abstract = {We are given a bipartite graph $G=(A \cup B, E)$ where each vertex has a preference list ranking its neighbors: in particular, every $a \in A$ ranks its neighbors in a strict order of preference, whereas the preference lists of $b \in B$ may contain ties. A matching $M$ is popular if there is no matching $M'$ such that the number of vertices that prefer $M'$ to $M$ exceeds the number that prefer $M$ to $M'$. We show that the problem of deciding whether $G$ admits a popular matching or not is NP-hard. This is the case even when every $b \in B$ either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each $b \in B$ puts all its neighbors into a single tie. That is, all neighbors of $b$ are tied in $b’s$ list and and b desires to be matched to any of them. Our main result is an $\mathcal{O}(n^2)$ algorithm (where $n=|A \cup B|$) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in $B$ have no preferences and do not care whether they are matched or not.}, author = {Cseh, Ágnes and Huang, Chien-Chung and Kavitha, Telikepalli}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {telikepallikavitha sys:relevantfor:ae chien-chunghuang agnescseh year2015 icalp}, pages = {367-379}, title = {Popular Matchings with Two-Sided Preferences and One-Sided Ties}, year = 2015 }

Arulselvan, Ashwin; Cseh, Ágnes; Groß, Martin; Manlove, David F.; Matuschke, Jannik Many-to-one Matchings with Lower Quotas: Algorithms and ComplexityInternational Symposium Algorithms and Computation (ISAAC) 2015: 176–187
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph \(G = (A \cup P, E)\) with weights on the edges in \(E\), and with lower and upper quotas on the vertices in \(P\). We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (wmlq), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of wmlq from the viewpoints of classic polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NP -hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota \($u_max$\) as basis, and we prove that this dependence is necessary unless FPT=W[1]. Finally, we also present an approximation algorithm for the general case with performance guarantee \(u_max + 1\), which is asymptotically best possible unless \(P=NP\).
@inproceedings{arulselvan2015manytoone, abstract = {We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph \(G = (A \cup P, E)\) with weights on the edges in \(E\), and with lower and upper quotas on the vertices in \(P\). We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (wmlq), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of wmlq from the viewpoints of classic polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NP -hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota $u_max$ as basis, and we prove that this dependence is necessary unless FPT=W[1]. Finally, we also present an approximation algorithm for the general case with performance guarantee \(u_max + 1\), which is asymptotically best possible unless \(P=NP\).}, author = {Arulselvan, Ashwin and Cseh, Ágnes and Groß, Martin and Manlove, David F. and Matuschke, Jannik}, booktitle = {International Symposium Algorithms and Computation (ISAAC)}, keywords = {davidfmanlove martingroß sys:relevantfor:ae jannikmatuschke isaac ashwinarulselvan agnescseh year2015}, pages = {176-187}, title = {Many-to-one Matchings with Lower Quotas: Algorithms and Complexity}, year = 2015 }

Cseh, Ágnes; Manlove, David F. Stable Marriage and Roommates Problems with Restricted Edges: Complexity and ApproximabilitySymposium Algorithmic Game Theory (SAGT) 2015: 15–26
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
In the stable marriage and roommates problems, a set of agents is given, each of them having a strictly ordered preference list over some or all of the other agents. A matching is a set of disjoint pairs of mutually acceptable agents. If any two agents mutually prefer each other to their partner, then they block the matching, otherwise, the matching is said to be stable. We investigate the complexity of finding a solution satisfying additional constraints on restricted pairs of agents. Restricted pairs can be either forced or forbidden. A stable solution must contain all of the forced pairs, while it must contain none of the forbidden pairs. Dias et al. [5] gave a polynomial-time algorithm to decide whether such a solution exists in the presence of restricted edges. If the answer is no, one might look for a solution close to optimal. Since optimality in this context means that the matching is stable and satisfies all constraints on restricted pairs, there are two ways of relaxing the constraints by permitting a solution to: (1) be blocked by as few as possible pairs, or (2) violate as few as possible constraints on restricted pairs. Our main theorems prove that for the (bipartite) stable marriage problem, case (1) leads to NP-hardness and inapproximability results, whilst case (2) can be solved in polynomial time. For non-bipartite stable roommates instances, case (2) yields an NP-hard but (under some cardinality assumptions) 2-approximable problem. In the case of NP-hard problems, we also discuss polynomially solvable special cases, arising from restrictions on the lengths of the preference lists, or upper bounds on the numbers of restricted pairs.
@inproceedings{cseh2015stable, abstract = {In the stable marriage and roommates problems, a set of agents is given, each of them having a strictly ordered preference list over some or all of the other agents. A matching is a set of disjoint pairs of mutually acceptable agents. If any two agents mutually prefer each other to their partner, then they block the matching, otherwise, the matching is said to be stable. We investigate the complexity of finding a solution satisfying additional constraints on restricted pairs of agents. Restricted pairs can be either forced or forbidden. A stable solution must contain all of the forced pairs, while it must contain none of the forbidden pairs. Dias et al. [5] gave a polynomial-time algorithm to decide whether such a solution exists in the presence of restricted edges. If the answer is no, one might look for a solution close to optimal. Since optimality in this context means that the matching is stable and satisfies all constraints on restricted pairs, there are two ways of relaxing the constraints by permitting a solution to: (1) be blocked by as few as possible pairs, or (2) violate as few as possible constraints on restricted pairs. Our main theorems prove that for the (bipartite) stable marriage problem, case (1) leads to NP-hardness and inapproximability results, whilst case (2) can be solved in polynomial time. For non-bipartite stable roommates instances, case (2) yields an NP-hard but (under some cardinality assumptions) 2-approximable problem. In the case of NP-hard problems, we also discuss polynomially solvable special cases, arising from restrictions on the lengths of the preference lists, or upper bounds on the numbers of restricted pairs.}, author = {Cseh, Ágnes and Manlove, David F.}, booktitle = {Symposium Algorithmic Game Theory (SAGT)}, keywords = {davidfmanlove sys:relevantfor:ae agnescseh year2015 sagt}, pages = {15-26}, title = {Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability}, year = 2015 }

2014 [ nach oben ]

Cseh, Ágnes; Skutella, Martin Paths to Stable AllocationsSymposium Algorithmic Game Theory (SAGT) 2014: 61–73
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
The stable allocation problem is one of the broadest extensions of the well-known stable marriage problem. In an allocation problem, edges of a bipartite graph have capacities and vertices have quotas to fill. Here we investigate the case of uncoordinated processes in stable allocation instances. In this setting, a feasible allocation is given and the aim is to reach a stable allocation by raising the value of the allocation along blocking edges and reducing it on worse edges if needed. Do such myopic changes lead to a stable solution? In our present work, we analyze both better and best response dynamics from an algorithmic point of view. With the help of two deterministic algorithms we show that random procedures reach a stable solution with probability one for all rational input data in both cases. Surprisingly, while there is a polynomial path to stability when better response strategies are played (even for irrational input data), the more intuitive best response steps may require exponential time. We also study the special case of correlated markets. There, random best response strategies lead to a stable allocation in expected polynomial time.
@inproceedings{cseh2014paths, abstract = {The stable allocation problem is one of the broadest extensions of the well-known stable marriage problem. In an allocation problem, edges of a bipartite graph have capacities and vertices have quotas to fill. Here we investigate the case of uncoordinated processes in stable allocation instances. In this setting, a feasible allocation is given and the aim is to reach a stable allocation by raising the value of the allocation along blocking edges and reducing it on worse edges if needed. Do such myopic changes lead to a stable solution? In our present work, we analyze both better and best response dynamics from an algorithmic point of view. With the help of two deterministic algorithms we show that random procedures reach a stable solution with probability one for all rational input data in both cases. Surprisingly, while there is a polynomial path to stability when better response strategies are played (even for irrational input data), the more intuitive best response steps may require exponential time. We also study the special case of correlated markets. There, random best response strategies lead to a stable allocation in expected polynomial time.}, author = {Cseh, Ágnes and Skutella, Martin}, booktitle = {Symposium Algorithmic Game Theory (SAGT)}, keywords = {sys:relevantfor:ae agnescseh year2014 martinskutella sagt}, pages = {61-73}, title = {Paths to Stable Allocations}, year = 2014 }

2013 [ nach oben ]

Cseh, Ágnes; Matuschke, Jannik; Skutella, Martin Stable Flows over TimeAlgorithms 2013: 532–545
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In this paper, the notion of stability is extended to network flows over time. As a useful device in our proofs, we present an elegant preflow-push variant of the Gale-Shapley algorithm that operates directly on the given network and computes stable flows in pseudo-polynomial time, both in the static flow and the flow over time case. We show periodical properties of stable flows over time on networks with an infinite time horizon. Finally, we discuss the influence of storage at vertices, with different results depending on the priority of the corresponding holdover edges.
@article{cseh2013stable, abstract = {In this paper, the notion of stability is extended to network flows over time. As a useful device in our proofs, we present an elegant preflow-push variant of the Gale-Shapley algorithm that operates directly on the given network and computes stable flows in pseudo-polynomial time, both in the static flow and the flow over time case. We show periodical properties of stable flows over time on networks with an infinite time horizon. Finally, we discuss the influence of storage at vertices, with different results depending on the priority of the corresponding holdover edges.}, author = {Cseh, Ágnes and Matuschke, Jannik and Skutella, Martin}, journal = {Algorithms}, keywords = {sys:relevantfor:ae jannikmatuschke algorithms agnescseh year2013 martinskutella}, pages = {532-545}, title = {Stable Flows over Time}, year = 2013 }