Search

Recently, wide applications of fuzzy set theory have attracted the attention of both researchers and practitioners. Fuzzy portfolio develops as a new area in the research field of investment portfolio. This paper investigates the major research hotspots, development trend, and evolution of fuzzy portfolio, which provides a systematic review of the current fuzzy portfolio literature. CiteSpace, the most commonly used bibliometrics software, is used in this article. According to the 602 articles with 15132 references, several conclusions can be summarized as follows: (1) Fuzzy portfolio becomes increasingly interdisciplinary with the connections among "Computer Science" and so on. (2) Most contributive authors are Markowitz and Zadeh. (3) South China University of Technology makes excellent performance in this research area and China is the most influential country. (4) European Journal of Operations Research is the cradle of plenty of crucial fuzzy portfolio investigations. (5) We find some research hotspots helpful to make scientific predictions of future trends by analyzing the keywords. By utilizing the effective bibliometric methods, we provide a comprehensive analysis and deep insights into the fuzzy portfolio research, enabling the individuals, especially the new beginners who are interested in this area to learn fuzzy portfolio, which will be of great help for their future explorations. [ABSTRACT FROM AUTHOR]

Negative correlation learning (NCL) is a neural network ensemble learning algorithm that introduces a correlation penalty term to the cost function of each individual network so that each neural network minimizes its mean square error/MSEI together with the correlation of the ensemble. This paper analyzes NCL and reveals that the training of NCL (when λ = 1) corresponds to training the entire ensemble as a single learning machine that only minimizes the MSE without regularization. This analysis explains the reason why NCL is prone to overtitting the noise in the training set. This paper also demonstrates that tuning the correlation parameter λ in NCL by cross validation cannot overcome the overfitting problem. The paper analyzes this problem and proposes the regularized negative correlation learning (RNCL) algorithm which incorporates an additional regularization term for the whole ensemble. RNCL decomposes the ensemble's training objectives, including MSE and regularization, into a set of sub-objectives, and each sub-objective is implemented by an individual neural network. In this paper, we also provide a Bayesian interpretation for RNCL and provide an automatic algorithm to optimize regularization parameters based on Bayesian inference. The RNCL formulation is applicable to any nonlinear estimator minimizing the MSE. The experiments on synthetic as well as real-world data sets demonstrate that RNCL achieves better performance than NCL, especially when the noise level is nontrivial in the data set. [ABSTRACT FROM AUTHOR]

This paper introduces strict fuzzy orderings in the framework of similarity-based fuzzy orderings, i.e. where a context of similarity/indistinguishability is given by means of a fuzzy equivalence relation. We consider how to construct strict fuzzy orderings from partial fuzzy orderings and vice versa. The appropriateness of the concepts introduced in this paper is underlined by theoretical results and examples. We observe that the strongest results are achieved if the underlying triangular norm induces an involutive residual negation. [ABSTRACT FROM AUTHOR]

The comparison of sets of objects is a research topic with applications in diverse fields such as computer science, biology and psychology. Since the introduction of the Jaccard index, many techniques have been proposed. This paper aims at extending an existing framework of comparison indices for sets. Firstly, the novel indices account for similarities between elements, rather than identity of elements as is the case for existing techniques. As a result, a richer framework of comparison indices is obtained. The use of fuzzy quantifiers in this framework is shown. Secondly, the machinery for sets is extended to the case of multisets, which results in two classes of comparison indices. The first class considers each element instance as a separate element, while the second class considers groups of elements instances as an atomic entity. The number of instances is then a property of this group, that is taken into account when calculating similarity between element groups. [ABSTRACT FROM AUTHOR]

This paper discusses and characterizes a distance function on the set of quasi choice functions. The derived distance function is in the spirit of the widely used Kemeny metric on binary relations but extends Kemeny’s use of the symmetric difference distance to set functions and hence to a more general model of choice. [ABSTRACT FROM AUTHOR]

The concepts of a tight set of points and an m-ovoid of a generalised quadrangle were unified recently by Bamberg, Law and Penttila under the title of intriguing sets. This unification was subsequently extended to polar spaces of arbitrary rank. The first part of this paper deals with a method of constructing intriguing sets of one polar space from those of another via field reduction. In the second part of this paper, we generalise an ovoid derivation of Payne and Thas to a derivation of intriguing sets. [ABSTRACT FROM AUTHOR]

This paper proposes a fuzzy mm-max neural network classifier with compensatory neurons (FMCNs). FMCN uses hyperbox fuzzy sets to represent the pattern classes. It is a supervised classification technique with new compensatory neuron architecture. The concept of compensatory neuron is inspired from the reflex system of human brain which takes over the control in hazardous conditions. Compensatory neurons (CNs) imitate this behavior by getting activated whenever a test sample falls in the overlapped regions amongst different classes. These neurons are capable to handle the hyperbox overlap and containment more efficiently. Simpson used contraction process based on the principle of minimal disturbance, to solve the problem of hyperbox overlaps. FMCN eliminates use of this process since it is found to be erroneous. FMCN is capable to learn the data online in a single pass through with reduced classification and gradation errors. One of the good features of FMCN is that its performance is less dependent on the initialization of expansion coefficient, i.e., maximum hyperbox size. The paper demonstrates the performance of FMCN by comparing it with fuzzy min-max neural network (FMNN) classifier and general fuzzy mm-max neural network (GFMN) classifier, using several examples. [ABSTRACT FROM AUTHOR]

In this paper, we develop a framework for reconfiguration of a discrete event system (DES) controller, which has a dynamic event observation set We will show the designed reconfiguration yields a more tolerable controller than the one designed in [5] Starting with a maximally permissive controller that has a full observation of its DES, we design a me ga-controller that monitors the observation set of the DES controller and its state continuously. Upon a change in the observation set, the mega-controller reconfigures the controller by a aggregation or disaggregation of the controller states. The mega-controller is also responsible for feedback function adjustments in the available observation set causes a conflict in control. We illustrate the reconfiguration procedures by an example. [ABSTRACT FROM AUTHOR]

A variety of methods for ranking fuzzy sets has been suggested. Generally, these methods fall under two main categories: a fuzzy-real sets mapping, a dominance relation of one fuzzy set over another. The original approach proposed in this paper belongs to the second category, as the ranking is based on the degree of inclusion in the MIN of two fuzzy numbers. The novelty lies mainly in the intuitive connection between the topological relationship of fuzzy shapes (triangles, trapezoids, etc.) and the measure of inclusion or dominance referred as inclusion index. This connection led to the classification of different topological relationships into classes identified by a binary pattern. This operation is referred to as Bitset Encoding. Consequently, the outcome of a ranking is already decided for most cases by merely identifying its pattern. Ultimately, the method is validated by the axiomatic system of Wang and Kerre and proven to be a reliable, efficient and strong potential alternative to the other prominent methods. [ABSTRACT FROM AUTHOR]

Decision problems in physics have been an active field of research for quite a few decades resulting in some interesting findings in recent years. However, such research investigations are based on a priori knowledge of theoretical computer science and the technical jargon of set theory. Here, I discuss a particular, but a significant, instance of how decision problems in physics can be realised without such specific prerequisites. I expose a hitherto unnoticed contradiction, that can be posed as as decision problem, concerning the oil drop experiment, thereby resolve it by refining the notion of 'existence' in physics. This consequently leads to the undecidability of the charge spectral gap through the notion of 'undecidable charges' which is in tandem with the completeness condition of a theory as was stated by Einstein, Podolsky and Rosen in their seminal work. Decision problems can now be realised in connection with basic physics, in general, rather than quantum physics, in particular, as per some recent claims. [ABSTRACT FROM AUTHOR]

Since the critical graphs of order n ≤ 14 were studied so far [1–4,6,11] , in this paper, we are concerned with 5-critical graphs of order 15. This paper gives the complete possible list of degree sequences of 5-critical graphs of order 15. [ABSTRACT FROM AUTHOR]

Many problems in Computer Science can be abstracted to the following question: given a set of objects and rules respectively, which new objects can be produced? In the paper, we consider a succinct version of the question: given a set of binary strings and several operations like conjunction and disjunction , which new binary strings can be generated? Although it is a fundamental problem, to the best of our knowledge, the problem hasn't been studied yet. In this paper, an O ( m 2 n ) algorithm is presented to determine whether a string s is representable by a set W , where n is the number of strings in W and each string has the same length m . However, looking for the minimum subset to represent a given string is shown to be NP -hard. Also, finding the smallest subset to represent each string in the original set is NP -hard. We establish tight inapproximability results and approximation algorithms for these NP -hard problems. In addition, we prove that counting the number of representable strings is # P -complete. We then explore how the problems change when the operator negation is available. For example, if the operator negation can be used, the counting problem is as simple as some power of 2. This difference may help us to better understand the problem. [ABSTRACT FROM AUTHOR]

The problem of automated theorem finding is one of the 33 basic research problems in automated reasoning which was originally proposed by Wos in 1988, and it is still an open problem. To solve the problem, an approach of forward deduction based on the strong relevant logics was proposed. Following the approach, this paper presents a systematic methodology for automated theorem finding. To show the effectiveness of our methodology, the paper presents two case studies, one is automated theorem finding in NBG set theory and the other is automated theorem finding in Peano's arithmetic. Some known theorems have been found in our case studies. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study the protein structure comparison problem where each protein is modeled as a sequence of 3D points, and a contact edge is placed between every two of these points that are sufficiently close. Given two proteins represented this way, our problem is to find a subset of points from each protein, and a bijective matching of points between these two subsets, with the objective of maximizing either (A) the size of the subsets (the LCP problem), or (B) the number of edges that exist simultaneously in both subsets (the CMO problem), under the requirement that only points within a specified proximity can be matched. It is known that the general CMO problem (without the proximity requirement) is hard to approximate. However, with the proximity requirement, it is known that if a minimum inter-residue distance is imposed on the input, approximate solutions can be efficiently obtained. In this paper we mainly show that the CMO problem under these conditions: (1) is NP-hard, but (2) allows a PTAS. The rest of this paper shows algorithms for the LCP problem which improve on known results. [Copyright &y& Elsevier]

Given a set of vectors F={ f,..., f} in a Hilbert space $\mathcal {H}$, and given a family $\mathcal {C}$ of closed subspaces of $\mathcal {H}$, the subspace clustering problem consists in finding a union of subspaces in $\mathcal {C}$ that best approximates (is nearest to) the data F. This problem has applications to and connections with many areas of mathematics, computer science and engineering, such as Generalized Principal Component Analysis (GPCA), learning theory, compressed sensing, and sampling with finite rate of innovation. In this paper, we characterize families of subspaces $\mathcal {C}$ for which such a best approximation exists. In finite dimensions the characterization is in terms of the convex hull of an augmented set $\mathcal {C}^{+}$. In infinite dimensions, however, the characterization is in terms of a new but related notion; that of contact half-spaces. As an application, the existence of best approximations from π( G)-invariant families $\mathcal {C}$ of unitary representations of Abelian groups is derived. [ABSTRACT FROM AUTHOR]

Abstract: Let be a simple graph with vertex set and edge set . A subset is a mixed dominating set if every element is either adjacent or incident to an element of . The mixed domination problem is to find a minimum mixed dominating set of . In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs. [Copyright &y& Elsevier]

Abstract: Upward-closed sets of integer vectors enjoy the merit of having a finite number of minimal elements, which is behind the decidability of a number of Petri net related problems. In general, however, such a finite set of minimal elements may not be effectively computable. In this paper, we develop a unified strategy for computing the sizes of the minimal elements of certain upward-closed sets associated with Petri nets. Our approach can be regarded as a refinement of a previous work by Valk and Jantzen (in which a necessary and sufficient condition for effective computability of the set was given), in the sense that complexity bounds now become available provided that a bound can be placed on the size of a witness for a key query. The sizes of several upward-closed sets that arise in the theory of Petri nets as well as in backward-reachability analysis in automated verification are derived in this paper, improving upon previous decidability results shown in the literature. [Copyright &y& Elsevier]

Abstract: In this paper, we show that it can be tested in polynomial time as to whether a scenario is an execution of a Petri net. This holds for a wide variety of Petri net classes, ranging from elementary nets to general inhibitor nets. Scenarios are given by causal structures expressing causal dependencies and concurrency among events. In the case of elementary nets and of place/transition nets, such causal structures are partial orders among transition occurrences. For several extended Petri net classes, the extension of partial orders to stratified order structures is considered. The algorithms are based on the representation of the non-sequential behavior of Petri nets by so-called token flow functions and a characterization of Petri net executions called token flow property. This property allows nontrivial transformations into flow optimization problems, which can be solved in polynomial time. The paper is a revised, consolidated and extended version of the conference papers [G. Juhás, R. Lorenz, J. Desel, Can I execute my scenario in your net?, in: G. Ciardo, P. Darondeau (Eds.), ICATPN, in: Lecture Notes in Computer Science, Springer, 2005, pp. 289–308; R. Lorenz, S. Mauser, R. Bergenthum, Testing the Executability of Scenarios in General Inhibitor Nets, in: ACSD, IEEE Computer Society, 2007, pp. 167–176] and includes parts of the habilitation thesis [R. Lorenz, Szenario-basierte Verifikation und Synthese von Perinetzen: Theorie und Anwendungen, Habilitation, 2006]. [Copyright &y& Elsevier]

Abstract: This paper deals with the inferrability of classes of E-pattern languages–also referred to as extended or erasing pattern languages–from positive data in Gold’s model of identification in the limit. The first main part of the paper shows that the recently presented negative result on terminal-free E-pattern languages over binary alphabets does not hold for other alphabet sizes, so that the full class of these languages is inferrable from positive data if and only if the corresponding terminal alphabet does not consist of exactly two distinct letters. The second main part yields the insight that the positive result on terminal-free E-pattern languages over alphabets with three or four letters cannot be extended to the class of general E-pattern languages. With regard to larger alphabets, the extensibility remains open. The proof methods developed for these main results do not directly discuss the (non-)existence of appropriate learning strategies, but they deal with structural properties of classes of E-pattern languages, and, in particular, with the problem of finding telltales for these languages. It is shown that the inferrability of classes of E-pattern languages is closely connected to some problems on the ambiguity of morphisms so that the technical contributions of the paper largely consist of combinatorial insights into morphisms in word monoids. [Copyright &y& Elsevier]

This paper presents an asymmetric subset- hood-product fuzzy neural inference system (ASuPFuNIS) that directly extends the SuPFuNIS model [1] by permitting signal and weight fuzzy sets to be modeled by asymmetric Gaussian membership functions. The asymmetric subsethood-product network admits both numeric as well as linguistic inputs. Input nodes, which act as tunable feature fuzzifiers, fuzzify numeric inputs with asymmetric Gaussian fuzzy sets; and linguistic inputs are presented as is. The antecedent and consequent labels of standard fuzzy if-then rules are represented as asymmetric Gaussian fuzzy connection weights of the network. The model uses mutual subsethood based activation spread and a product aggregation operator that works in conjunction with volume defuzzification in a gradient descent learning framework. Despite the increase in the number of free parameters, the proposed model performs better than SuPFuNIS, on various benchmarking problems, both in terms of the performance accuracy and architectural economy and compares excellently with other various existing models with a performance better than most of them. [ABSTRACT FROM AUTHOR]

In recent years, monotonic ordinal classification has increased the focus of attention for machine learning community. Real life problems frequently have monotonicity constraints. Many of the monotonic classifiers require that the input data sets satisfy the monotonicity relationships between its samples. To address this, a conventional strategy consists of relabeling the input data to achieve complete monotonicity. As an alternative, we explore the use of preprocessing algorithms without modifying the class label of the input data. In this paper we propose the use of training set selection to choose the most effective instances which lead the monotonic classifiers to obtain more accurate and efficient models, fulfilling the monotonic constraints. To show the benefits of our proposed training set selection algorithm, called MonTSS, we carry out an experimentation over 30 data sets related to ordinal classification problems. [ABSTRACT FROM AUTHOR]

Let M be a metric space and P a finite set of points in M. The Steiner ratio in M is defined to be ρ(M) = inf{Ls(P)/Lm(P)\P ⊂ M}. where Ls,(P) and Lm(P) are the lengths of the Steiner minimal tree and the minimal spanning tree on P, respectively. In this paper, we study various conjectures on ρ(M). In particular, we show that for n-dimensional Euclidean space /Rn , ρ(/Rn) » 0.615. [ABSTRACT FROM AUTHOR]

In 1974 Lawson and Hanson produced a seminal active set strategy to solve least-squares problems with non-negativity constraints that remains popular today. In this paper we present TNT-NN, a new active set method for solving non-negative least squares (NNLS) problems. TNT-NN uses a different strategy not only for the construction of the active set but also for the solution of the unconstrained least squares sub-problem. This results in dramatically improved performance over traditional active set NNLS solvers, including the Lawson and Hanson NNLS algorithm and the Fast NNLS (FNNLS) algorithm, allowing for computational investigations of new types of scientific and engineering problems. For the small systems tested (5000 × 5000 or smaller), it is shown that TNT-NN is up to 95 × faster than FNNLS. Recent studies in rock magnetism have revealed a need for fast NNLS algorithms to address large problems (on the order of 10 5 × 10 5 or larger). We apply the TNT-NN algorithm to a representative rock magnetism inversion problem where it is 60× faster than FNNLS. We also show that TNT-NN is capable of solving large (45000 × 45000) problems more than 150 × faster than FNNLS. These large test problems were previously considered to be unsolvable, due to the excessive execution time required by traditional methods. [ABSTRACT FROM AUTHOR]

In the last decades, one issue that has received a lot of attention in classification problems is how to obtain better classifications. This problem becomes even more complicated when the number of classes is high. In this multiclass scenario, it is assumed that the class labels are independent of each other, and thus, most techniques and methods proposed to improve the performance of the classifiers rely on it. An alternative way to address the multiclass problem is to hierarchically distribute the classes in a collection of multiclass subproblems by reducing the number of classes involved in each local subproblem. In this paper, we propose a new method for inducing a class hierarchy from the confusion matrix of a multiclass classifier. Then, we use the class hierarchy to learn a tree-like hierarchy of classifiers for solving the original multiclass problem in a similar way as the top-down hierarchical classification approach does for working with hierarchical domains. We experimentally evaluate the proposal on a collection of multiclass datasets showing that, in general, the generated hierarchies not only outperforms the original (flat) classification but also hierarchical approaches based on other alternative ways of constructing the class hierarchy. [ABSTRACT FROM AUTHOR]

Parameterized Approximation is a topic of considerable interest in the field of Parameterized Complexity. In the past decade, new color coding-related techniques, including the breakthrough representative sets technique, have been proven extremely powerful in the design of fast parameterized algorithms. Furthermore, packing problems, which are often solved via color coding-related techniques, have enjoyed a race towards obtaining the fastest parameterized algorithms that solve them. Therefore, it is natural to ask whether packing problems admit efficient parameterized approximation algorithms. In this paper, we answer this question affirmatively. We present tradeoffs that improve the running times of algorithms for well-known special cases of the 3 -Set k -Packing problem at the cost of their accuracy. Consider a packing problem for which there is no known algorithm with approximation ratio α , and a parameter k . If the value of an optimal solution is at least k , we seek a solution of value at least αk ; otherwise, we seek an arbitrary solution. Clearly, if the best known parameterized algorithm that finds a solution of value t runs in time O ⁎ ( f ( t ) ) for some function f , we are interested in running times better than O ⁎ ( f ( α k ) ) . Our main contribution lies in the adaptation of notions fundamental to the representative sets technique to the design of approximation algorithms: We introduce the definition of “approximate lopsided universal sets”, combine partial executions of representative sets-based algorithms with approximation algorithms, and adapt the iterative expansion framework (in the context of representative sets) to the design of parameterized approximation algorithms. Our ideas are intuitive, and may be relevant to the design of other parameterized approximation algorithms. [ABSTRACT FROM AUTHOR]

Metric spaces and their various generalizations occur frequently in computer science applications. This is the reason why, in this paper, we introduced and studied the concept of fuzzy b-metric space, generalizing, in this way, both the notion of fuzzy metric space introduced by I. Kramosil and J. Michálek and the concept of b-metric space. On the other hand, we introduced the concept of fuzzy quasi-bmetric space, extending the notion of fuzzy quasi metric space recently introduced by V. Gregori and S. Romaguera. Finally, a decomposition theorem for a fuzzy quasipseudo- b-metric into an ascending family of quasi-pseudo-b-metrics is established. The use of fuzzy b-metric spaces and fuzzy quasi-b-metric spaces in the study of denotational semantics and their applications in control theory will be an important next step. [ABSTRACT FROM AUTHOR]

In the committee coordination problem , a committee consists of a set of professors and committee meetings are synchronized, so that each professor participates in at most one committee meeting at a time. In this paper, we propose two snap-stabilizing distributed algorithms for the committee coordination. Snap-stabilization is a versatile property which requires a distributed algorithm to efficiently tolerate transient faults. Indeed, after a finite number of such faults, a snap-stabilizing algorithm immediately operates correctly, without any external intervention. We design snap-stabilizing committee coordination algorithms enriched with some desirable properties related to concurrency , (weak) fairness , and a stronger synchronization mechanism called 2- Phase Discussion . In our setting, all processes are identical and each process has a unique identifier. The existing work in the literature has shown that (1) in general, fairness cannot be achieved in committee coordination, and (2) it becomes feasible if each professor waits for meetings infinitely often. Nevertheless, we show that even under this latter assumption, it is impossible to implement a fair solution that allows maximal concurrency . Hence, we propose two orthogonal snap-stabilizing algorithms, each satisfying 2-phase discussion, and either maximal concurrency or fairness. The algorithm that implements fairness requires that every professor waits for meetings infinitely often. Moreover, for this algorithm, we introduce and evaluate a new efficiency criterion called the degree of fair concurrency . This criterion shows that even if it does not satisfy maximal concurrency, our snap-stabilizing fair algorithm still allows a high level of concurrency. [ABSTRACT FROM AUTHOR]

In 1998, Chartrand, E. Salehi and P. Zhang introduced the concept of graph partition dimension. This is a variant of graph metric dimension concept introduced independently by Slater in 1975 and Harary & Melter in 1976. In this paper, we determine the partition dimension of specific classes of trees, namely homogeneous caterpillars and homogeneous banana trees. In particular, we characterize all trees in these classes with partition dimension three. [ABSTRACT FROM AUTHOR]

The assumption that the training and testing samples are drawn from the same distribution is violated under covariate shift setting, and most algorithms for the covariate shift setting try to first estimate distributions and then reweight samples based on the distributions estimated. Due to the difficulty of estimating a correct distribution, previous methods can not get good classification performance. In this paper, we firstly present two types of covariate shift problems. Rather than estimating the distributions, we then desire an effective method to select a maximum subset following the target testing distribution based on feature space split from the auxiliary set or the target training set. Finally, we prove that our subset selection method can consistently deal with both scenarios of covariate shift. Experimental results demonstrate that training a classifier with the selected maximum subset exhibits good generalization ability and running efficiency over those of traditional methods under covariate shift setting. [ABSTRACT FROM AUTHOR]

A detailed and extensive empirical study of empty prediction of multi-label classification is conducted in this paper and to the best of our knowledge this work is the first empirical study of this problem. Total 8 state of the art multi-label classification methods, BR, CC, CLR, HOMER, RAkEL, ECC, MLkNN, and BRkNN, are compared on 11 datasets. The empirical results clearly answer the two research questions, (1) whether empty prediction problems happen in commonly used state of the art multi-label classification methods and what their empty prediction rates (EPR) on different test sets are and (2) what multi-label classification methods are with overall highest/lowest EPRs. Specifically, it is empirically shown that every method considered all made empty predictions on different datasets. In addition, several thresholding methods which in theory can solve empty prediction are compared. The clear answers to the two research questions and the experimental findings are the main contributions of this work to multi-label classification. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the concept of smg-closed sets in biminimal structure space and a new notion of a pair wise smg-closed set is defined and studied some of its properties. [ABSTRACT FROM AUTHOR]

The minimum eccentric dominating graph MmD E (G) of a graph G is defined to be the intersection graph on the minimum eccentric dominating sets of G. In this paper minimum eccentric dominating graph of some families of graphs are studied. [ABSTRACT FROM AUTHOR]

The advice complexity of an online problem describes the additional information both necessary and sufficient for online algorithms to compute solutions of a certain quality. In this model, an oracle inspects the input before it is processed by an online algorithm. Depending on the input string, the oracle prepares an advice bit string that is accessed sequentially by the algorithm. The number of advice bits that are read to achieve some specific solution quality can then serve as a fine-grained complexity measure. The main contribution of this paper is to study a powerful method for proving lower bounds on the number of advice bits necessary. To this end, we consider the string guessing problem as a generic online problem and show a lower bound on the number of advice bits needed to obtain a good solution. We use special reductions from string guessing to improve the best known lower bound for the online set cover problem and to give a lower bound on the advice complexity of the online maximum clique problem. [ABSTRACT FROM AUTHOR]

We study Gentzen-style proof theory of the finitary version of the coalgebraic logic introduced by L. Moss. The logic captures the behaviour of coalgebras for a large class of set functors. The syntax of the logic, defined uniformly with respect to a finitary coalgebraic type functor T , uses a single modal operator ∇ T of arity given by the functor T itself, and its semantics is defined in terms of a relation lifting functor T ¯ . An axiomatization of the logic, consisting of modal distributive laws, has been given together with an algebraic completeness proof in work of C. Kupke, A. Kurz and Y. Venema. In this paper, following our previous work on structural proof theory of the logic in the special case of the finitary powerset functor, we present cut-free, one- and two-sided sequent calculi for the finitary version of Moss' coalgebraic logic for a general finitary functor T in a uniform way. For the two-sided calculi to be cut-free we use a language extended with the boolean dual of the nabla modality. [ABSTRACT FROM AUTHOR]

Abstract: A challenge for Linked Data is to link instances from different data sources that denote the same real-world object. Millions of high-quality owl:sameAs linkages have been generated, but potential ones are still considerable. Traditional similarity-based methods to this data linkage problem do not scale well since they exhaustively compare every pair of instances. In this paper, we propose an automatic approach to data linkage generation for Linked Data. Specifically, a highly-accurate training set is automatically generated based on equivalence reasoning and common prefix blocking. The contexts of the instances in the training set, after extracting, are pairwise matched in order to learn discriminative property pairs supporting linkage discovery. For a particular class pair and a pay-level-domain pair, the discriminability of each property pair is measured, and a few property pairs with high discriminability are aggregated in order to be reused in the future to link instances between the same classes and domains. The experimental results show that our approach achieves good accuracy against some complex methods in two OAEI tests and the BTC2011 dataset. [Copyright &y& Elsevier]

Abstract: Recently a logic programming language AC was proposed by Mellarkod et al. [1] to integrate answer set programming and constraint logic programming. Soon after that, a clingcon language integrating answer set programming and finite domain constraints, as well as an ezcsp language integrating answer set programming and constraint logic programming were introduced. The development of these languages and systems constitutes the appearance of a new AI subarea called constraint answer set programming. All these languages have something in common. In particular, they aim at developing new efficient inference algorithms that combine traditional answer set programming procedures and other methods in constraint programming. Yet, the exact relation between the constraint answer set programming languages and the underlying systems is not well understood. In this paper we address this issue by formally stating the precise relation between several constraint answer set programming languages – AC, clingcon, ezcsp – as well as the underlying systems. [Copyright &y& Elsevier]

Contrary to the notion of a set or a tuple, a multiset is an unordered collection of elements which do not need to be different. As multisets are already widely used in combinatorics and computer science, the aim of this paper is to get on track to algebraic multiset theory. We consider generalizations of known results that hold for equivalence and order relations on sets and get several properties that are specific to multisets. Furthermore, we exemplify the novelty that brings this concept by showing that multisets are suitable to represent partial orders. Finally, after introducing the notion of an algebra on multisets, we prove that two algebras on multisets, whose root algebras are isomorphic, are in general not isomorphic. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we identify a minimum width rectangular annulus that encloses a given set of points in a plane. We propose an time and space algorithm for this problem. To the best of our knowledge this is the first sub-cubic algorithm for a rectangular annulus for arbitrary orientation. [Copyright &y& Elsevier]

Abstract: In this paper, we present an -time algorithm to decide whether a graph of maximum degree has an edge dominating set of size at most or not, which is based on enumeration of vertex covers and improves all previous results on this problem. We first enumerate partial vertex covers of size at most and then construct an edge dominating set based on each vertex cover to find a required edge dominating set. To effectively enumerate vertex covers, we adopt a branch-and-reduce method, and use some techniques, such as ‘pseudo-cliques’ and ‘amortized transfer of cliques,’ to analyze the running time bound. [Copyright &y& Elsevier]

Abstract: Matching is one of the most extensively studied areas in Computer Science and is interesting from the combinatorial point of view as well. A matching in a graph is a subset M of edges, no two of which have a vertex in common. A matching M is said to be perfect if every vertex in G is an endpoint of one of the edges in M. The excessive index of a graph G is the minimum number of perfect matchings to cover the edge set of G. The study of excessive index has a number of applications particularly in scheduling theory. In this paper we determine the excessive index for certain classes of graphs including augmented butterfly network and honeycomb network. We also prove that the excessive index does not exist for butterfly and Benes networks. [Copyright &y& Elsevier]

Abstract: In this paper, we consider a variant of the knapsack problem. There are two knapsacks with probably different capacities, owned by two agents respectively. Given a set of items, each with a fixed size and a profit. The two agents select items and pack them into their own knapsacks under the capacity constraint. Same items can be packed simultaneously to different knapsacks. However, in this case the profit of such items may vary. One agent packs items into his knapsack to maximize the total profit, while another agent can only pack items into his knapsack as well but he cares about the total profits of items packed into two knapsacks. The latter agent is a leader while the former is a follower. We aim at designing an approximation algorithm for the leader assuming that the follower is selfish. For different settings we provide approximation results. [Copyright &y& Elsevier]

Abstract: An -labeling of a graph is a function from the vertex set to the set of all non-negative integers such that if and if , where denotes the distance between and in . The -labeling number of is the smallest number such that has an -labeling with . This paper considers the -labeling number of the modular product of two graphs and it is proved that Griggs and Yeh’s conjecture is true for the modular product of two graphs with minor exceptions. [Copyright &y& Elsevier]

Abstract: In this paper, we study algebraic aggregate computations in Sensor Networks. The main contribution is the presentation of an early-stopping protocol that computes the average function under a harsh model of the conditions under which sensor nodes operate. This protocol is shown to be time-optimal in the presence of infrequent failures. The approach followed saves time and energy by the computation relying on a small network of delegate nodes that can be rebuilt fast in case of node failures and communicate using a collision-free schedule. Delegate nodes run two protocols simultaneously, namely, a collection/dissemination tree-based algorithm, which is shown to be optimal, and a mass-distribution algorithm. Both algorithms are analyzed under a model where the frequency of failures is a parameter. Other aggregate computation algorithms can be easily derived from this protocol. To the best of our knowledge, this is the first optimal early-stopping algorithm for aggregate computations in Sensor Networks. [Copyright &y& Elsevier]

Abstract: Regression via classification (RvC) is a method in which a regression problem is converted into a classification problem. A discretization process is used to covert continuous target value to classes. The discretized data can be used with classifiers as a classification problem. In this paper, we use a discretization method, Extreme Randomized Discretization (ERD), in which bin boundaries are created randomly to create ensembles. We present two ensemble methods for RvC problems. We show theoretically that the proposed ensembles for RvC perform better than RvC with the equal-width discretization method. We also show the superiority of the proposed ensemble methods experimentally. Experimental results suggest that the proposed ensembles perform competitively to the method developed specifically for regression problems. [Copyright &y& Elsevier]

Abstract: Since the concept of IFS-probability was proposed, the probability theory for IF-events has been constructed. In this paper the concepts of IVFS-probability and IVIFS-probability are proposed for the first time. And the representation theorem for IVFS-probability is given. Furthermore, the relationships between IFS-probability, IVFS-probability and IVIFS-probability are discussed. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the fault-tolerant edge-bipancyclicity of an -dimensional star graph . Given a set comprised of faulty vertices and/or edges in with and any fault-free edge in , we show that there exist cycles of every even length from 6 to in containing , where . Our result is optimal because the star graph is both bipartite and regular with the common degree . The length of the longest fault-free cycle in the bipartite is in the worst case, where all faulty vertices are in the same partite set. We also provide some sufficient conditions from which longer cycles with length from to can be embedded. [Copyright &y& Elsevier]

Abstract: We introduce the vertex cover () problem, that is, the problem of finding a minimum weight set such that the graph has no , where is a path with vertices. The problem also has its application background. In this paper, we first show that the problem is NP-hard for any integer . Then we restrict our attention to the problem and give a 2-approximation algorithm using the primal–dual method. [Copyright &y& Elsevier]

Abstract: Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with as few sets of the family as possible. The variations of covering problems include well-known problems like Set Cover, Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets. In this paper we study partial covering problems in graphs in the realm of parameterized complexity. Classical (non-partial) version of all these problems has been intensively studied in planar graphs and in graphs excluding a fixed graph H as a minor. However, the techniques developed for parameterized version of non-partial covering problems cannot be applied directly to their partial counterparts. The approach we use, to show that various partial covering problems are fixed parameter tractable on planar graphs, graphs of bounded local treewidth and graph excluding some graph as a minor, is quite different from previously known techniques. The main idea behind our approach is the concept of implicit branching. We find implicit branching technique to be interesting on its own and believe that it can be used for some other problems. [Copyright &y& Elsevier]

Abstract: In the -set agreement problem, each process (in a set of processes) proposes a value and has to decide a proposed value in such a way that at most different values are decided. While this problem can easily be solved in asynchronous systems prone to process crashes when , it cannot be solved when . For several years, the failure-detector-based approach has been investigated to circumvent this impossibility. While the weakest failure detector class to solve the -set agreement problem in read/write shared memory systems has recently been discovered (PODC 2009), the situation is different in message-passing systems where the weakest failure detector classes are known only for the extreme cases (consensus) and (set agreement). This paper presents four contributions whose aim is to help pave the way to discover the weakest failure detector class for -set agreement in message-passing systems. These contributions are the following. (a) The first is a new failure detector class, denoted , that is such that (the weakest class for ), and (the weakest class for ). (b) The second is an investigation of the structure of that shows that is the combination of two failure detector classes (that is new) and (they generalize the previous “quorums” and “eventual leaders” failure detector classes, respectively). (c) The third contribution concerns that is shown to be a necessary requirement (as far as information on failure is concerned) to solve the -set agreement problem in message-passing systems. (d) Finally, the last contribution is a -based algorithm that solves the -set agreement problem. This algorithm provides us with a new algorithmic insight on the way the -set agreement problem can be solved in asynchronous message-passing systems. It is hoped that these contributions will help discover the weakest failure detector class for -set agreement in message-passing systems. [Copyright &y& Elsevier]

Abstract: Frequent-itemset mining only considers the frequency of occurrence of the items but does not reflect any other factors, such as price or profit. Utility mining is an extension of frequent-itemset mining, considering cost, profit or other measures from user preference. Traditionally, the utility of an itemset is the summation of the utilities of the itemset in all the transactions regardless of its length. The average utility measure is thus adopted in this paper to reveal a better utility effect of combining several items than the original utility measure. It is defined as the total utility of an itemset divided by its number of items within it. The average-utility itemsets, as well as the original utility itemsets, does not have the “downward-closure” property. A mining algorithm is then proposed to efficiently find the high average-utility itemsets. It uses the summation of the maximal utility among the items in each transaction with the target itemset as the upper bound to overestimate the actual average utilities of the itemset and processes it in two phases. As expected, the mined high average-utility itemsets in the proposed way will be fewer than the high utility itemsets under the same threshold. The proposed approach can thus be executed under a larger threshold than the original, thus with a more significant and relevant criterion. Experimental results also show the performance of the proposed algorithm. [Copyright &y& Elsevier]