Weighted inverse maximum perfect matching problems under the Hamming distance

Given an undirected network G(V, E, c) and a perfect matching M ⁰, the inverse maximum perfect matching problem is to modify the cost vector as little as possible such that the given perfect matching M ⁰ can form a maximum perfect matching. The modification can be measured by different norms. In this paper, we consider the weighted inverse maximum perfect matching problems under the Hamming distance, where we use the weighted Hamming distance to measure the modification of the edges. We consider both of the sum-type and the bottleneck-type problems. For the general case of the sum-type case, we show it is NP-hard. For the bottleneck-type, we present a strongly polynomial algorithm which can be done in O(m · n ³).     

Weighted matching as a generic pruning technique applied to optimization constraints

We study the application of matching theory within a constraint programming framework. In this work we describe a filtering scheme based on weighted matchings. A first benefit of our pruning technique comes from the fact that it can be applied on various optimization constraints. In a number of important cases our method achieves domain consistency in polynomial time. A key feature in our implementation is the use of decomposition theory. The paper compares some of the optimization constraints reported in the literature and shows how they can be solved with the help of the weighted matching.     

Set partitions with restrictions

Based on finite set partitions, we introduce restrictions to the distances among the elements in each part and refine the Stirling numbers of the second kind with an extra parameter in two different ways. Combinatorial approach through distributions of “balls into boxes” is employed to establish explicit formulae.     

Endomorphisms with pseudoidentical restrictions

Mathematical Notes -     

Even-aged restrictions with sub-graph adjacency

Restrictions on the size and proximity of clearcuts have led to the development of a variety of exact and heuristic methods to optimize the net present value of timber harvests, subject to adjacency constraints. Most treat harvest units as pre-defined, and impose adjacency constraints on any two units sharing a common border. By using graph theory notation to define sub-graph adjacency constraints, opening size can be considered variable, which may be more appropriate for landscape-level planning. A small example data set is used in this paper to demonstrate the difference between the two types of adjacency constraints for both integer programming and heuristic solution methods.     

Finite union theorem with restrictions

The aim of this paper is to prove the following extension of the Folkman-Rado-Sanders Finite Union Theorem: For every positive integersr andk there exists a familyL of sets having the following properties:

1. ifS ₁,S ₂, ...,S _{k + 1} are distinct pariwise disjoint elements ofL then there exists nonemptyI ? {1, 2, ...,k + 1} with ∪ _i∈I S _i ?L
2. ifL =L ₁ ?...?L _r is an arbitrary partition then there existsj ≤ r and pairwise disjoint setsS ₁,S ₂, ...,S _k ∈L _j , such thatL _i∈I S _i ∈L _j for every nonemptyI ? {1, 2, ...,k}.

     

Matroids with given restrictions and contractions

If M is a matroid on a set S and if X is a subset of S, then there are two matroids on X induced by M: namely, the restriction and the contraction of M onto X. Necessary and sufficient conditions are obtained for two matroids on the same set to be of this form and an analogous result is obtained when (X₁,…, X_t) is a partition of S. The corresponding results when all the matroids are binary are also obtained.     

Quasilinear conflict-controlled processes with additional restrictions

A class of conflict-controlled processes [1–3] with additional (“phase” type) restrictions on the state of the evader is considered. A similar unrestricted problem was considered in [4]. Unlike [5, 6] the boundary of the “phase” restrictions is not a “death line” for the evader. Sufficient conditions for the solvability of the pursuit and evasion problems are obtained, which complement a range of well-known results [5–10].^‡     

Quasicqnformal mappings with restrictions in measure

The principal result of the paper is a criterion of compactness for mappings quasiconformal in the mean. The semicontinuity of a deformation of homeomorphisms from the Sobolev class is also proved.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 45, No. 7, pp. 1009–1019, July, 1993.     

Extremally distant normed spaces with additional restrictions

We study the relationship between the Banach—Mazur distance and the modified Banach—Mazur distance. We sharpen the Szarek theorem on the construction of invariant norms with specific properties and construct extremally distant normed spaces with norms invariant under groups of automorphisms of small cardinality. We prove that the trivial upper bound for the Banach—Mazur distance obtained in terms of the modified Banach—Mazur distance is order-sharp.     

Weekly staff scheduling with workstation group restrictions

This paper addresses the weekly adjustment problem for staff scheduling when movement restrictions exist between workstation groups (WSGs). In practice, it is common for employees to be organized into physical or logical groups to match the layout of a facility or to facilitate managerial oversight. A complication in the problem arises when each employee is required to spend more time at his or her assigned home base during the week than at any other WSG. This conflicts with a common strategy of reassigning employees to different WSGs when idle time exists in their schedules. Ordinarily, the full problem is tackled with a two-phase approach, where optimal shifts and overtime allocations are first derived and then tasks are assigned. When movement restrictions exist in a facility, this approach is no longer practical or even possible for all but the smallest instances. Alternatively, a new model is proposed that integrates WSG restrictions with the shift scheduling and task assignment constraints. The model takes the form of a large-scale integer program and is solved with one of two decomposition heuristics. The first splits the movement restrictions network into manageable pieces; the second uses column generation to identify good individual schedules that are used to construct a set-covering-type master problem. A solution to the master problem provides a feasible solution to the original integer program. Extensive testing was done with data obtained from the U.S. Postal Service mail processing and distribution center in Dallas. The results show that good feasible solutions can be obtained in less than an hour.     

Groups with restrictions on infinite subnormal subgroups

In this article groups are investigated in which every infinite subnormal subgroup has finitely many conjugates or has finite index in its normal closure.     

Scheduling unit-length jobs with machine eligibility restrictions

We consider uniform parallel machine scheduling problems with unit-length jobs where every job is only allowed to be processed on a specified subset of machines. We develop efficient methods to solve problems with various objectives, including minimizing a total tardiness function, a maximum tardiness function, total completion time, the number of tardy jobs, the makespan, etc.     

Groups with some restrictions on non-Baer subgroups

Ricerche di Matematica - It is proved that if G is an $$mathfrak {X}$$ -group of infinite rank whose proper subgroups of infinite rank are Baer groups, then so are all proper subgroups of G, where...     

Iterative processes with „nucleolar“ restrictions

Some aspects of the convergence of iterative processes are examined in a general context and a specific iterative process that generalizesStearns' K-transfer schemes is evolved. This yields a simplified proof ofStearns' convergence theorem and an iterative scheme that converges to the nucleolus. Stability and finite convergence properties are shown to hold and various known results on the nucleolus derive as by-products.     

Menger-type theorems with restrictions on path lengths

If the paths of length s, joining two non-adjacent vertices u, υ of a graph cannot be destroyed by deleting less than t vertices, then there are at least t internally vertex-disjoint paths joining u and υ, each having length less than . Some constructions show that using paths of length at least s/t−1^t might be necessary.     

The Adjusted Spherical Frontier Model with weight restrictions

This paper presents the ASFM-lp model, a parametric Data Envelopment Analysis (DEA) model for allocating resources, commonly called inputs. This model considers that a fair allocation of inputs is one that maximizes the DEA-CCR efficiencies of the Decision Making Units (DMUs). The main assumption of the ASFM-lp is the predefined spherical shape of the efficiency frontier. We have demonstrated that our method extends the existing parametric model ASFM to allow the introduction of weight restrictions, which has great importance in practical applications of DEA. Numeric examples are presented to show the application of the method.     

Parameterized matching with mismatches

The problem of approximate parameterized string searching consists of finding, for a given text t=t₁t₂…t_n and pattern p=p₁p₂…p_m over respective alphabets Σ_t and Σ_p, the injection π_i from Σ_p to Σ_t maximizing the number of matches between π_i(p) and t_it_i+1…t_i+m−1 (i=1,2,…,n−m+1). We examine the special case where both strings are run-length encoded, and further restrict to the case where one of the alphabets is binary. For this case, we give a construction working in time O(n+(r_p×r_t)α(r_t)log(r_t)), where r_p and r_t denote the number of runs in the corresponding encodings for y and x, respectively, and α is the inverse of the Ackermann's function.