Author name cluster

Alessandro Ferrante

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.

4 papers

2 author rows

TCS Journal 2009 Journal Article

Fast payment schemes for truthful mechanisms with verification

Alessandro Ferrante
Gennaro Parlato
Francesco Sorrentino
Carmine Ventre

In this paper we study optimization problems with verifiable one-parameter selfish agents introduced by Auletta et al. [V. Auletta, R. De Prisco, P. Penna, P. Persiano, The power of verification for one-parameter agents, in: Proceedings of the 31st International Colloquium on Automata, Languages and Programming, ICALP, in: LNCS, vol. 3142, 2004, pp. 171–182]. Our goal is to allocate load among the agents, provided that the secret data of each agent is a single positive real number: the cost they incur per unit load. In such a setting the payment is given after the load completion, therefore if a positive load is assigned to an agent, we are able to verify if the agent declared to be faster than she actually is. We design truthful mechanisms when the agents’ type sets are upper-bounded by a finite value. We provide a truthful mechanism that is c ⋅ ( 1 + ϵ ) -approximate if the underlying algorithm is c -approximate and weakly-monotone. Moreover, if type sets are also discrete, we provide a truthful mechanism preserving the approximation ratio of its algorithmic part. Our results improve the existing ones which provide truthful mechanisms dealing only with finite type sets and do not preserve the approximation ratio of the underlying algorithm. Finally, we give applications for our payment schemes. Firstly, we give a full characterization of the Q ∥ C max problem by using our techniques. Even if our payment schemes need upper-bounded type sets, every instance of Q ∥ C max can be “mapped” into an instance with upper-bounded type sets preserving the approximation ratio. In conclusion, we turn our attention to binary demand games. In particular, we show that the Minimum Radius Spanning Tree admits an exact truthful mechanism with verification achieving time (and space) complexity of the fastest centralized algorithm for it. This contrasts with a recent truthful mechanism for the same problem [G. Proietti, P. Widmayer, A truthful mechanism for the non-utilitarian minimum radius spanning tree problem, in: Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, ACM Press, 2005, pp. 195–202] which pays a linear factor with respect to the complexity of the fastest centralized algorithm. Such a result is extended to several binary demand games studied in literature.

Details DOI

TCS Journal 2008 Journal Article

Mixed Nash equilibria in selfish routing problems with dynamic constraints

Alessandro Ferrante
Mimmo Parente

We study the problem of routing traffic through a congested network consisting of m parallel links, each having a certain speed. Moreover, we are given n selfish (non-cooperative) agents, each of them willing to route her own piece of traffic on exactly one link. Agents are selfish in that they only pick a link which minimize the delay of their own piece of traffic. In this context much effort has been lavished in the framework of mixed Nash equilibria where the agent’s routing choices are regulated by probability distributions, one for each agent, which let the system thus enter a steady state from which no agent is willing to unilaterally deviate. In this work we consider situations in which some agents have constraints on the routing choice: in a sense they are forbidden to route their traffic on some links. We show that at most one Nash equilibrium may exist and, in some cases with equal speed links and where each agent is forbidden to route on at most one link, we give necessary and sufficient conditions on its existence; these conditions correlate the traffic load of the agents. We consider also a dynamic behaviour of the network when the constraints may vary, in particular when a constraint is removed: we establish under which conditions the network is still in equilibrium. These conditions are all effective in the sense that, given a set of yes/no routing constraints on each link for each agent, we provide the probability distributions corresponding to the unique Nash equilibrium associated to the constraints (if it exists). Moreover these conditions and the possible Nash equilibrium are computed in time O ( m n ).

Details DOI

TCS Journal 2008 Journal Article

On the hardness of optimization in power-law graphs

Alessandro Ferrante
Gopal Pandurangan
Kihong Park

Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y i of a given degree i is proportional to i − β where β > 0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent β? Our main result is the proof that many classical NP-hard graph-theoretic optimization problems remain NP-hard on power-law graphs for certain values of β. In particular, we show that some classical problems, such as CLIQUE and COLORING, remain NP-hard for all β ≥ 1. Moreover, we show that all the problems that satisfy the so-called “optimal substructure property” remain NP-hard for all β > 0. This includes classical problems such as MINIMUM VERTEX COVER, MAXIMUM INDEPENDENT SET, and MINIMUM DOMINATING SET. Our proofs involve designing efficient algorithms for constructing graphs with prescribed degree sequences that are tractable with respect to various optimization problems.

Details DOI

LPAR Conference 2007 Conference Paper

Enriched µ-Calculus Pushdown Module Checking

Alessandro Ferrante
Aniello Murano
Mimmo Parente

Abstract The model checking problem for open systems (called module checking ) has been intensively studied in the literature, both for finite–state and infinite–state systems. In this paper, we focus on pushdown module checking with respect to μ –calculus enriched with graded and nominals ( hybrid graded μ -calulus ). We show that this problem is decidable and solvable in double–exponential time in the size of the formula and in exponential time in the size of the system. This result is obtained by exploiting a classical automata–theoretic approach via pushdown nondeterministic parity tree automata. In particular, we reduce in exponential time our problem to the emptiness problem for these automata, which is known to be decidable in Exptime. As a key step of our algorithm, we show an exponential improvement of the construction of a nondeterministic parity tree automaton accepting all models of a formula of the considered logic. This result, not only allows our algorithm to match the known lower bound, but it is also interesting by itself, since it allows investigating decision problems related to enriched μ -calculus formulas in a greatly simplified manner. We conclude the paper with a discussion on the model checking w. r. t. μ -calculus formulas enriched with backward modalities as well.

Details