Author name cluster

Maria Serna

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

1 author row

TCS Journal 2016 Journal Article

Celebrity games

Carme Àlvarez
Maria J. Blesa
Amalia Duch
Arnau Messegué
Maria Serna

We introduce Celebrity games, a new model of network creation games. In this model players have weights (W being the sum of all the player's weights) and there is a critical distance β as well as a link cost α. The cost incurred by a player depends on the cost of establishing links to other players and on the sum of the weights of those players that remain farther than the critical distance. Intuitively, the aim of any player is to be relatively close (at a distance less than β) from the rest of players, mainly of those having high weights. The main features of celebrity games are that: computing the best response of a player is NP-hard if β > 1 and polynomial time solvable otherwise; they always have a pure Nash equilibrium; the family of celebrity games having a connected Nash equilibrium is characterized (the so called star celebrity games) and bounds on the diameter of the resulting equilibrium graphs are given; a special case of star celebrity games shares its set of Nash equilibrium profiles with the MaxBD games with uniform bounded distance β introduced in Bilò et al. [6]. Moreover, we analyze the Price of Anarchy (PoA) and of Stability (PoS) of celebrity games and give several bounds. These are that: for non-star celebrity games PoA = PoS = m a x { 1, W / α }; for star celebrity games PoS = 1 and PoA = O ( m i n { n / β, W α } ) but if the Nash Equilibrium is a tree then the PoA is O ( 1 ); finally, when β = 1 the PoA is at most 2. The upper bounds on the PoA are complemented with some lower bounds for β = 2.

Details DOI

TCS Journal 2011 Journal Article

The complexity of game isomorphism

Joaquim Gabarró
Alina García
Maria Serna

We address the question of whether two multiplayer strategic games are equivalent and the computational complexity of deciding such a property. We introduce two notions of isomorphisms, strong and weak. Each one of those isomorphisms preserves a different structure of the game. Strong isomorphisms are defined to preserve the utility functions and Nash equilibria. Weak isomorphisms preserve only the player’s preference relations and thus pure Nash equilibria. We show that the computational complexity of the game isomorphism problem depends on the level of succinctness of the description of the input games but it is independent of which of the two types of isomorphisms is considered. Utilities in games can be given succinctly by Turing machines, boolean circuits or boolean formulas, or explicitly by tables. Actions can be given both explicitly or succinctly. When the games are given in general form, we assume an explicit description of actions and a succinct description of utilities. We show that the game isomorphism problem for general form games is equivalent to the circuit isomorphism when utilities are described by TMs and to the boolean formula isomorphism problem when utilities are described by formulas. When the game is given in explicit form, we show that the game isomorphism problem is equivalent to the graph isomorphism problem.

Details DOI

TCS Journal 2011 Journal Article

The robustness of stability under link and node failures

Carme Àlvarez
Maria Blesa
Maria Serna

In the area of communication systems, stability refers to the property of keeping the amount of traffic in the system always bounded over time. Different communication system models have been proposed in order to capture the unpredictable behavior of some users and applications. Among those proposed models the adversarial queueing theory (aqt) model turned out to be the most adequate to analyze an unpredictable network. Until now, most of the research done in this field did not consider the possibility of the adversary producing failures on the network structure. The adversarial models proposed in this work incorporate the possibility of dealing with node and link failures provoked by the adversary. Such failures produce temporal disruptions of the connectivity of the system and increase the collisions of packets in the intermediate hosts of the network, and thus the average traffic load. Under such a scenario, the network is required to be equipped with some mechanism for dealing with those collisions. In addition to proposing adversarial models for faulty systems we study the relation between the robustness of the stability of the system and the management of the queues affected by the failures. When the adversary produces link or node failures the queues associated to the corresponding links can be affected in many different ways depending on whether they can receive or serve packets, or rather that they cannot. In most of the cases, protocols and networks containing very simple topologies, which were known to be universally stable in the aqt model, turn out to be unstable under some of the newly proposed adversarial models. This shows that universal stability of networks is not a robust property in the presence of failures.

Details DOI

TCS Journal 2008 Journal Article

High level communication functionalities for wireless sensor networks

Carme Àlvarez
Josep Díaz
Jordi Petit
José Rolim
Maria Serna

In this paper we show how to establish a reliable and efficient high level communication system in a randomly deployed network of sensors equipped with directional antennas. This high level communication system enables the programming of the sensor network using high level communication functionalities without the burden of taking care of their physical capacities (low range, unidirectional links, single frequency, presence of collisions, etc.). The high level communication functionalities we offer include point-to-point communication, point-to-area communication, and one-to-all communication. The basic idea to implement this system is to simulate a virtual network that emerges from the ad-hoc network using self-organization, self-discovery and collaborative methods. We also analyse the efficiency, scalability and robustness of the proposed protocols.

Details DOI

TCS Journal 2007 Journal Article

Communication tree problems

Carme Àlvarez
Rafel Cases
Josep Díaz
Jordi Petit
Maria Serna

In this paper, we deal with the problem of constructing optimal communication trees satisfying given communication requirements. We consider two constant degree tree communication models and several cost measures. First, we analyze whether a tree selected at random provides a good randomized approximation algorithm, and we show that such a construction fails for some of the measures. Secondly, we provide approximation algorithms for the case in which the communication requirements are given by a random graph in two different random models, namely the classical G n, p and random geometric graphs. Finally, we conclude with some open problems.

Details DOI

TCS Journal 2005 Journal Article

The approximability of non-Boolean satisfiability problems and restricted integer programming

Maria Serna
Luca Trevisan
Fatos Xhafa

In this paper we present improved approximation algorithms for two classes of maximization problems defined in Barland et al. (J. Comput. System Sci. 57(2) (1998) 144). Our factors of approximation substantially improve the previous known results and are close to the best possible. On the other hand, we show that the approximation results in the framework of Barland et al. hold also in the parallel setting, and thus we have a new common framework for both computational settings. We prove almost tight non-approximability results, thus solving a main open question of Barland et al. We obtain the results through the constraint satisfaction problem over multi-valued domains, for which we develop approximation algorithms and show non-approximability results. Our parallel approximation algorithms are based on linear programming and random rounding; they are better than previously known sequential algorithms. The non-approximability results are based on new recent progress in the fields of probabilistically checkable proofs and multi-prover one-round proof systems.

Details DOI

TCS Journal 2005 Journal Article

The chromatic and clique numbers of random scaled sector graphs

Josep Díaz
Vishal Sanwalani
Maria Serna
Paul G. Spirakis

Random scaled sector graphs were introduced as a generalization of random geometric graphs to model networks of sensors using optical communication. In the random scaled sector graph model vertices are placed uniformly at random into the [ 0, 1 ] 2 unit square. Each vertex i is assigned uniformly at random sector S i, of central angle α i, in a circle of radius r i (with vertex i as the origin). An arc is present from vertex i to any vertex j, if j falls in S i. In this work, we study the value of the chromatic number χ ( G n ), directed clique number ω ( G n ), and undirected clique number ω 2 ^ ( G n ) for random scaled sector graphs with n vertices, where each vertex spans a sector of α degrees with radius r n = ln n n. We prove that for values α < π, as n → ∞ w. h. p. , χ ( G n ) and ω 2 ^ ( G n ) are Θ ( ln n ln ln n ), while ω ( G n ) is O ( 1 ), showing a clear difference with the random geometric graph model. For α > π w. h. p. , χ ( G n ) and ω 2 ^ ( G n ) are Θ ( ln n ), being the same for random scaled sector and random geometric graphs, while ω ( G n ) is Θ ( ln n ln ln n ).

Details DOI

TCS Journal 2003 Journal Article

An efficient deterministic parallel algorithm for two processors precedence constraint scheduling

Hermann Jung
Maria Serna
Paul Spirakis

We present here a new deterministic parallel algorithm for the two-processor scheduling problem. The algorithm uses only O(n3) processors and takes O(log 2n) time on a CREW PRAM. In order to prove the above bounds we show how to compute in NC the lexicographically first matching for a special kind of convex bipartite graphs.

Details DOI

TCS Journal 2002 Journal Article

Counting H-colorings of partial k-trees

Josep Díaz
Maria Serna
Dimitrios M. Thilikos

The problem of counting all H-colorings of a graph G with n vertices is considered. While the problem is, in general, #P-complete, we give linear time algorithms that solve the main variants of this problem when the input graph G is a k-tree or, in the case where G is directed, when the underlying graph of G is a k-tree. Our algorithms remain polynomial even in the case where k=O(log n) or in the case where the size of H is O(n). Our results are easy to implement and imply the existence of polynomial time algorithms for a series of problems on partial k-trees such as core checking and chromatic polynomial computation.

Details DOI

TCS Journal 2001 Journal Article

On the parallel approximability of a subclass of quadratic programming

Maria Serna
Fatos Xhafa

In this paper we deal with the parallel approximability of a special class of quadratic programming (QP), called smooth quadratic programming. This subclass of QP is obtained by imposing restrictions on the coefficients of QP instance, namely the smoothness and positiveness restrictions. The smoothness condition restricts the magnitudes of the coefficients of the instance while the positiveness condition requires that (part of) the coefficients of the instance be non-negative. Interestingly, even with these restrictions several combinatorial optimization problems are captured by this class. We show that there is a parallel additive approximation procedure to instances of smooth QP. The additive procedure translates into an NC approximation scheme (NCAS) when the optimal value of the instance is Ω(n2), where n is the number of variables of the instance. In particular, the procedure yields an NCAS for positive instances of smooth QP. The additive approximation procedure is obtained by reducing the instance of QP to an instance of positive linear programming, finding in NC an approximate fractional solution to the obtained program, and then rounding the fractional solution to an integer approximate solution for the original problem. Next, we extend the result to instances of bounded degree Smooth Integer Programming. Finally, we consider several combinatorial problems that are modeled by smooth QP (or smooth integer programs) and show that the techniques presented here can be used to obtain NC Approximation Schemes for “dense” instances of such problems.

Details DOI