Search

В статье рассмотрена задача восстановления символьных периодических последовательностей, искаженных шумами вставки, а также замены и удаления символов. Поскольку степень детализации символьного описания процесса определяется мощностью алфавита, представляет интерес исследование влияния степени детализации символьного описания на возможность восстановления полной информации об исходной периодической последовательности. Представлено экспериментальное исследование зависимости характеристик качества предложенного авторами метода восстановления периода от мощности алфавита. Для алфавитов разной мощности приводятся доля последовательностей с удовлетворительно восстановленным периодом и относительная погрешность определения длины периода. Качество восстановления оценивается отношением редакционного расстояния от восстановленной периодической последовательности до исходной строго периодической последовательности The relevance of this study is associated with the presence of a wide range of applied problems in real-world data processing and analysis. It is sensible to encode information using symbols from a finite alphabet in such problems. By varying the cardinality of the alphabet, in the description of the process, the symbolic representation provides a level of detail sufficient for real-world data analysis. However, for a number of subject areas in which it is possible to use symbolic coding of trajectories of the examined processes researchers face the presence of distortions, noise, and fragmentation of information. This occurs in bioinformatics, medicine, digital economy, time series forecasting and analysis of business processes. Periodic processes are widely represented in these subject areas. Without noise, these processes correspond to periodic symbolic sequences, i.e. words over a finite alphabet. A researcher often receives a sequence distorted by noises of various origins as the experimental data, instead of the expected periodic symbolic sequence. Under these conditions, when solving the problem of identifying the periodicity, which includes both the determination of a periodically repeating symbolic fragment and its length, hereinafter called the period, the problem requires reducing the effect of noise on the experimental results. The article deals with the problem of recovering periodic sequences, distorted by presence of noise along the replaced and deleted symbols. Since the level of detail in the description of the process depends on the cardinality of the alphabet, it is of interest to study the influence of the level of detail in the symbolic description on the possibility of recovering complete information about the initially periodic sequences. The article experimentally examines the dependence of the cardinality of the alphabet on the quality characteristics of the period recovery method proposed by the authors. For alphabets of different cardinalities, the proportion of sequences with a satisfactorily reconstructed period and the relative error in determining the length of the period are given. The quality of reconstruction of a periodically repeating fragment is estimated by the ratio of the editing distance from the reconstructed periodic sequence to the original sequence distorted by noise

Given an undirected graph G = ( V , E ) and a positive integer k ∈ 1 , … , | V | , we initiate the combinatorial study of stable sets of cardinality exactly k in G . Our aim is to instigate the polyhedral investigation of the convex hull of fixed cardinality stable sets, inspired by the rich theory on the classical structure of stable sets. We introduce a large class of valid inequalities to the natural integer programming formulation of the problem. We also present simple combinatorial relaxations based on computing maximum weighted matchings, which yield dual bounds towards finding minimum-weight fixed cardinality stable sets, and particular cases which are solvable in polynomial time.

I would like to dedicate this little exposition to Prof. Phan Dinh Dieu, one of the giants and pioneers of Mathematics in Computer Science in Vietnam. In the past 15 years or so, new and exciting connections between fundamental problems in database theory and information theory have emerged. There are several angles one can take to describe this connection. This paper takes one such angle, influenced by the author's own bias and research results. In particular, we will describe how the cardinality estimation problem -- a corner-stone problem for query optimizers -- is deeply connected to information theoretic inequalities. Furthermore, we explain how inequalities can also be used to derive a couple of classic geometric inequalities such as the Loomis-Whitney inequality. A purpose of the article is to introduce the reader to these new connections, where theory and practice meet in a wonderful way. Another objective is to point the reader to a research area with many new open questions.

In a cardinality constrained inverse center location problem on networks, the goal is to modify the edge lengths at the minimum total cost subject to the given modification bounds so that a prespecified vertex becomes an absolute center location of the underlying network under the perturbed edge lengths and further the cardinality of the modified edge lengths obeys an upper bound. Using a set of self-constructed red-black search trees, as a suitable data structure, we propose novel optimal algorithms with polynomial time complexities for the problem on tree networks under various cost norms.

In this brief, we present a novel quantum protocol for Multiparty Privacy Set Intersection Cardinality (MPSI-CA) and design the corresponding quantum circuits. The proposed protocol demonstrates two primary aspects of quantum advantage: the parallelism of quantum computing and the randomness of quantum measurement. Compared with the classical related protocols, the proposed MPSI-CA protocol can ensure higher security (i.e., unconditional security) and achieve better communication complexity (i.e., ${O}({t}^{2})$ ).

We study subspace codes with nonmaximum code distance. As opposed to spreads, i.e., codes with the maximum subspace distance, we refer to them as nonspreads here. We consider families of nonspreads based on using the Silva–Kotter–Kschischang (SKK) subspace code construction and Gabidulin–Bossert multicomponent codes with zero prefix (MZP). We give estimates for cardinalities of nonspreads for a large number of parameters. We show that for large dimensions, the cardinalities almost attain the upper bound given by the Johnson inequality.

We study a cardinality-constrained optimisation problem with nonnegative variables in this paper. This problem is often encountered in practice. Firstly, we study some properties on the optimal sol...

17 USC 105 interim-entered record; under review. The article of record as published may be found at http://dx.doi.org/10.3934/amc.2020071 In the field of privacy preserving protocols, Private Set Intersection (PSI) plays an important role. In most of the cases, PSI allows two parties to securely determine the intersection of their private input sets, and no other information. In this paper, employing a Bloom filter, we propose a Multiparty Private Set Intersection Cardinality (MPSI-CA), where the number of participants in PSI is not limited to two. The security of our scheme is achieved in the standard model under the Decisional Diffie-Hellman (DDH) assumption against semi-honest adversaries. Our scheme is flexible in the sense that set size of one participant is independent from that of the others. We consider the number of modular exponentiations in order to determine computational complexity. In our construction, communication and computation overheads of each participant is O(v max k) except that the complexity of the designated party is O(v1), where v max is the maximum set size, v1 denotes the set size of the designated party and k is a security parameter. Particularly, our MSPI-CA is the first that incurs linear complexity in terms of set size, namely O(nv max k), where n is the number of participants. Further, we extend our MPSI-CA to MPSI retaining all the security attributes and other properties. As far as we are aware of, there is no other MPSI so far where individual computational cost of each participant is independent of the number of participants. Unlike MPSI-CA, our MPSI does not require any kind of broadcast channel as it uses star network topology in the sense that a designated party communicates with everyone else. This research was funded by an Andrew Carnegie Fellowship (to S.M.) from the Carnegie Corporation of New York. Additional support was provided by a Donald R. Beall Defense Fellowship (to M.R.Z.) through the Naval Postgraduate School Foundation.

We study sender–receiver games in which a privately informed sender sends a message to N receivers, who then take an action. The sender’s type space T has finite cardinality (i.e., | T | ∞ ). We show that every equilibrium payoff vector (resp. every Pareto efficient equilibrium payoff vector) is achieved by an equilibrium in which the sender sends at most | T | + N (resp. | T | + N − 1 ) messages with positive probability. We also show that such bounds do not exist when two privately informed senders simultaneously send a message to a receiver.

This paper investigates the principles that one must add to Boolean algebra to capture reasoning not only about intersection, union, and complementation of sets, but also about the relative size of sets. We completely axiomatize such reasoning under the Cantorian definition of relative size in terms of injections.

In two previous publications we have, on the one hand, extended the description logic (DL) ALCQ by more expressive number restrictions using numerical and set constraints expressed in the quantifier-free fragment of Boolean Algebra with Presburger Arithmetic (QFBAPA). The resulting DL was called ALCSCC . On the other hand, we have extended the terminological formalism of the well-known description logic ALC from concept inclusions (CIs) to more general cardinality constraints expressed in QFBAPA, which we called extended cardinality constraints. Here, we combine the two extensions, i.e., we consider extended cardinality constraints on ALCSCC concepts. We show that this does not increase the complexity of reasoning, which is NExpTime-complete both for extended cardinality constraints in the DL ALC and in its extension ALCSCC . The same is true for a restricted version of such cardinality constraints, where the complexity of reasoning decreases to ExpTime, not just for ALC , but also for ALCSCC.

We introduce a linear programming framework for obtaining upper bounds for the potential energy of spherical codes of fixed cardinality and minimum distance. Using Hermite interpolation we construct polynomials to derive corresponding bounds. These bounds are universal in the sense that they are valid for all absolutely monotone potential functions and the required interpolation nodes do not depend on the potentials.

We give a recursion-like theorem which enables us to encode the elements of the real Borel class by infinite sequences of integers. This fact implies that the cardinality of the Borel class is not above continuum, without depending on cumbrous tools like transfinite induction and Suslin operation.

In this paper we propose some mixed integer linear programming formulations for the K clusters with fixed cardinality problem. These formulations are strengthened by valid inequalities and all the mixed integer linear models are compared from a theoretical and practical point of view. The continuous linear relaxation bounds of the developed models are tested on randomly generated instances, by using standard software, with promising results.

Estimating the cardinality (number of distinct elements) of a large multiset is a classic problem in streaming and sketching, dating back to Flajolet and Martin's classic Probabilistic Counting (PCSA) algorithm from 1983. In this paper we study the intrinsic tradeoff between the space complexity of the sketch and its estimation error in the random oracle model. We define a new measure of efficiency for cardinality estimators called the Fisher-Shannon (Fish) number $\mathcal{H}/\mathcal{I}$. It captures the tension between the limiting Shannon entropy ($\mathcal{H}$) of the sketch and its normalized Fisher information ($\mathcal{I}$), which characterizes the variance of a statistically efficient, asymptotically unbiased estimator. Our results are as follows. We prove that all base-$q$ variants of Flajolet and Martin's PCSA sketch have Fish-number $H_0/I_0 \approx 1.98016$ and that every base-$q$ variant of (Hyper)LogLog has Fish-number worse than $H_0/I_0$, but that they tend to $H_0/I_0$ in the limit as $q\rightarrow \infty$. Here $H_0,I_0$ are precisely defined constants. We describe a sketch called Fishmonger that is based on a smoothed, entropy-compressed variant of PCSA with a different estimator function. It is proved that with high probability, Fishmonger processes a multiset of $[U]$ such that at all times, its space is $O(\log^2\log U) + (1+o(1))(H_0/I_0)b \approx 1.98b$ bits and its standard error is $1/\sqrt{b}$. We give circumstantial evidence that $H_0/I_0$ is the optimum Fish-number of mergeable sketches for Cardinality Estimation. We define a class of linearizable sketches and prove that no member of this class can beat $H_0/I_0$. The popular mergeable sketches are, in fact, also linearizable., 50 pages, 7 figures, submitted to STOC 2021

Threshold Private Set Intersection (PSI) allows multiple parties to compute the intersection of their input sets if and only if the intersection is larger than \(n-t\), where n is the size of each set and t is some threshold. The main appeal of this primitive is that, in contrast to standard PSI, known upper-bounds on the communication complexity only depend on the threshold t and not on the sizes of the input sets. Current threshold PSI protocols split themselves into two components: A Cardinality Testing phase, where parties decide if the intersection is larger than some threshold; and a PSI phase, where the intersection is computed. The main source of inefficiency of threshold PSI is the former part.

Certain English quantificational expressions feature what appears to be an indefinite article, e.g. a bunch, a few, a hundred. These can be divided into three types of quantifying expressions: pseudopartitives (a lot, a bunch, a ton), article-requiring quantifiers (a few, a couple, a hundred), and article-free quantifiers (three, many, several); article-free quantifiers have an article under certain circumstances, e.g. modification by an adjective (a surprising 30 …). While standard analyses would take the article in these expressions to be a D head, it is argued here that the article is not in D, nor is it singular or count, as evidenced by its (lack of an) interaction with verbal agreement. Instead, it is claimed that a(n) is a default cardinality marker, which surfaces when a QP is present, but fails to be spelled-out by other material. The distribution of default a(n) further interacts with adjective placement (a surprising 30), plural marking on some quantifiers (tons of), other determiners (the hundred), and the functional status of the quantifier (a wealth of vs. a lot). The resemblance of this article to the English indefinite article a(n) is also considered, and a possible unifying analysis is given.

In order to improve the simultaneous localization and mapping (SLAM) accuracy of mobile robots in complex indoor environments, the multi-robot cardinality-balanced multi-Bernoulli filter SLAM (MR-CBMber-SLAM) method is proposed. First of all, this method introduces a multi-Bernoulli filter based on the random finite set (RFS) theory to solve the complex data association problem. This method aims to overcome the problem that the multi-Bernoulli filter will overestimate the aspect of SLAM map feature estimation, and combines the strategy of balancing cardinality with a multi-Bernoulli filter. What is more, in order to further improve the accuracy and operating efficiency of SLAM, a multi-robot strategy and a multi-robot Gaussian information-fusion method are proposed. In the experiment, the MR-CBMber-SLAM method is compared with the multi-vehicle probability hypothesis density SLAM (MV-PHD-SLAM) method. The experimental results show that the MR-CBMber-SLAM method is better than MV-PHD-SLAM method. Therefore, it effectively verifies that the MR-CBMber-SLAM method is more adaptable to a complex indoor environment.

Cardinality constraints state that at most (at least, or exactly) k out of n propositional variables can be true. In this paper we prove the arc-consistency property of an encoding of cardinality constraint (into a CNF formula) that we call a standard encoding of generalized selection networks.

To identify abnormal traffic such as P2P flows, DDoS attacks, and Internet worms, this paper discusses a circuit design to realize real-time abnormal traffic detection in broadband networks. Real-time counting of cardinality is the key feature of the circuit. Although our previous study showed that cardinality counting is effective for detecting various types of abnormal traffic, the slowness of DRAM access prevented us from deploying cardinality counting in backbone networks. To address the problem of DRAM access time, this paper proposes a new algorithm for cardinality counting. By changing the order of the cardinality counting process, the proposed algorithm enables parallel accesses of DRAM circuits, which hides the slow DRAM access time through a pipeline circuit. In addition, we propose a new hashing function that also hides the DRAM access problem. It partially replaces scattered addresses with successive addresses, in order to use a faster DRAM burst access. We also report the accuracy of the cardinality counting of the new algorithm, and describe the estimated processing performance based on a pipeline tact level circuit simulation. Our experimental results show that the use of the self-timed pipeline circuit can help realize cardinality counting at rates up to 100Gbps.

The problem of minimizing a multilinear function of binary variables is a well-studied NP-hard problem. The set of solutions of the standard linearization of this problem is called the multilinear set, and many valid inequalities for its convex hull are available in the literature. Motivated by a machine learning application, we study a cardinality constrained version of this problem with upper and lower bounds on the number of nonzero variables. We call the set of solutions of the standard linearization of this problem a cardinality constrained multilinear set, and give a complete polyhedral description of its convex hull when the multilinear terms in the problem have a nested structure.

We employ signed measures that are positive definite up to certain degrees to establish Levenshtein-type upper bounds on the cardinality of codes with given minimum and maximum distance, and universal lower bounds on the potential energy (for absolutely monotone interactions) for codes with given maximum distance and fixed cardinality. In particular, we extend the framework of Levenshtein bounds for such codes.

In two previous publications we have, on the one hand, extended the description logic (DL) ALCQ by more expressive number restrictions using numerical and set constraints expressed in the quantifier-free fragment of Boolean Algebra with Presburger Arithmetic (QFBAPA). The resulting DL was called ALCSCC. On the other hand, we have extended the terminological formalism of the well-known description logic ALC from concept inclusions (CIs) to more general cardinality constraints expressed in QFBAPA, which we called extended cardinality constraints. Here, we combine the two extensions, i.e., we consider extended cardinality constraints on ALCSCC concepts. We show that this does not increase the complexity of reasoning, which is NExpTime-complete both for extended cardinality constraints in ALC and ALCSCC. The same is true for a restricted version of such cardinality constraints, where the complexity of reasoning decreases to ExpTime, not just for ALC, but also for ALCSCC.

The work considers an equivalence relation in the set of all n × m binary matrices. In each element of the factor-set generated by this relation, we define the concept of canonical binary matrix, namely the minimal element with respect to the lexicographic order. For this purpose, the binary matrices are uniquely represented by ordered n-tuples of integers. We have found a necessary and sufficient condition for an arbitrary matrix to be canonical. This condition could be the base for realizing recursive algorithm for finding all n × m canonical binary matrices and consequently for finding all bipartite graphs, up to isomorphism with cardinality of each part equal to n and m.

The paper puts forward a nontrivial lower estimate 2 1 6 n $2\!\frac16n $ for the cardinality of the domain of a universal function for the class of linear Boolean functions, where n is the number of variables.

We try to find a common extension of two cardinal inequalities for Lindelof spaces. Using an estimate of the number of G δ points due to Balogh, we improve a result of Juhasz and Spadaro. A cardinal inequality for linearly Lindelof Tychonoff spaces proved by Arhangel'skiĭ and Buzyakova should be actually true for Hausdorff spaces. We observe this happens under some restrictions on cardinal arithmetics, including a consequence of Martin's axiom. Finally, we address the question to estimate the cardinality of a first countable linearly H-closed space.

Cardinality constraints enforce an upper bound on the number of variables that can be nonzero. This article investigates linear programs with cardinality constraints that mutually overlap, i.e., share variables. We present the components of a branch-and-cut solution approach, including new branching rules that exploit the structure of the corresponding conflict hypergraph. We also investigate valid or facet defining cutting planes for the convex hull of the feasible solution set. Our approach can be seen as a continuous analogue of independence system polytopes. We study three different classes of cutting planes: hyperclique bound cuts, implied bound cuts, and flow cover cuts. In a computational study, we examine the effectiveness of an implementation based on the presented concepts.

In this paper, we prove that every polynomial-size theory in simple definite causal theories (STry) can be equivalently translated into a cardinality constraint program (CPing) with small-size growth(without introducing new variables). It is well known that the PARITY problem can be represented by a polynomial-size CPing program but exponential-size blowup is inevitable in STry, we get the conclusion that CPing is more succinct than STry. The result gives us a deeper understanding about the succinctness relationships between different classes of logic formalisms.

In this paper, we will discuss the succinctness between cardinality constraint programs (CPing) and canonical logic programs (Ping). We prove that every Ping program has an equivalent translation in CPing with small-size growth(without new variables). It is well known that the PARITY problem can be represented by a polynomial-size CPing program while exponential-size blowup is inevitable in Ping programs(without new variables). we get the conclusion that CPing is more succinct than Ping.

An invariant cover quantifies the information needed by a controller to enforce an invariance specification. This paper investigates some fundamental problems concerning existence and computation of an invariant cover for uncertain discrete-time linear control systems subject to state and control constraints. We develop necessary and sufficient conditions on the existence of an invariant cover for a polytopic set of states. The conditions can be checked by solving a set of linear programs , one for each extreme point of the state set. Based on these conditions, we give upper and lower bounds on the minimal cardinality of the invariant cover, and design an iterative algorithm with finite-time convergence to compute an invariant cover. We further show in two examples how to use an invariant cover in the design of a coder–controller pair that ensures invariance of a given set for a networked control system with a finite communication data rate.

26 pags., 12 figs., In this work we develop tools to address combinatorial optimization problems with a cardinality constraint, in which only a subset of variables end up having nonzero values. Firstly, we introduce a new heuristic pruning method that iteratively discards variables through a hybrid quantum-classical optimization step. Secondly, we analyse the use of soft constraints in the form of 'chemical potentials' to control the number of non-zero variables. We illustrate the power of both techniques using the problem of index tracking, which aims to mimicking the performance of a financial index with a balanced subset of assets. We also compare the performance of different state-of-the-art quantum variational optimization algorithms in our pruning method., D. Porras and J.J. Garcıa Ripoll acknowledge funding from Spanish project PGC2018- 094792-B-I00 (MCIU/AEI/FEDER, UE), CSIC Research Platform PTI-001, and CAM/FEDER Project No. S2018/TCS4342 (QUITEMAD-CM).

Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph G a k-coloring, i.e., a partition V-1,...,V-k of the vertex set of G such that, for some specified neighborhood (N) over tilde(upsilon) of each vertex upsilon, the number of vertices in (N) over tilde(upsilon) boolean AND V-i is (at most) a given integer h(upsilon)(i). The complexity of some variations is discussed according to (N) over tilde(upsilon), which may be the usual neighbors, or the vertices at distance at most 2, or the closed neighborhood of upsilon (upsilon and its neighbors). Polynomially solvable cases are exhibited (in particular when G is a special tree). (C) 2009 Elsevier B.V. All rights reserved.

The soft cardinality function generalizes the concept of counting measure of the classic cardinality of sets. This function provides an intuitive measure of the amount of elements in a collection (i.e. a set or a bag) exploiting the similarities among them. Although soft cardinality was first proposed in an ad-hoc way, it has been successfully used in various tasks in the field of natural language processing. In this paper, a formal definition of soft cardinality is proposed together with an analysis of its boundaries, monotonicity property and a method for constructing similarity functions. Additionally, an empirical evaluation of the model was carried out using synthetic data.

The paper presents an improved product multi-sensor PHD (PM-PHD) algorithm, CM-GM-PHD.The authors prove that the infinite sums in the update formula of PM-PHD can be approximated by the sum of exact intervals.The authors propose a cardinality modified method to deal with the inaccurate state estimation of PM-PHD. The iterated-corrector PHD (IC-PHD) filter, which is the most commonly used multi-sensor PHD filter, is affected by the sensor order and the probability of detection. To address this problem, the product multi-sensor PHD (PM-PHD) filter, a modified version of the IC-PHD filter, is proposed. The update formulation of the PM-PHD filter consists of a likelihood function and a modified coefficient. Although the coefficient improves the performance of the PM-PHD filter, it still has some drawbacks. In this paper, two improvements on the coefficient are proposed. (1) The coefficient is the quotient of two infinite sums which are computational intractable. We prove that some terms in the infinite sums can be eliminated, and thus the infinite sums can be approximated by the sum of finite terms. (2) Since the coefficient is a scalar quantity, it mainly focuses on maintaining the magnitudes of the posterior PHD and the number of targets. It may lead to an inaccurate state estimation in some situations. In the Gaussian mixture implementation of the PM-PHD filter, a cardinality modified method is proposed to reassign the weight of Gaussian components and modify the posterior PHD. The advantages of these two methods are verified by simulations and experiments.

A set S of integers is a B 3 -set if all the sums of the form a 1 + a 2 + a 3 , with a 1 , a 2 and a 3 ? S and a 1 ? a 2 ? a 3 , are distinct. We obtain asymptotic bounds for the number of B 3 -sets of a given cardinality contained in the interval n = { 1 , ? , n } . We use these results to estimate the maximum size of a B 3 -set contained in a typical (random) subset of n of a given cardinality. These results confirm conjectures recently put forward by the authors On the number of B h -sets, Combin. Probab. Comput. 25 (2016), no. 1, 108-127.

It is well-known that the intersection of the matching polytope with a cardinality constraint is integral (Schrijver, 2003)? 8. In this note, we prove a similar result for the polytope corresponding to the transportation problem with market choice (TPMC) (introduced in Damci-Kurt et?al. (2015)) when the demands are in the set { 1 , 2 } . This result generalizes the result regarding the matching polytope. The result in this note implies that some special classes of minimum weight perfect matching problem with a cardinality constraint on a subset of edges can be solved in polynomial time.

This paper introduces the minimum cardinality bin covering problem where we are given m identical bins with capacity C and n indivisible items with integer weights wj ( j = 1 , … , n ) . The objective is to minimize the number of items packed into the m bins so that the total weight of each bin is at least equal to C. We discuss reduction criteria, derive several lower bound arguments and propose construction heuristics as well as a powerful subset sum-based improvement algorithm that is even optimal when m = 2 . Moreover, we present a tailored branch-and-bound method which is able to solve instances with up to 20 bins and several hundreds of items within a reasonable amount of time. In a comprehensive computational study on a wide range of randomly generated instances, our algorithmic approach proved to be much more effective than a commercial solver.

Based on Y. Kawahara's characterisation of the cardinality of relations we derive some fundamental properties of cardinalities concerning vectors, points and mapping-related relations. As applications of these results we verify some properties of linear orders and graphs in a calculational manner. These include the cardinalities of rooted trees and some estimates concerning graph parameters. We also calculationally prove the result of D. Kźnig that in bipartite graphs the matching number equals the vertex cover number.

It is introduced a certain approach for equipment of sets with cardinality of the continuum by structures of Polish groups with two-sided (left or right) invariant Haar measures. By using this approach we answer positively Maleki’s certain question (2012) what are the real k-dimensional manifolds with at least two different Lie group structures that have the same Haar measure. It is demonstrated that for each diffused Borel probability measure defined in a Polish space (G;ρ;Bρ(G)) without isolated points there exist a metric ρ1and a group operation ⊙ in G such that Bρ(G) = Bρ1(G) and (G;ρ1;Bρ1(G);⊙) stands a compact Polish group with a two-sided (left or right) invariant Haar measure μ , where Bρ(G) and Bρ1(G) denote Borel σ-algebras of subsets of G generated by metrics ρ and ρ1, respectively. Similar approach is used for a construction of locally compact non-compact or non-locally compact Polish groups equipped with two-sided (left or right) invariant quasi-finite Borel measures.

In this article, we investigate the Minimum Cardinality Segmentation Problem (MCSP), an NP-hard combinatorial optimization problem arising in intensity-modulated radiation therapy. The problem consists in decomposing a given nonnegative integer matrix into a nonnegative integer linear combination of a minimum cardinality set of binary matrices satisfying the consecutive ones property. We show how to transform the MCSP into a combinatorial optimization problem on a weighted directed network and we exploit this result to develop an integer linear programming formulation to exactly solve it. Computational experiments show that the lower bounds obtained by the linear relaxation of the considered formulation improve upon those currently described in the literature and suggest, at the same time, new directions for the development of future exact solution approaches to the problem.

We show that the asymptotic number of 2-generated semigroups is super-exponential in the cardinality. This answers a question raised by Bailey et al. (Isr J Math 215(1):459–501, 2016).

In this chapter we present results from Przymusinski’s paper (Proc Am Math Soc 69:333–338, 1978) concerning the notions of n-cardinality and n-Bernstein sets. Applications will be given in the chapters that follow. In particular, the notion of 2-cardinality is used in the chapter on normal products and dimension.

The aim of this paper is to investigate the behaviour of uncountable groups of regular cardinality ℵ in which all proper subgroups of cardinality ℵ belong to a given group class X . It is proved that if every proper subgroup of G of cardinality ℵ has finite conjugacy classes, then also the conjugacy classes of G are finite, provided that G has no simple homomorphic images of cardinality ℵ. Moreover, it turns out that if G is a locally graded group of cardinality ℵ in which every proper subgroup of cardinality ℵ contains a nilpotent subgroup of finite index, then G is nilpotent-by-finite, again under the assumption that G has no simple homomorphic images of cardinality ℵ. A similar result holds also for uncountable locally graded groups whose large proper subgroups are abelian-by-finite.