Yazar "Shalom, Mordechai" seçeneğine göre listele
Listeleniyor 1 - 5 / 5
Sayfa Başına Sonuç
Sıralama seçenekleri
Öğe Distribution games: a new class of games with application to user provided networks(Institute of Electrical and Electronics Engineers Inc., 2022-11-29) Taşçı, Sinan Emre; Shalom, Mordechai; Korçak, ÖmerUser Provided Network (UPN) is a promising solution for sharing the limited network resources by utilizing user capabilities as a part of the communication infrastructure. In UPNs, it is an important problem to decide how to share the resources among multiple clients in decentralized manner. Motivated by this problem, we introduce a new class of games termed distribution games that can be used to distribute efficiently and fairly the bandwidth capacity among users. We show that every distribution game has at least one pure strategy Nash equilibrium (NE) and any best response dynamics always converges to such an equilibrium. We consider social welfare functions that are weighted sums of bandwidths allocated to clients. We present tight upper bounds for the price of anarchy and price of stability of these games provided that they satisfy some reasonable assumptions. We define two specific practical instances of distribution games that fit these assumptions. We conduct experiments on one of these instances and demonstrate that in most of the settings the social welfare obtained by the best response dynamics is very close to the optimum. Simulations show that this game also leads to a fair distribution of the bandwidth.Öğe Hierarchical b-Matching(Springer Science and Business Media Deutschland GmbH, 2021) Emek, Yuval; Kutten, Shay; Shalom, Mordechai; Zaks, ShmuelA matching of a graph is a subset of edges no two of which share a common vertex, and a maximum matching is a matching of maximum cardinality. In a b-matching every vertex v has an associated bound bv, and a maximum b-matching is a maximum set of edges, such that every vertex v appears in at most bv of them. We study an extension of this problem, termed Hierarchical b-Matching. In this extension, the vertices are arranged in a hierarchical manner. At the first level the vertices are partitioned into disjoint subsets, with a given bound for each subset. At the second level the set of these subsets is again partitioned into disjoint subsets, with a given bound for each subset, and so on. We seek for a maximum set of edges, that obey all bounds (that is, no vertex v participates in more than bv edges, then all the vertices in one subset do not participate in more that subset’s bound of edges, and so on hierarchically). This is a sub-problem of the matroid matching problem which is NP -hard in general. It corresponds to the special case where the matroid is restricted to be laminar and the weights are unity. A pseudo-polynomial algorithm for the weighted laminar matroid matching problem is presented in [8]. We propose a polynomial-time algorithm for Hierarchical b-matching, i.e. the unweighted laminar matroid matching problem, and discuss how our techniques can possibly be generalized to the weighted case.Öğe On the maximum cardinality cut problem in proper interval graphs and related graph classes(Elsevier B.V., 2022-01-04) Boyacı, Arman; Ekim, Tınaz; Shalom, MordechaiAlthough it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this work we consider the parameterized complexity of this problem. We show that the maximum cardinality cut problem in proper/unit interval graphs is FPT when parameterized by the maximum number of non-empty bubbles in a column of its bubble model. We then generalize this result to a more general graph class by defining new parameters related to the well-known clique-width parameter. Specifically, we define an (?,?,?)-clique-width decomposition of a graph as a clique-width decomposition in which at each step the following invariant is preserved: after discarding at most ? labels, a) every label consists of at most ? sets of twin vertices, and b) all the labels together induce a graph with independence number at most ?. We show that for every two constants ?,?>0 the problem is FPT when parameterized by ? plus the smallest width of an (?,?,?)-clique-width decomposition.Öğe On the online coalition structure generation problem(AI Access Foundationusc Information Sciences Inst, 2021) Flammini, Michele; Monaco, Gianpiero; Moscardelli, Luca; Shalom, Mordechai; Zaks, ShmuelWe consider the online version of the coalition structure generation problem, in which agents, corresponding to the vertices of a graph, appear in an online fashion and have to be partitioned into coalitions by an authority (i.e., an online algorithm). When an agent appears, the algorithm has to decide whether to put the agent into an existing coalition or to create a new one containing, at this moment, only her. The decision is irrevocable. The objective is partitioning agents into coalitions so as to maximize the resulting social welfare that is the sum of all coalition values. We consider two cases for the value of a coalition: (1) the sum of the weights of its edges, and (2) the sum of the weights of its edges divided by its size. Coalition structures appear in a variety of application in AI, multi-agent systems, networks, as well as in social networks, data analysis, computational biology, game theory, and scheduling. For each of the coalition value functions we consider the bounded and unbounded cases depending on whether or not the size of a coalition can exceed a given value alpha. Furthermore, we consider the case of a limited number of coalitions and various weight functions for the edges, i.e., unrestricted, positive and constant weights. We show tight or nearly tight bounds for the competitive ratio in each case.Öğe A short proof of the size of edge-extremal chordal graphs(Mahmut Akyiğit, 2022-08-30) Shalom, MordechaiBlair et. al. [3] have recently determined the maximum number of edges of a chordal graph with a maximum degree less than d and the matching number at most ? by exhibiting a family of chordal graphs achieving this bound. We provide simple proof of their result.
