On Combinatorial Approximation of Covering 0-1 Integer Programs and Partial Set Cover

The problems dealt with in this paper are generalizations of the set cover problem, min{cx | Ax b, x {0,1}ⁿ}, where c Q₊ⁿ, A {0,1}^{m × n}, b 1. The covering 0-1 integer program is the one, in this formulation, with arbitrary nonnegative entries of A and b, while the partial set cover problem requires only m–K constrains (or more) in Ax b to be satisfied when integer K is additionall specified. While many approximation algorithms have been recently developed for these problems and their special cases, using computationally rather expensive (albeit polynomial) LP-rounding (or SDP-rounding), we present a more efficient purely combinatorial algorithm and investigate its approximation capability for them. It will be shown that, when compared with the best performance known today and obtained by rounding methods, although its performance comes short in some special cases, it is at least equally good in general, extends for partial vertex cover, and improves for weighted multicover, partial set cover, and further generalizations.     

试论发达地区加快实现社保全民化的策略

加快实现社会保险全民化是推动社会保险事业持续快速发展,构建社会主义和谐社会的重要手段。针对困扰先发地区社会保险全民化发展的政策、经济和社会因素,此文以推进社会化管理为突破口,以机制建立为有效保障,对实现社保全民化的策略进行了一些探索。     

R~2上完备性定理的等价性循环证明

给出了R2上五个完备性定理的循环证明,从理论上更详细地说明了定理之间的等价性.     

Computing Optimal Beams in Two and Three Dimensions

The problem of computing an optimal beam among weighted regions (called the optimal beam problem) arises in several applied areas such as radiation therapy, stereotactic brain surgery, medical surgery, geological exploration, manufacturing, and environmental engineering. In this paper, we present computational geometry techniques that enable us to develop efficient algorithms for solving various optimal beam problems among weighted regions in two and three dimensional spaces. In particular, we consider two types of problems: the covering problems (seeking an optimal beam to contain a specified target region), and the piercing problems (seeking an optimal beam of a fixed shape to pierce the target region). We investigate several versions of these problems, with a variety of beam shapes and target region shapes in 2-D and 3-D. Our algorithms are based on interesting combinations of computational geometry techniques and optimization methods, and transform the optimal beam problems to solving a collection of instances of certain special non-linear optimization problems. Our approach makes use of interesting geometric observations, such as utilizing some new features of Minkowski sums.     

汉英委婉语的交际效用及其文化现象

委婉语是人类相互沟通过程中普遍存在的一种表达方式,并且被不同文化背景的人们所共知和认可,对协调人际关系、维护正常交际具有重要作用。通过对汉英语言实例的分析,探讨汉英委婉语交际效用的相似性,如避讳或避俗效用、出于礼貌效用、模糊掩饰效用等;分析委婉语在不同文化中体现的不同特色,如文化习俗差异、语言内涵不同、表达方式差异等。     

少数民族服饰的伦理学研究

本文试图从少数民族服饰与伦理学相互联系、相互作用的角度出发,挖掘蕴涵在少数民族服饰中的伦理观念,说明少数民族服饰是民族伦理观物化的标识。     

Estimation and selection procedures in regression: An L1 approach

The authors consider the problem of estimating a regression function go involving several variables by the closest functional element of a prescribed class _G that is closest to it in the L₁ norm. They propose a new estimator ? based on independent observations and give explicit finite sample bounds for the L₁distance between ?g and go. They apply their estimation procedure to the problem of selecting the smoothing parameter in nonparametric regression.     

不同模覆盖系的模倒数之和

构造性证明了当Z的不同模覆盖系最小模为2,3与4时,其模倒数之和可任意接近于1或2,并提出两个未解决问题.     

An Approximation Algorithm for Alignment of Multiple Sequences using Motif Discovery

Given a set of N sequence, the Multiple Sequence Alignment problem is to align these N sequences, possibly with gaps, that brings out the best commonality of the N sequences. The quality of the alignment is usually measured by penalizing the mis-matches and gaps, and rewarding the matches with appropriate weight functions. However for larger values of N, additional constraints are required to give meaningful alignments. We identify a user-controlled parameter, an alignment number K (2 K N): this additional requirement constrains the alignment to have at least K sequences agree on a character, whenever possible, in the alignment. We identify a natural optimization problem for this approach called the K-MSA problem. We show that the problem is MAX SNP hard. We give a natural extension of this problem that incorporates biological relevance by using motifs (common patterns in the sequences) and give an approximation algorithm for this problem in terms of the motifs in the data. MUSCA is an implementation of this approach and our experimental results indicate that this approach is efficient, particularly on large numbers of long sequences, and gives good alignments when tested on biological data such as DNA and protein sequences.     

Preemptive Machine Covering on Parallel Machines

This paper investigates the preemptive parallel machine scheduling to maximize the minimum machine completion time. We first show the off-line version can be solved in O(mn) time for general m-uniform-machine case. Then we study the on-line version. We show that any randomized on-line algorithm must have a competitive ratio m for m-uniform-machine case and ∑_{i = 1}^m1/i for m-identical-machine case. Lastly, we focus on two-uniform-machine case. We present an on-line deterministic algorithm whose competitive ratio matches the lower bound of the on-line problem for every machine speed ratio s≥ 1. We further consider the case that idle time is allowed to be introduced in the procedure of assigning jobs and the objective becomes to maximize the continuous period of time (starting from time zero) when both machines are busy. We present an on-line deterministic algorithm whose competitive ratio matches the lower bound of the problem for every s≥ 1. We show that randomization does not help.