Arama Sonuçları
Listeleniyor 1 - 6 / 6
Yayın On the maximum cardinality cut problem in proper interval graphs and related graph classes(Elsevier B.V., 2022-01-04) Boyacı, Arman; Ekim, Tınaz; Shalom, MordechaiAlthough it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this work we consider the parameterized complexity of this problem. We show that the maximum cardinality cut problem in proper/unit interval graphs is FPT when parameterized by the maximum number of non-empty bubbles in a column of its bubble model. We then generalize this result to a more general graph class by defining new parameters related to the well-known clique-width parameter. Specifically, we define an (?,?,?)-clique-width decomposition of a graph as a clique-width decomposition in which at each step the following invariant is preserved: after discarding at most ? labels, a) every label consists of at most ? sets of twin vertices, and b) all the labels together induce a graph with independence number at most ?. We show that for every two constants ?,?>0 the problem is FPT when parameterized by ? plus the smallest width of an (?,?,?)-clique-width decomposition.Yayın Incremental construction of classifier and discriminant ensembles(Elsevier Science Inc, 2009-04-15) Ulaş, Aydın; Semerci, Murat; Yıldız, Olcay Taner; Alpaydın, Ahmet İbrahim EthemWe discuss approaches to incrementally construct an ensemble. The first constructs an ensemble of classifiers choosing a subset from a larger set, and the second constructs an ensemble of discriminants, where a classifier is used for some classes only. We investigate criteria including accuracy, significant improvement, diversity, correlation, and the role of search direction. For discriminant ensembles, we test subset selection and trees. Fusion is by voting or by a linear model. Using 14 classifiers on 38 data sets. incremental search finds small, accurate ensembles in polynomial time. The discriminant ensemble uses a subset of discriminants and is simpler, interpretable, and accurate. We see that an incremental ensemble has higher accuracy than bagging and random subspace method; and it has a comparable accuracy to AdaBoost. but fewer classifiers.Yayın Crossing minimization in weighted bipartite graphs(Elsevier B.V., 2009-12) Çakıroğlu, Olca Arda; Erten, Cesim; Karataş, Ömer; Sözdinler, MelihGiven a bipartite graph G = (L0, L1, E) and a fixed ordering of the nodes in L0, the problem of finding an ordering of the nodes in L1 that minimizes the number of crossings has received much attention in literature. The problem is NP-complete in general and several practically efficient heuristics and polynomial-time algorithms with a constant approximation ratio have been suggested. We generalize the problem and consider the version where the edges have nonnegative weights. Although this problem is more general and finds specific applications in automatic graph layout problems similar to those of the unweighted case, it has not received as much attention. We provide a new technique that efficiently approximates a solution to this more general problem within a constant approximation ratio of 3. In addition we provide appropriate generalizations of some common heuristics usually employed for the unweighted case and compare their performances.Yayın The two-level economic lot sizing problem with perishable items(Elsevier, 2016-05-01) Önal, MehmetWe present an economic lot sizing model of a supply chain for the procurement and distribution of a perishable item. We assume that the consumers always buy the item that lasts longer. We show that determining optimal procurement and transfer plan is NP-hard, and present polynomial time solvable special cases.Yayın Hierarchical b-Matching(Springer Science and Business Media Deutschland GmbH, 2021) Emek, Yuval; Kutten, Shay; Shalom, Mordechai; Zaks, ShmuelA matching of a graph is a subset of edges no two of which share a common vertex, and a maximum matching is a matching of maximum cardinality. In a b-matching every vertex v has an associated bound bv, and a maximum b-matching is a maximum set of edges, such that every vertex v appears in at most bv of them. We study an extension of this problem, termed Hierarchical b-Matching. In this extension, the vertices are arranged in a hierarchical manner. At the first level the vertices are partitioned into disjoint subsets, with a given bound for each subset. At the second level the set of these subsets is again partitioned into disjoint subsets, with a given bound for each subset, and so on. We seek for a maximum set of edges, that obey all bounds (that is, no vertex v participates in more than bv edges, then all the vertices in one subset do not participate in more that subset’s bound of edges, and so on hierarchically). This is a sub-problem of the matroid matching problem which is NP -hard in general. It corresponds to the special case where the matroid is restricted to be laminar and the weights are unity. A pseudo-polynomial algorithm for the weighted laminar matroid matching problem is presented in [8]. We propose a polynomial-time algorithm for Hierarchical b-matching, i.e. the unweighted laminar matroid matching problem, and discuss how our techniques can possibly be generalized to the weighted case.Yayın ANN activation function estimators for homomorphic encrypted inference(Institute of Electrical and Electronics Engineers Inc., 2025-06-13) Harb, Mhd Raja Abou; Çeliktaş, BarışHomomorphic Encryption (HE) enables secure computations on encrypted data, facilitating machine learning inference in sensitive environments such as healthcare and finance. However, efficiently handling non-linear activation functions, specifically Sigmoid and Tanh, remains a significant computational challenge for encrypted inference using Artificial Neural Networks (ANNs). This study introduces a lightweight, ANN-based estimator designed to accurately approximate activation functions under homomorphic encryption. Unlike traditional polynomial and piecewise linear approximations, the proposed ANN estimators achieve superior accuracy with lower computational overhead associated with bootstrapping or high-degree polynomial techniques. These estimators are trained on plaintext data and seamlessly integrated into encrypted inference pipelines, significantly outperforming conventional methods. Experimental evaluations demonstrate notable improvements, with ANN estimators enhancing accuracy by approximately 2% for Sigmoid and up to 73% for Tanh functions, improving F1-scores by approximately 2% for Sigmoid and up to 88% for Tanh, and markedly reducing Mean Square Error (MSE) by up to 96% compared to polynomial approximations. The ANN estimator achieves an accuracy of 97.70% and an AUC of 0.9997 when integrated into a CNN architecture on the MNIST dataset, and an accuracy of 85.25% with an AUC of 0.9459 on the UCI Heart Disease dataset during ciphertext inference. These results underscore the estimator’s practical effectiveness and computational feasibility, making it suitable for secure and efficient ANN inference in encrypted environments.
