GLORIA

GEOMAR Library Ocean Research Information Access

X

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • MDPI AG  (3)
Material
Publisher
  • MDPI AG  (3)
Person/Organisation
Language
Years
  • 1
    Online Resource
    Online Resource
    The Traffic Grooming Problem in Optical Networks with Respect to ADMs and OADMs: Complexity and Approximation
    MDPI AG ; 2021
    In:  Algorithms Vol. 14, No. 5 ( 2021-05-11), p. 151-
    Details
    In: Algorithms, MDPI AG, Vol. 14, No. 5 ( 2021-05-11), p. 151-
    Abstract: All-optical networks transmit messages along lightpaths in which the signal is transmitted using the same wavelength in all the relevant links. We consider the problem of switching cost minimization in these networks. Specifically, the input to the problem under consideration is an optical network modeled by a graph G, a set of lightpaths modeled by paths on G, and an integer g termed the grooming factor. One has to assign a wavelength (modeled by a color) to every lightpath, so that every edge of the graph is used by at most g paths of the same color. A lightpath operating at some wavelength λ uses one Add/Drop multiplexer (ADM) at both endpoints and one Optical Add/Drop multiplexer (OADM) at every intermediate node, all operating at a wavelength of λ. Two lightpaths, both operating at the same wavelength λ, share the ADMs and OADMs in their common nodes. Therefore, the total switching cost due to the usage of ADMs and OADMs depends on the wavelength assignment. We consider networks of ring and path topology and a cost function that is a convex combination α·|OADMs|+(1−α)|ADMs| of the number of ADMs and the number of OADMs deployed in the network. We showed that the problem of minimizing this cost function is NP-complete for every convex combination, even in a path topology network with g=2. On the positive side, we present a polynomial-time approximation algorithm for the problem.
    Type of Medium: Online Resource
    ISSN: 1999-4893
    URL: Article
    DOI: 10.3390/a14050151
    Language: English
    Publisher: MDPI AG
    Publication Date: 2021
    detail.hit.zdb_id: 2455149-1
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 2
    Online Resource
    Online Resource
    On Multidimensional Congestion Games
    MDPI AG ; 2020
    In:  Algorithms Vol. 13, No. 10 ( 2020-10-15), p. 261-
    Details
    In: Algorithms, MDPI AG, Vol. 13, No. 10 ( 2020-10-15), p. 261-
    Abstract: We introduce multidimensional congestion games, that is, congestion games whose set of players is partitioned into d+1 clusters C0,C1,…,Cd. Players in C0 have full information about all the other participants in the game, while players in Ci, for any 1≤i≤d, have full information only about the members of C0∪Ci and are unaware of all the others. This model has at least two interesting applications: (i) it is a special case of graphical congestion games induced by an undirected social knowledge graph with independence number equal to d, and (ii) it represents scenarios in which players have a type and the level of competition they experience on a resource depends on their type and on the types of the other players using it. We focus on the case in which the cost function associated with each resource is affine and bound the price of anarchy and stability as a function of d with respect to two meaningful social cost functions and for both weighted and unweighted players. We also provide refined bounds for the special case of d=2 in presence of unweighted players.
    Type of Medium: Online Resource
    ISSN: 1999-4893
    URL: Article
    DOI: 10.3390/a13100261
    Language: English
    Publisher: MDPI AG
    Publication Date: 2020
    detail.hit.zdb_id: 2455149-1
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 3
    Online Resource
    Online Resource
    On Nash Equilibria in Non-Cooperative All-Optical Networks
    MDPI AG ; 2021
    In:  Algorithms Vol. 14, No. 1 ( 2021-01-09), p. 15-
    Details
    In: Algorithms, MDPI AG, Vol. 14, No. 1 ( 2021-01-09), p. 15-
    Abstract: We consider the problem of determining a routing in all-optical networks, in which some couples of nodes want to communicate. In particular, we study this problem from the point of view of a network provider that has to design suitable payment functions for non-cooperative agents, corresponding to the couples of nodes wishing to communicate. The network provider aims at inducing stable routings (i.e., routings corresponding to Nash equilibria) using a low number of wavelengths. We consider three different kinds of local knowledge that agents may exploit to compute their payments, leading to three corresponding information levels. Under complete information, the network provider can design a payment function, inducing the agents to reach a Nash equilibrium mirroring any desired routing. If the price to an agent is computed only as a function of the wavelengths used along connecting paths (minimal level) or edges (intermediate level), the most reasonable functions either do not admit Nash equilibria or admit very inefficient ones, i.e., with the largest possible price of anarchy. However, by suitably restricting the network topology, a constant price of anarchy for chains and rings and a logarithmic one for trees can be obtained under the minimal and intermediate levels, respectively.
    Type of Medium: Online Resource
    ISSN: 1999-4893
    URL: Article
    DOI: 10.3390/a14010015
    Language: English
    Publisher: MDPI AG
    Publication Date: 2021
    detail.hit.zdb_id: 2455149-1
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...