Arrow Research search

Author name cluster

Jesús Cerquides

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.

13 papers
2 author rows

Possible papers

13

TIST Journal 2017 Journal Article

Algorithms for Graph-Constrained Coalition Formation in the Real World

  • Filippo Bistaffa
  • Alessandro Farinelli
  • Jesús Cerquides
  • Juan Rodríguez-Aguilar
  • Sarvapali D. Ramchurn

Coalition formation typically involves the coming together of multiple, heterogeneous, agents to achieve both their individual and collective goals. In this article, we focus on a special case of coalition formation known as Graph-Constrained Coalition Formation (GCCF) whereby a network connecting the agents constrains the formation of coalitions. We focus on this type of problem given that in many real-world applications, agents may be connected by a communication network or only trust certain peers in their social network. We propose a novel representation of this problem based on the concept of edge contraction, which allows us to model the search space induced by the GCCF problem as a rooted tree. Then, we propose an anytime solution algorithm (Coalition Formation for Sparse Synergies (CFSS)), which is particularly efficient when applied to a general class of characteristic functions called m + a functions. Moreover, we show how CFSS can be efficiently parallelised to solve GCCF using a nonredundant partition of the search space. We benchmark CFSS on both synthetic and realistic scenarios, using a real-world dataset consisting of the energy consumption of a large number of households in the UK. Our results show that, in the best case, the serial version of CFSS is four orders of magnitude faster than the state of the art, while the parallel version is 9.44 times faster than the serial version on a 12-core machine. Moreover, CFSS is the first approach to provide anytime approximate solutions with quality guarantees for very large systems of agents (i.e., with more than 2,700 agents).

Details DOI

JMLR Journal 2013 Journal Article

Alleviating Naive Bayes Attribute Independence Assumption by Attribute Weighting

  • Nayyar A. Zaidi
  • Jesús Cerquides
  • Mark J. Carman
  • Geoffrey I. Webb

Despite the simplicity of the Naive Bayes classifier, it has continued to perform well against more sophisticated newcomers and has remained, therefore, of great interest to the machine learning community. Of numerous approaches to refining the naive Bayes classifier, attribute weighting has received less attention than it warrants. Most approaches, perhaps influenced by attribute weighting in other machine learning algorithms, use weighting to place more emphasis on highly predictive attributes than those that are less predictive. In this paper, we argue that for naive Bayes attribute weighting should instead be used to alleviate the conditional independence assumption. Based on this premise, we propose a weighted naive Bayes algorithm, called WANBIA, that selects weights to minimize either the negative conditional log likelihood or the mean squared error objective functions. We perform extensive evaluations and find that WANBIA is a competitive alternative to state of the art classifiers like Random Forest, Logistic Regression and A1DE. [abs] [ pdf ][ bib ] &copy JMLR 2013. ( edit, beta )

PDF Details

ECAI Conference 2012 Conference Paper

Speeding Up 2-way Number Partitioning

  • Jesús Cerquides
  • Pedro Meseguer

Several algorithms exist for optimally solving 2-way number partitioning. When the cardinality of the multiset to partition is high enough, solving algorithms have to relay on search techniques with low memory complexity. Currently, CKK is the reference of such algorithms. Here we propose a contribution to speed-up CKK. We detail how to consider terminal nodes with 4, 5, 6 or more numbers left, when the original CKK considers a node terminal when it contains 4 or less numbers left. Using this idea, we propose new CKK implementations, which provide savings up to 70% of execution time with respect to the original CKK algorithm. We provide experimental evidence of the benefits of this approach on random number partitioning instances with numbers of 35 bits.

Details

JAAMAS Journal 2010 Journal Article

Constructing a unifying theory of dynamic programming DCOP algorithms via the generalized distributive law

  • Meritxell Vinyals
  • Juan A. Rodriguez-Aguilar
  • Jesús Cerquides

Abstract In this paper we propose a novel message-passing algorithm, the so-called Action-GDL, as an extension to the generalized distributive law (GDL) to efficiently solve DCOPs. Action-GDL provides a unifying perspective of several dynamic programming DCOP algorithms that are based on GDL, such as DPOP and DCPOP algorithms. We empirically show how Action-GDL using a novel distributed post-processing heuristic can outperform DCPOP, and by extension DPOP, even when the latter uses the best arrangement provided by multiple state-of-the-art heuristics.

Details DOI

ECAI Conference 2010 Conference Paper

Egalitarian Utilities Divide-and-Coordinate: Stop arguing about decisions, let's share rewards!

  • Meritxell Vinyals
  • Juan A. Rodríguez-Aguilar
  • Jesús Cerquides

In this paper we formulate a novel Divide-and-Coordinate (DaC) algorithm, the so-called Egalitarian Utilities Divide-and-Coordinate (EU-DaC) algorithm. The Divide-and-Coordinate (DaC) framework [3] is a family of bounded DCOP algorithms that solve DCOPs by exploiting the concept of agreement. The intuition behind EU-DaC is that agents get closer to an agreement, on the optimal solution, when they communicate the local max-marginals utilities for their assignments instead of only their preferred assignments. We provide empirical evidence supporting this hypothesis as well as illustrating the competitiveness of EU-DaC.

Details

JAAMAS Journal 2009 Journal Article

A graphical formalism for mixed multi-unit combinatorial auctions

  • Andrea Giovannucci
  • Jesús Cerquides
  • Juan A. Rodríguez-Aguilar

Abstract Mixed multi-unit combinatorial auctions are auctions that allow participants to bid for bundles of goods to buy, for bundles of goods to sell, and for transformations of goods. The intuitive meaning of a bid for a transformation is that the bidder is offering to produce a set of output goods after having received a set of input goods. To solve such an auction the auctioneer has to choose a set of bids to accept and decide on a sequence in which to implement the associated transformations. Mixed auctions can potentially be employed for the automated assembly of supply chains of agents. However, mixed auctions can be effectively applied only if we can also ensure their computational feasibility without jeopardising optimality. To this end, we propose a graphical formalism, based on Petri nets, that facilitates the compact represention of both the search space and the solutions associated with the winner determination problem for mixed auctions. This approach allows us to dramatically reduce the number of decision variables required for solving a broad class of mixed auction winner determination problems. An additional major benefit of our graphical formalism is that it provides new ways to formally analyse the structural and behavioural properties of mixed auctions.

Details DOI

ECAI Conference 2006 Conference Paper

Benefits of Combinatorial Auctions with Transformability Relationships

  • Andrea Giovannucci
  • Jesús Cerquides
  • Juan A. Rodríguez-Aguilar

In this paper we explore whether an auctioneer/buyer may benefit from introducing his transformability relationships (some goods can be transformed into others at a transformation cost) into multi-unit combinatorial reverse auctions. Thus, we quantitatively assess the potential savings the auctioneer/buyer may obtain with respect to combinatorial reverse auctions that do not consider tranformability relationships. Furthermore, we empirically identify the market conditions under which it is worth for the auctioneer/buyer to exploit transformability relationships.

Details