We consider Max-min Share (MmS) fair allocations of indivisible chores (items with negative utilities). We show that allocation of chores and classical allocation of goods (items with positive utilities) have some fundamental connections but also differences which prevent a straightforward application of algorithms for goods in the chores setting and vice-versa. We prove that an MmS allocation does not need to exist for chores and computing an MmS allocation - if it exists - is strongly NP-hard. In view of these non-existence and complexity results, we present a polynomial-time 2-approximation algorithm for MmS fairness for chores. We then introduce a new fairness concept called optimal MmS that represents the best possible allocation in terms of MmS that is guaranteed to exist. We use connections to parallel machine scheduling to give (1) a polynomial-time approximation scheme for computing an optimal MmS allocation when the number of agents is fixed and (2) an effective and efficient heuristic with an ex-post worst-case analysis.

Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns in which they take one item among those that are still available. It has long been known that sequential allocation is not strategyproof. This raises the question of the complexity of computing a preference report that yields a higher utility than the truthful preference. We show that the problem is NP-complete for one manipulating agent with additive utilities and several non-manipulating agents. In doing so, we correct a wrong claim made in a previous paper. We then give two additional results. First, we present a polynomial-time algorithm for optimal manipulation when the manipulator has additive binary utilities. Second, we consider a stronger notion of manipulation whereby the untruthful outcome yields more utility than the truthful outcome for all utilities consistent with the ordinal preferences; for this notion, we show that a manipulation, if any, can be computed in polynomial time.

In this paper, we proposed an integrated model of both semantic-aware and contrast-aware saliency (SCA) combining both bottom-up and top-down cues for effective eye fixation prediction. The proposed (SCA) model contains two pathways. The first pathway is a deep neural network customized for semantic-aware saliency, which aims to capture the semantic information in images, especially for the presence of meaningful objects and object parts. The second pathway is based on on-line feature learning and information maximization, which learns an adaptive representation for the input and discovers the high contrast salient patterns within the image context. The two pathways characterize both long-term and short-term attention cues and are integrated using maxima normalization. Experimental results on artificial images and several benchmark dataset demonstrate the superior performance and better plausibility of the proposed model over both classic approaches and recent deep models.

Solving constrained combinatorial optimisation problems via MAP inference is often achieved by introducing extra potential functions for each constraint. This can result in very high order potentials, e.g. a 2nd-order objective with pairwise potentials and a quadratic constraint over all N variables would correspond to an unconstrained objective with an order-N potential. This limits the practicality of such an approach, since inference with high order potentials is tractable only for a few special classes of functions. We propose an approach which is able to solve constrained combinatorial problems using belief propagation without increasing the order. For example, in our scheme the 2nd-order problem above remains order 2 instead of order N. Experiments on applications ranging from foreground detection, image reconstruction, quadratic knapsack, and the M-best solutions problem demonstrate the effectiveness and efficiency of our method. Moreover, we show several situations in which our approach outperforms commercial solvers like CPLEX and others designed for specific constrained MAP inference problems.

In this paper we focus on Social Distance Games (SDGs), Coalition formation is a pervasive aspect of social life and an important subclass of HGs introduced in (Brânzei and it has been studied extensively in algorithmic game theory Larson 2011) where agent utilities are based on the concept using the natural model of Hedonic Games (HGs), introduced of social distance (i.e., the number of hops required to reach in (Dreze and Greenberg 1980) and further explored one node from another), which has become famous since in (Aziz, Brandt, and Harrenstein 2011; Aziz, Brandt, and Milgram's study on six degrees of separation. In SDGs the Seedig 2013; Banerjee, Konishi, and Sönmez 2001; Bogomolnaia utility of an agent is given by the average inverse distance and Jackson 2002; Elkind and Wooldridge 2009; from all the other nodes in her coalition, that is by her harmonic Elkind, Fanelli, and Flammini 2016; Gairing and Savani centrality (Boldi and Vigna 2014) divided by the size 2010). A HG consists of a set of selfish agents (humans, of the coalition. The basic idea is that the agents prefer to robots, software agents, etc.) having preferences over coalitions maintain ties with other agents who are close to them. The that might include them, regardless of which other utility formulation is a variant of the closeness centrality and coalitions may or may not be present. The outcome is a partition reflects the principle of homophily, that similarity breeds of the agent set into disjoint coalitions (or clusters), connection and people tend to form communities with similar referred to as a clustering or coalition structure.

Trivia is any fact about an entity which is interesting due to its unusualness, uniqueness or unexpectedness. Trivia could be successfully employed to promote user engagement in various product experiences featuring the given entity. A Knowledge Graph (KG) is a semantic network which encodes various facts about entities and their relationships. In this paper, we propose a novel approach called DBpedia Trivia Miner (DTM) to automatically mine trivia for entities of a given domain in KGs. The essence of DTM lies in learning an Interestingness Model (IM), for a given domain, from human annotated training data provided in the form of interesting facts from the KG. The IM thus learnt is applied to extract trivia for other entities of the same domain in the KG. We propose two different approaches for learning the IM - a) A Convolutional Neural Network (CNN) based approach and b) Fusion Based CNN (F-CNN) approach which combines both hand-crafted and CNN features. Experiments across two different domains - Bollywood Actors and Music Artists reveal that CNN automatically learns features which are relevant to the task and shows competitive performance relative to hand-crafted feature based baselines whereas F-CNN significantly improves the performance over the baseline approaches which use hand-crafted features alone. Overall, DTM achieves an F1 score of 0.81 and 0.65 in Bollywood Actors and Music Artists domains respectively.

We provide a brief overview on some hot topics in the area of evolutionary computation. Our main focus is on recent developments in the areas of combinatorial optimization and real-world applications. Furthermore, we highlight recent progress on the theoretical understanding of evolutionary computing methods.

Real world data is usually generated over multiple time periods associated with multiple labels, which can be represented as multiple labeled tensor sequences. These sequences are linked together, sharing some common features while exhibiting their own unique features. Conventional tensor factorization techniques are limited to extract either common or unique features, but not both simultaneously. However, both types of these features are important in many machine learning systems as they inherently affect the systems' performance. In this paper, we propose a novel supervised tensor factorization technique which simultaneously extracts ordered common and unique features. Classification results using features extracted by our method on CIFAR-10 database achieves significantly better performance over other factorization methods, illustrating the effectiveness of the proposed technique.

The introduction of smart meters has motivated the electricity industry to manage electrical demand, using dynamic pricing schemes such as real-time pricing. The overall aim of demand management is to minimize electricity generation and distribution costs while meeting the demands and preferences of consumers. However, rapidly scheduling consumption of large groups of households is a challenge. In this paper, we present a highly scalable approach to find the optimal consumption levels for households in an iterative and distributed manner. The complexity of this approach is independent of the number of households, which allows it to be applied to problems with large groups of households. Moreover, the intermediate results of this approach can be used by smart meters to schedule tasks with a simple randomized method.

Training machine leaning algorithms on augmented data fromdifferent related sources is a challenging task. This problemarises in several applications, such as the Internet of Things(IoT), where data may be collected from devices with differentsettings. The learned model on such datasets can generalizepoorly due to distribution bias. In this paper we considerthe problem of classifying unseen datasets, given several labeledtraining samples drawn from similar distributions. Weexploit the intrinsic structure of samples in a latent subspaceand identify landmarks, a subset of training instances fromdifferent sources that should be similar. Incorporating subspacelearning and landmark selection enhances generalizationby alleviating the impact of noise and outliers, as well asimproving efficiency by reducing the size of the data. However,since addressing the two issues simultaneously resultsin an intractable problem, we relax the objective functionby leveraging the theory of nonlinear projection and solve atractable convex optimisation. Through comprehensive analysis,we show that our proposed approach outperforms stateof-the-art results on several benchmark datasets, while keepingthe computational complexity low.