A probabilistic analysis of some greedy cardinality matching algorithms

This paper deals with the expected cardinality of greedy matchings in random graphs. Different versions of the greedy heuristic for the cardinality matching problem are considered. Experimental data and some theoretical results are reported.     

Efficient Algorithms for Variants of Weighted Matching and Assignment Problems

Obtaining a matching in a graph satisfying a certain objective is an important class of graph problems. Matching algorithms have received attention for several decades. However, while there are efficient algorithms to obtain a maximum weight matching, not much is known about the maximum weight maximum cardinality, and maximum cardinality maximum weight matching problems for general graphs. Our contribution in this work is to show that for bounded weight input graphs one can obtain an algorithm for both maximum weight maximum cardinality (for real weights), and maximum cardinality maximum weight matching (for integer weights) by modifying the input and running the existing maximum weight matching algorithm. Also, given the current state of the art in maximum weight matching algorithms, we show that, for bounded weight input graphs, both maximum weight maximum cardinality, and maximum cardinality maximum weight matching have algorithms of similar complexities to that of maximum weight matching. Subsequently, we also obtain approximation algorithms for maximum weight maximum cardinality, and maximum cardinality maximum weight matching.      

处处不连续又不可测的达布函数类的势

该文提出了一种构造处处不连续，而且在任何区间内取到任一函数值ｃ次的达布函数类的新方法，证明了该函数类的势为２＾ｃ（ｃ为连续统势）；还得到了处处不连续又不可测的达布函数类的势为２＾ｃ。     

变动基数投资组合中的系统误差与估计误差权衡

投资组合选择中的系统误差与估计误差是决定样本期外绩效的重要因素,其权衡受到资产基数N的影响。本文在变动基数的设定下,将Bootstrapping和样本期外滚动的方法应用到均权重、最小方差组合及其误差修正策略的绩效和尾部风险检验过程中,并在不同的市场状态下进行分组讨论。研究发现:(1)最小方差组合与均权重策略的样本期外夏普比率差异与N存在倒U型的关系。(2)最小方差组合的尾部风险随N的扩大而迅速降低,总体来看最小方差组合的尾部风险低于均权重策略。(3)最小方差组合的换手率与N存在正相关关系,盲目增加投资组合选择中的资产基数会带来无谓损失。研究结果表明,投资者应理性选择资产基数,充分利用最小方差组合带来的分散化收益。     

A number theoretic formula and asymptotic optimality of cardinalities of BAD correcting codes

This paper presents a formula for the cardinality of a class of non-linear error correcting codes for Balanced Adjacent Deletions that are provided as an extension of standard deletion from the point of the view of Weyl groups. Furthermore, we show that the cardinality is approximately optimal over any single BAD correcting codes. In other words, the ratio of the cardinality of the code and that of maximum cardinality BAD correcting code converges to 1 for sufficiently large length.     

A polyhedral study on 0–1 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting

We study the set of 0–1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP), which generalizes the classical 0–1 knapsack polytope and the 0–1 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its feasible solutions using sequence-independent lifting. For problems with a single cardinality constraint, we derive two-dimensional superadditive lifting functions and prove that they are maximal and non-dominated under some mild conditions. We then show that these functions can be used to build strong valid inequalities for problems with multiple disjoint cardinality constraints. Finally, we present preliminary computational results aimed at evaluating the strength of the cuts obtained from sequence-independent lifting with respect to those obtained from sequential lifting.     

Elections generate all binary relations on infinite sets

Every binary relation on an infinite set can be represented by an election in which each voter’s preferences are quasi-transitive and complete (except possibly not reflexive) and in which the electorate has smaller cardinality than or the same cardinality as the set of alternatives, depending on the cardinality of that set.     

Characterizations of Postman Sets

Using results by McKee and Woodall on binary matroids, we prove that the set of postman sets has odd cardinality, generalizing a result by Toida on the cardinality of cycles in Eulerian graphs. We study the relationship between T-joins and blocks of the underlying graph, obtaining a decom- position of postman sets in terms of blocks. We conclude by giving several characterizations of T-joins which are postman sets and commenting on practical issues.     

Study of the cardinalities of linear spaces

The paper discusses the relation between the cardinalities of linear spaces over a number field F and the cardinality of F, and obtains the result that the cardinality of a countable dimensional linear space V(F) equals the cardinality of the number field F. Some examples are given for the cardinality of a general infinite dimensional linear space.     

Characterizations of postman sets

Using results by McKee and Woodall on binary matroids, we show that the set of postman sets has odd cardinality, generalizing a result by Toida on the cardinality of cycles in Eulerian graphs. We study the relationship between T-joins and blocks of the underlying graph, obtaining a decomposition of postman sets in terms of blocks. We conclude by giving several characterizations of T-joins which are postman sets.     

Cardinality constrained combinatorial optimization: Complexity and polyhedra

Given a combinatorial optimization problem and a subset $N$ of nonnegative integer numbers, we obtain a cardinality constrained version of this problem by permitting only those feasible solutions whose cardinalities are elements of $N$. In this paper we briefly touch on questions that address common grounds and differences of the complexity of a combinatorial optimization problem and its cardinality constrained version. Afterwards we focus on the polyhedral aspects of the cardinality constrained combinatorial optimization problems. Maurras (1977) [5] introduced a class of inequalities, called forbidden cardinality inequalities in this paper, that can be added to a given integer programming formulation for a combinatorial optimization problem to obtain one for the cardinality restricted versions of this problem. Since the forbidden cardinality inequalities in their original form are mostly not facet defining for the associated polyhedron, we discuss some possibilities to strengthen them, based on the experiments made in Kaibel and Stephan (2007) and Maurras and Stephan (2009) [2], [3].     

Caps and Colouring Steiner Triple Systems

Hill [6] showed that the largest cap in PG(5,3) has cardinality 56. Using this cap it is easy to construct a cap of cardinality 45 in AG(5,3). Here we show that the size of a cap in AG(5,3) is bounded above by 48. We also give an example of three disjoint 45-caps in AG(5,3). Using these two results we are able to prove that the Steiner triple system AG(5,3) is 6-chromatic, and so we exhibit the first specific example of a 6-chromatic Steiner triple system.     

No Cycling in the Graphs!

A variety of results on the problem of destroying all cycles in a graph by removing sets of vertices of minimum cardinality are presented.     

On Center Cycles in Grid Graphs

Finding good cycles in graphs is a problem of great interest in graph theory as well as in locational analysis. We show that the center and median problems are NP-hard in general graphs. This result holds both for the variable cardinality case (i.e., all cycles of the graph are considered) and the fixed cardinality case (i.e., only cycles with a given cardinality p are feasible). Hence it is of interest to investigate special cases where the problem is solvable in polynomial time. In grid graphs, the variable cardinality case is, for instance, trivially solvable if the shape of the cycle can be chosen freely. If the shape is fixed to be a rectangle one can analyze rectangles in grid graphs with, in sequence, fixed dimension, fixed cardinality, and variable cardinality. In all cases a complete characterization of the optimal cycles and closed form expressions of the optimal objective values are given, yielding polynomial time algorithms for all cases of center rectangle problems. Finally, it is shown that center cycles can be chosen as rectangles for bounded cardinalities such that the center cycle problem in grid graphs is in these cases completely solved.     

A Note on Varying Cardinality in the Average Case Setting

We study how much information with varying cardinality can be better than information with fixed cardinality for approximating linear operators in the average case setting with Gaussian measure. It has been known that adaptive choice of functionals forming information is not better than nonadaptive, and that the only gain may be obtained by using varying cardinality. We prove that the lower bounds from Traub (J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, "Information-Based Complexity," Academic Press, San Diego, 1988) et al. on the efficiency of varying cardinality are sharp. In particular, we show that information whose cardinality assumes at most two different values can significantly help in approximating any linear operator with infinite dimensional domain space.     

Perfect binary codes of infinite length

A subset C of infinite-dimensional binary cube is called a perfect binary code with distance 3 if all balls of radius 1 (in the Hamming metric) with centers in C are pairwise disjoint and their union cover this binary cube. Similarly, we can define a perfect binary code in zero layer, consisting of all vectors of infinite-dimensional binary cube having finite supports. In this article we prove that the cardinality of all cosets of perfect binary codes in zero layer is the cardinality of the continuum. Moreover, the cardinality of all cosets of perfect binary codes in the whole binary cube is equal to the cardinality of the hypercontinuum.     

An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

In this paper, we consider combinatorial optimization problems with additional cardinality constraints. In k-cardinality combinatorial optimization problems, a cardinality constraint requires feasible solutions to contain exactly k elements of a finite set E. Problems of this type have applications in many areas, e.g. in the mining and oil industry, telecommunications, circuit layout, and location planning. We formally define the problem, mention some examples and summarize general results. We provide an annotated bibliography of combinatorial optimization problems of which versions with cardinality constraint have been considered in the literature.     

A polyhedral study of the cardinality constrained knapsack problem

 A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas such as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous and the 0-1 variables. We use an alternative approach, in which we keep in the model only the continuous variables, and we enforce the cardinality constraint through a specialized branching scheme and the use of strong inequalities valid for the convex hull of the feasible set in the space of the continuous variables. To derive the valid inequalities, we extend the concepts of cover and cover inequality, commonly used in 0-1 programming, to this class of problems, and we show how cover inequalities can be lifted to derive facet-defining inequalities. We present three families of non-trivial facet-defining inequalities that are lifted cover inequalities. Finally, we report computational results that demonstrate the effectiveness of lifted cover inequalities and the superiority of the approach of not introducing auxiliary 0-1 variables over the traditional MIP approach for this class of problems. Received: March 13, 2003 Published online: April 10, 2003 Key Words. mixed-integer programming – knapsack problem – cardinality constrained programming – branch-and-cut     

Cardinality and nilpotency of localizations of groups andG-modules

We consider the effect of a coagumented idempotent functorJ in the the category of groups orG-modules whereG is a fixed group. We are interested in the ‘extent’ to which such functors change the structure of the objects to which they are applied. Some positive results are obtained and examples are given concerning the cardinality and structure ofJ(A) in terms of the cardinality and structure ofA, where the latter is a torsion abelian group. For non-abelian groups some partial results and examples are given connecting the nilpotency classes and the varieties of a groupG andJ(G). Similar but stronger results are obtained in the category ofG-modules.     

On line perfect graphs

Line-perfect graphs have been defined by L.E. Trotter as graphs whose line-graphs are perfect. They are characterized by the property of having no elementary odd cycle of size larger than 3. L.E. Trotter showed constructively that the maximum cardinality of a set of mutually non-adjacent edges (matching) is equal to the minimum cardinality of a collection of sets of mutually adjacent edges which cover all edges.The purpose of this note is to give an algorithmic proof that the chromatic index of these graphs is equal to the maximum cardinality of a set of mutually adjacent edges.