Half integer extreme points in the linear relaxation of the 2-edge-connected subgraph polyhedron

This paper studies the graphs for which the linear relaxation of the 2-connected spanning subgraph polyhedron has integer or half-integer extreme points. These graphs are called quasi-integer. For these graphs, the linear relaxation of the k-edge connected spanning subgraph polyhedron is integer for all k=4r, r≥1. The class of quasi-integer graphs is closed under minors and contains for instance the class of series-parallel graphs. We discuss some structural properties of graphs which are minimally non quasi-integer graphs, then we examine some basic operations which preserve the quasi-integer property. Using this, we show that the subdivisions of wheels are quasi-integer.     

Interkulturelles Coaching – eine komplexe,systemische Herausforderung

Intercultural coaching takes place in the highly complex reality of a globalized world. The coachee is an individual acting in the situational context of his assignment and his corporate culture. He has been socialized in his own culture, but is communicating and interacting with people who have been socialized in different cultures. In order to identify and solve problems, all three aspects (person, situation, culture) have to be considered. Some aspects may have more influence than others may, but they combine in a closely interwoven system. The authors outline the theoretical background of intercultural coaching and illustrate the process with case studies.     

Lexicographically minimizing axial motions for the Euclidean TSP

A variant of the Euclidean traveling salesman problem (TSP) is defined and studied. In the three-dimensional space, the objective function is to lexicographically minimize the x-moves, then the y-moves and finally the z-moves. The 2D and 3D cases are first studied and solved as a shortest path problem. Then the approach is generalized to the d-dimensional case.     

Anonymizing binary and small tables is hard to approximate

The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization recently proposed is the k-anonymity. This approach requires that the rows in a table are clustered in sets of size at least k and that all the rows in a cluster become the same tuple, after the suppression of some records. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be NP-hard when the values are over a ternary alphabet, k=3 and the rows length is unbounded. In this paper we give a lower bound on the approximation factor that any polynomial-time algorithm can achieve on two restrictions of the problem, namely (i) when the records values are over a binary alphabet and k=3, and (ii) when the records have length at most 8 and k=4, showing that these restrictions of the problem are APX-hard.     

阅读2:用民主的方法解决矛盾:代价最小,效果最好

当资产阶级革命在17、18世纪的欧洲兴起时,为了防止封建君主专制的复辟,“并使它们(统治阶级的各个派别)最少分裂”,新兴的资产阶级恢复并完善了在中世纪的黑暗中被尘封了十几个世纪的民主制度。但是,这种制度“在这个人数很少的阶级和这     

A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem

This paper addresses a constrained two-dimensional (2D), non-guillotine restricted, packing problem, where a fixed set of small rectangles has to be placed into a larger stock rectangle so as to maximize the value of the rectangles packed. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We propose also a new fitness function to drive the optimization. The approach is tested on a set of instances taken from the literature and compared with other approaches. The experimental results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

The bandpass problem: combinatorial optimization and library of problems

A combinatorial optimization problem, called the Bandpass Problem, is introduced. Given a rectangular matrix A of binary elements {0,1} and a positive integer B called the Bandpass Number, a set of B consecutive non-zero elements in any column is called a Bandpass. No two bandpasses in the same column can have common rows. The Bandpass problem consists of finding an optimal permutation of rows of the matrix, which produces the maximum total number of bandpasses having the same given bandpass number in all columns. This combinatorial problem arises in considering the optimal packing of information flows on different wavelengths into groups to obtain the highest available cost reduction in design and operating the optical communication networks using wavelength division multiplexing technology. Integer programming models of two versions of the bandpass problems are developed. For a matrix A with three or more columns the Bandpass problem is proved to be NP-hard. For matrices with two or one column a polynomial algorithm solving the problem to optimality is presented. For the general case fast performing heuristic polynomial algorithms are presented, which provide near optimal solutions, acceptable for applications. High quality of the generated heuristic solutions has been confirmed in the extensive computational experiments. As an NP-hard combinatorial optimization problem with important applications the Bandpass problem offers a challenge for researchers to develop efficient computational solution methods. To encourage the further research a Library of Bandpass Problems has been developed. The Library is open to public and consists of 90 problems of different sizes (numbers of rows, columns and density of non-zero elements of matrix A and bandpass number B), half of them with known optimal solutions and the second half, without.     

对2/3场1-2-2区域紧逼防守战术的解析

为了弥补战术的弱点、完善战术效果,在实践中派生出了全场区域紧逼防守的多种变形、换区阵型,2/3场1-2-2区域紧逼防守战术就是其中一种。该战术适用于青少年业余比赛和训练,对促进技、战术的全面发展有着极其重要的作用。     

对2／3场1-2-2区域紧逼防守战术的解析

为了弥补战术的弱点、完善战术效果,在实践中派生出了全场区域紧逼防守的多种变形、换区阵型,2/3场1-2-2区域紧逼防守战术就是其中一种.该战术适用于青少年业余比赛和训练,对促进技、战术的全面发展有着极其重要的作用.     

Incremental Facility Location Problem and Its Competitive Algorithms

We consider the incremental version of the k-Facility Location Problem, which is a common generalization of the facility location and the k-median problems. The objective is to produce an incremental sequence of facility sets F ₁?F ₂?????F _n , where each F _k contains at most k facilities. An incremental facility sequence or an algorithm producing such a sequence is called c -competitive if the cost of each F _k is at most c times the optimum cost of corresponding k-facility location problem, where c is called competitive ratio. In this paper we present two competitive algorithms for this problem. The first algorithm produces competitive ratio 8α, where α is the approximation ratio of k-facility location problem. By recently result (Zhang, Theor. Comput. Sci. 384:126–135, 2007), we obtain the competitive ratio \(16+8\sqrt{3}+\epsilon\). The second algorithm has the competitive ratio Δ+1, where Δ is the ratio between the maximum and minimum nonzero interpoint distances. The latter result has its self interest, specially for the small metric space with Δ≤8α?1.     

Human Resource Development in Asia – Thriving on dynamism & change: Reflections from 2006 Asian HRD conference

This article discusses the experiences of the conference management team and the host (Universiti Putra Malaysia -UPM) of the Fifth Asian Conference of the Academy of Human Resource Development, held in Putrajaya, Malaysia from 2 to 5 December 2006. In reviewing the conference, the following sub-topics are used for organizing the contents of the article: HRD in Malaysia; conference theme & overview; participations/country representations and paper streams; keynote addresses; conference assessment; and conclusions. At the end, brief perspectives of the next Asian HRD conference to be held in China are also provided.     

Bounding the total domination subdivision number of a graph in terms of its order

The total domination subdivision number \(\mathrm{sd}_{\gamma _{t}}(G)\) of a graph G is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that \(\mathrm{sd}_{\gamma_{t}}(G)\leq \lfloor\frac{2n}{3}\rfloor\) for any simple connected graph G of order n≥3 other than K ₄. We also determine all simple connected graphs G with \(\mathrm{sd}_{\gamma_{t}}(G)=\lfloor\frac{2n}{3}\rfloor\).     

Honeynet games: a game theoretic approach to defending network monitors

A honeynet is a portion of routed but otherwise unused address space that is instrumented for network traffic monitoring. It is an invaluable tool for understanding unwanted Internet traffic and malicious attacks. We formalize the problem of defending honeynets from systematic mapping (a serious threat to their viability) as a simple two-person game. The objective of the Attacker is to identify a honeynet with a minimum number of probes. The objective of the Defender is to maintain a honeynet for as long as possible before moving it to a new location within a larger address space. Using this game theoretic framework, we describe and prove optimal or near-optimal strategies for both the Attacker and the Defender. This is the first mathematically rigorous study of this increasingly important problem on honeynet defense. Our theoretical ideas provide the first formalism of the honeynet monitoring problem, illustrate the viability of network address shuffling, and inform the design of next generation honeynet defense systems.