Search

In this paper, we introduce a squared metric k-facility location problem (SM-k-FLP) which is a generalization of the squared metric facility location problem and k-facility location problem (k-FLP). In the SM-k-FLP, we are given a client set C and a facility set F from a metric space, a facility opening cost fi ≥ 0 for each i ∈ F, and an integer k. The goal is to open a facility subset F ⊆ F with |F| ≤ k and to connect each client to the nearest open facility such that the total cost (including facility opening cost and the sum of squares of distances) is minimized. Using local search and scaling techniques, we offer a constant approximation algorithm for the SM-k-FLP. [ABSTRACT FROM AUTHOR]

To describe the morphometry of iliac columns for transiliac screw and to testify the conformity among the anatomic measurement, two-dimensional (2D) and three-dimensional (3D) computed tomography. We evaluated the length, inner width, and angle of three screw trajectories starting at the iliac tubercle, posterior superior iliac spine, and posterior inferior iliac spine toward the anterior inferior iliac spine. Measurements were made on specimen, two- and 3D computed tomography using 18 embalmed cadaveric pelves. There was no significant difference among three measure methods. The path between the posterior superior iliac spine and anterior inferior iliac spine had the largest iliac column length, with 135 mm in male and 110 mm in female. The canal allowed placement of 8-mm screw in male and 6.5 mm in female with the angle of 25° laterally directed from the midsagittal plane. The line between the posterior inferior iliac spine and anterior inferior iliac spine was below or just located at the top of greater sciatic notch in the majority measurements. The safe section for transiliac screw approximately located above the greater sciatic notch and could be divided into anterior and posterior parts. The measurements among anatomic measurement, 2D and 3D computed tomography are consistent. The screw path from the posterior superior iliac spine toward anterior inferior iliac spine provided the longest anchor site. At the same time, the line between the posterior inferior iliac spine and anterior inferior iliac spine is not available for transiliac screw insertion of eastern population. The posterior of the safe section also can be regarded as another ilium anchorage area for transiliac screws. [ABSTRACT FROM AUTHOR]

We consider the MAX -DIRECTED-BISECTION problem, i.e., partitioning the vertices of a directed graph into two blocks of equal cardinality so as to maximize the total weight of the edges in the directed cut. A polynomial approximation algorithm using a semidefinite relaxation with 0.6458 performance guarantee is presented for the problem. The previous best-known results for approximating this problem are 0.5 using a linear programming relaxation, 0.6440 using a semidefinite relaxation. We also consider the MAX -DENSE-SUBGRAPH problem, i.e., determine a block of half the number of vertices from a weighted undirected graph such that the sum of the edge weights, within the subgraph induced by the block, is maximized. We present an 0.6236 approximation of the problem as opposed to 0.6221 of Halperin and Zwick. [ABSTRACT FROM AUTHOR]

We consider the MAX \fr/math>-DIRECTED-BISECTION problem, i.e., partitioning the vertices of a directed graph into two blocks of equal cardinality so as to maximize the total weight of the edges in the directed cut. A polynomial approximation algorithm using a semidefinite relaxation with 0.6458 performance guarantee is presented for the problem. The previous best-known results for approximating this problem are 0.5 using a linear programming relaxation, 0.6440 using a semidefinite relaxation. We also consider the MAX \fr/math>-DENSE-SUBGRAPH problem, i.e., determine a block of half the number of vertices from a weighted undirected graph such that the sum of the edge weights, within the subgraph induced by the block, is maximized. We present an 0.6236 approximation of the problem as opposed to 0.6221 of Halperin and Zwick. [ABSTRACT FROM AUTHOR]

Abstract Given a directed graph G and an edge weight function w : A(G) → R+ the maximum directed cut problem (MAX DICUT) is that of finding a directed cut δ(S) with maximum total weight. We consider a version of MAX DICUT -- MAX DICUT with given sizes of parts or MAX DICUT WITH GSP -- whose instance is that of MAX DICUT plus a positive integer k, and it is required to find a directed cut δ(S) having maximum weight over all cuts δ(S) with |S|=k. We present an approximation algorithm for this problem which is based on semidefinite programming (SDP) relaxation. The algorithm achieves the presently best performance guarantee for a range of k. [ABSTRACT FROM AUTHOR]