<abstract xmlns="http://www.w3.org/1999/xhtml">In this paper we investigate the online hypergraph coloring problem with rejection, where the algorithm is allowed to reject a vertex instead of coloring it but each vertex has a penalty which has to be paid if it is not colored. The goal is to minimize the sum of the number of the used colors for the accepted vertices and the total penalty paid for the rejected ones. We study the online problem which means that the algorithm receives the vertices of the hypergraph in some order <italic>v</italic>1, . . . , <italic>vn</italic> and it must decide about <italic>vi</italic> by only looking at the subhypergraph <italic>Hi</italic> = (<italic>Vi</italic>, <italic>Ei</italic>) where <italic>Vi</italic> = {<italic>v</italic>1, . . . , <italic>vi</italic>} and E<italic>i</italic> contains the edges of the hypergraph which are subsets of <italic>Vi</italic>. We consider two models: in the full edge model only the edges where each vertex is accepted must be well-colored, in the trace model the subsets of the edges formed by the accepted vertices must be well colored as well. We consider proper and conflict free colorings. We present in each cases optimal online algorithms in the sense that they achieve asymptotically the smallest possible competitive ratio.</abstract>

University of Szeged, Institute of Informatics

Online hypergraph coloring with rejection

<abstract xmlns="http://www.w3.org/1999/xhtml">Semi-supervised learning has become an important and thoroughly studied subdomain of machine learning in the past few years, because gathering large unlabeled data is almost costless, and the costly human labeling process can be minimized by semi-supervision. Label propagation is a transductive semi-supervised learning method that operates on the—most of the time undirected—data graph. It was introduced in [8] and since many variants were proposed. However, the base algorithm has two variants: the first variant presented in [8] and its slightly modified version used afterwards, e.g. in [7]. This paper presents and compares the two algorithms—both theoretically and experimentally—and also tries to make a recommendation which variant to use.</abstract>

A note on label propagation for semi-supervised learning

<abstract xmlns="http://www.w3.org/1999/xhtml">The Bin Packing problem is a well-known and highly investigated problem in the computer science: we have <italic>n</italic> items given with their sizes, and we want to assign them to unit capacity bins such, that we use the minimum number of bins.In this paper, some generalizations of this problem are considered, where there are some additional stackability constraints defining that certain items can or cannot be packed on each other. The corresponding model in the literature is the Bin Packing Problem with Conflicts (BPPC), where this additional constraint is defined by an undirected conflict graph having edges between items that cannot be assigned to the same bin. However, we show some practical cases, where this conflict is directed, meaning that the items can be assigned to the same bin, but only in a certain order. Two new models are introduced for this problem: Bin Packing Problem with Hanoi Conflicts (BPPHC) and Bin Packing Problem with Directed Conflicts (BPPDC). In this work, the connection of the three conflict models is examined in detail.We have investigated the complexity of the new models, mainly the BPPHC model, in the special case where each item have the same size. We also considered two cases depending on whether re-ordering the items is allowed or not.We show that for the online version of the BPPHC model with unit size items, every Any-Fit algorithm gives not better than <inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/ausi-2015-0011_i1.jpg"></inline-graphic>-competitive, when it is forbidden for the optimum to re-order the items, even if only 2 stackability classes, called Hanoi classes, are applied. This lower bound is generalized for arbitrary number of Hanoi classes. However, we also prove, that asymptotically the First-Fit algorithm is 1-competitive for this case.Finally, we introduce an algorithm for the offline version of the BPPHC model with unit size items, which has polynomial time complexity, if the number of the Hanoi classes and the capacity of the bins are constant.</abstract>

Bin packing with directed stackability conflicts

<abstract xmlns="http://www.w3.org/1999/xhtml">Pairwise comparison matrices are of key importance in multi-attribute decision analysis. A matrix is incomplete if some of the elements are missing. The eigenvector method, to derive the weights of criteria, can be generalized for the incomplete case by using the least inconsistent completion of the matrix. If inconsistency is indexed by CR, defined by Saaty, it leads to the minimization of the Perron eigenvalue. This problem can be transformed to a convex optimization problem. The paper presents a method based on the Newton iteration, univariate and multivariate. Numerical examples are also given.</abstract>

Minimization of the Perron eigenvalue of incomplete pairwise comparison matrices by Newton iteration

<abstract xmlns="http://www.w3.org/1999/xhtml">If <italic>k</italic> ≥ 1, then the <italic>global degree set</italic> of a k-partite graph <italic>G</italic> = (<italic>V</italic>1, <italic>V</italic>2, . . . , <italic>V</italic>k, <italic>E</italic>) is the set of the distinct degrees of the vertices of <italic>G</italic>, while if <italic>k</italic> ≥ 2, then the <italic>distributed degree set</italic> of <italic>G</italic> is the family of the <italic>k</italic> degree sets of the vertices of the parts of <italic>G</italic>. We propose algorithms to construct bipartite and tripartite graphs with prescribed global and distributed degree sets consisting from <italic>arbitrary</italic> nonnegative integers. We also present a review of the similar known results on digraphs.</abstract>

Eötvös Loránd University, Faculty of Informatics, Budapest, Hungary

Tripartite graphs with given degree set

<abstract xmlns="http://www.w3.org/1999/xhtml">Behind the link selection problem there is a practical problem that aims to check efficiently the vehicles on a road network. The checking process is to be realized with license plate reading cameras for checking the valid vignette of vehicles using that part of the network. However this problem should be defined generally and the methods of obtaining a solution can be applied to a wider range of problems independent of the original problem. This paper defines the link selection problem with directed graph, it shows the NP-hard complexity and it gives a heuristic and binary integer programming models to solve the problem. These two kinds of approaches allow us to examine and qualify the heuristic. The computational results of the methods are compared with different sizes of problems.</abstract>

Empirical study of the greedy heuristic as applied to the link selection problem

AHEAD OF PRINT

Volume 15 (2023): Issue 2 (December 2023)

Volume 15 (2023): Issue 1 (August 2023)

Volume 14 (2022): Issue 2 (December 2022)

Volume 14 (2022): Issue 1 (August 2022)

Volume 13 (2021): Issue 2 (December 2021)

Volume 13 (2021): Issue 1 (June 2021)

Volume 12 (2020): Issue 2 (December 2020)

Volume 12 (2020): Issue 1 (July 2020)

Volume 11 (2019): Issue 2 (December 2019)

Volume 11 (2019): Issue 1 (August 2019)

Volume 10 (2018): Issue 2 (December 2018)

Volume 10 (2018): Issue 1 (August 2018)

Volume 9 (2017): Issue 2 (December 2017)

Volume 9 (2017): Issue 1 (July 2017)

Volume 8 (2016): Issue 2 (December 2016)

Volume 8 (2016): Issue 1 (June 2016)

Volume 7 (2015): Issue 2 (December 2015)

Volume 7 (2015): Issue 1 (June 2015)

Volume 6 (2014): Issue 2 (December 2014)

Volume 6 (2014): Issue 1 (June 2014)

Volume 5 (2013): Issue 2 (December 2013)

Volume 5 (2013): Issue 1 (July 2013)

Acta Universitatis Sapientiae, Informatica

Acta Universitatis Sapientiae Informatica publishes peer-reviewed, high-quality original papers and surveys in English, in all areas of Computer Science and allied fields. The papers must be self-contained, including the purpose of the research, the basic definitions, the antecedents of the research, the presentation of the state-of-the-art and novel contributions. The articles must contain sufficient references to give the reader a broad view of the studied subject.  Articles must follow the technical requirements described in the Information for Authors. Please note, that if an article fails to do so, it will be rejected without peer-review.  The corresponding author is responsible for obtaining the permission of coauthors and of the authorities or institutions, if needed, for publication, the Editorial Board is disclaiming any responsibility.  The papers have to be prepared carefully, and must include the relevant keywords. References should be listed alphabetically based on the Instruction for Authors given at the address www.acta.sapientia.ro/acta-info/informatica-main.htm.  Why subscribe and read  The journal publishes papers in all fields of Computer Science, so it can satisfy a lot of interests; the online version is very attractive with the hyperlinks.  Why submit  The issues appear regularly 2 times per year, the waiting time is not too long, the online version contains hyperlinks.  Rejection Rate   56%   Archiving  Sciendo archives the contents of this journal in Portico - digital long-term preservation service of scholarly books, journals and collections.  Plagiarism Policy  The editorial board is participating in a growing community of Similarity Check System's users in order to ensure that the content published is original and trustworthy. Similarity Check is a medium that allows for comprehensive manuscripts screening, aimed to eliminate plagiarism and provide a high standard and quality peer-review process.  Article Processing Charge (APC)  The journal does not have article processing charges (APCs) nor article submission charges. 