Search

This paper provides a comprehensive convergence analysis of the PoA of both pure and mixed Nash equilibria in atomic congestion games with unsplittable demands., 57 pages

Team formation plays an essential role in the labor market. In this paper, we propose two bicriteria algorithms to construct a balance between gain and cost in a team formation problem under the streaming model, subject to a cardinality constraint. We formulate the problem as maximizing the difference of a non-negative normalized monotone submodular function and a non-negative linear function. As an extension, we also consider the case where the first function is $$\gamma $$ -weakly submodular. Combining the greedy technique with the threshold method, we present bicriteria streaming algorithms and give detailed analysis for both of these models. Our analysis is competitive with that in Ene’s work.

In this paper, we introduce the selfish bin packing problem under a new version of cost sharing mechanism based on harmonic mean. The items (as agents) are selfish and intelligent to minimize the cost they have to pay, by selecting a proper bin to fit in. The tricky part is that the one with bigger size pays less and vice versa. We present the motivations and prove the existence of pure Nash Equilibrium under this new defined cost sharing mechanism. Then we study the Price of Anarchy, which is the ratio between the objective value of worst Nash Equilibrium and that of the optimum in the case with central decision maker. We prove the upper bound to be approximately 1.722 and show a 5/3 lower bound for this problem. We then include punishment into the model and prove that in this new model, the Price of Anarchy could be decreased to 3/2.

Relevance and diversity are two desirable properties in data retrieval applications, an important field in data science and machine learning. In this paper, we consider three maximization problems to balance these two factors. The objective function in each problem is the sum of a monotone submodular function f and a supermodular function g, where f and g capture the relevance and diversity of any feasible solution, respectively. In the first problem, we consider a special supermodular diversity function g of a sum-sum format satisfying the relaxed triangle inequality, for which we propose a greedy-type approximation algorithm with an $$\left( 1-1/e,1/(2\alpha )\right) $$ -bifactor approximation ratio, improving the previous $$\left( 1/(2\alpha ),1/(2\alpha )\right) $$ -bifactor approximation ratio. In the second problem, we consider an arbitrary supermodular diversity function g, for which we propose a distorted greedy method to give a $$\min \left\{ 1-k_{f}e^{-1},1-k^{g}e^{-(1-k^{g})}\right\} $$ -approximation algorithm, improving the previous $$k_f^{-1}\left( 1-e^{-k_f(1-k^{g})}\right) $$ -approximation ratio, where $$k_f$$ and $$k^g$$ are the curvatures of the submodular function f and the supermodular funciton g, respectively. In the third problem, we generalize the uniform matroid constraint to the p matroid constraints, for which we present a local search algorithm to improve the previous $$\frac{1-k^g}{(1-k^g)k^f+p}$$ -approximation ratio to $$\min \left\{ \frac{p+1-k_f}{p(p+1)},\left( \frac{1-k^g}{p}+\frac{k^g(1-k^g)^2}{p+(1-k^g)^2}\right) \right\} $$ .

In this paper, we consider the Bregman k-means problem (BKM) which is a variant of the classical k-means problem. For an n-point set $${\mathcal {S}}$$ and $$k \le n$$ with respect to $$\mu $$ -similar Bregman divergence, the BKM problem aims first to find a center subset $$C \subseteq {\mathcal {S}}$$ with $$ \mid C \mid = k$$ and then separate $${\mathcal {S}}$$ into k clusters according to C, such that the sum of $$\mu $$ -similar Bregman divergence from each point in $${\mathcal {S}}$$ to its nearest center is minimized. We propose a $$\mu $$ -similar BregMeans++ algorithm by employing the local search scheme, and prove that the algorithm deserves a constant approximation guarantee. Moreover, we extend our algorithm to solve a variant of BKM called noisy $$\mu $$ -similar Bregman k-means++ (noisy $$\mu $$ -BKM++) which is BKM in the noisy scenario. For the same instance and purpose as BKM, we consider the case of sampling a point with an imprecise probability by a factor between $$1-\varepsilon _1$$ and $$1+ \varepsilon _2$$ for $$\varepsilon _1 \in [0,1)$$ and $$\varepsilon _2 \ge 0$$ , and obtain an approximation ratio of $$O(\log ^2 k)$$ in expectation.

The spherical k-means problem (SKMP) is an important variant of the k-means clustering problem (KMP). In this paper, we consider the SKMP, which aims to divide the n points in a given data point set $${\mathcal {S}}$$ into k clusters so as to minimize the total sum of the cosine dissimilarity measure from each data point to their respective closest cluster center. Our main contribution is to design an expected constant approximation algorithm for the SKMP by integrating the seeding algorithm for the KMP and the local search technique. By utilizing the structure of the clusters, we further obtain an improved LocalSearch++ algorithm involving $$\varepsilon k$$ local search steps.

In this paper, we study the k-level facility location problem with outliers (k-LFLPWO), which is an extension of the well-known k-level facility location problem (k-LFLP). In the k-LFLPWO, we are given k facility location sets, a client location set of cardinality n and a non-negative integer $$q

In this paper, we consider the $$\tau $$ -relaxed soft capacitated facility location problem ( $$\tau $$ -relaxed SCFLP), which extends several well-known facility location problems like the squared metric soft capacitated facility location problem (SMSCFLP), soft capacitated facility location problem (SCFLP), squared metric facility location problem and uncapacitated facility location problem. In the $$\tau $$ -relaxed SCFLP, we are given a facility set $$\mathcal {F}$$ , a client set and a parameter $$\tau \ge 1$$ . Every facility $$i \in \mathcal {F}$$ has a capacity $$u_i$$ and an opening cost $$f_i$$ , and can be opened multiple times. If facility i is opened l times, this facility can be connected by at most $$l u_i$$ clients and incurs an opening cost of $$l f_i$$ . Every facility-client pair has a connection cost. Under the assumption that the connection costs are non-negative, symmetric and satisfy the $$\tau $$ -relaxed triangle inequality, we wish to open some facilities (once or multiple times) and connect every client to an opened facility without violating the capacity constraint so as to minimize the total opening costs as well as connection costs. As our main contribution, we propose a primal-dual based $$(3 \tau + 1)$$ -approximation algorithm for the $$\tau $$ -relaxed SCFLP. Furthermore, our algorithm not only extends the applicability of the primal-dual technique but also improves the previous approximation guarantee for the SMSCFLP from $$11.18+ \varepsilon $$ to 10.

Submodular optimization has been well studied in combinatorial optimization. However, there are few works considering about non-submodular optimization problems which also have many applications, such as experimental design, some optimization problems in social networks, etc. In this paper, we consider the maximization of non-submodular function under a knapsack constraint, and explore the performance of the greedy algorithm, which is characterized by the submodularity ratio $$\beta $$ and curvature $$\alpha $$ . In particular, we prove that the greedy algorithm enjoys a tight approximation guarantee of $$ (1-e^{-\alpha \beta })/{\alpha }$$ for the above problem. To our knowledge, it is the first tight constant factor for this problem. We further utilize illustrative examples to demonstrate the performance of our algorithm.

Correlation clustering problem is a clustering problem which has many applications such as protein interaction networks, cross-lingual link detection, communication networks, and social computing. In this paper, we introduce two variants of correlation clustering problem: correlation clustering problem on uncertain graphs and correlation clustering problem with non-uniform hard constrained cluster sizes. Both problems overcome part of the limitations of the existing variants of correlation clustering problem and have practical applications in the real world. We provide a constant approximation algorithm and two approximation algorithms for the former and the latter problem, respectively.

Hard-capacitated k-means (HCKM) is one of the fundamental problems remaining open in combinatorial optimization and engineering. In HCKM, one is required to partition a given n-point set into k disjoint clusters with known capacity so as to minimize the sum of within-cluster variances. It is known to be at least APX-hard, and most of the work on it has been done from a meta heuristic or bi-criteria approximation perspective. To the best our knowledge, no constant approximation algorithm or existence proof of such an algorithm is known. As our main contribution, we propose an FPT(k) approximation algorithm with constant performance guarantee for HCKM in this paper.

Spherical k-means clustering as a known NP-hard variant of the k-means problem has broad applications in data mining. In contrast to k-means, it aims to partition a collection of given data distributed on a spherical surface into k sets so as to minimize the within-cluster sum of cosine dissimilarity. In the paper, we introduce spherical k-means clustering with penalties and give a $$2\max \{2,M\}(1+M)(\ln k+2)$$-approximation algorithm. Moreover, we prove that when against spherical k-means clustering with penalties but on separable instances, our algorithm is with an approximation ratio $$2\max \{3,M+1\}$$ with high probability, where M is the ratio of the maximal and the minimal penalty cost of the given data set.

In this paper, we consider the uniform capacitated k-means problem (UC-k-means), an extension of the classical k-means problem (k-means) in machine learning. In the UC-k-means, we are given a set $$\mathcal {D}$$ of n points in d-dimensional space and an integer k. Every point in the d-dimensional space has an uniform capacity which is an upper bound on the number of points in $$\mathcal {D}$$ that can be connected to this point. Every two-point pair in the space has an associated connecting cost, which is equal to the square of the distance between these two points. We want to find at most k points in the space as centers and connect every point in $$\mathcal {D}$$ to some center without violating the capacity constraint, such that the total connecting costs is minimized. Based on the technique of local search, we present a bi-criteria approximation algorithm, which has a constant approximation guarantee and violates the cardinality constraint within a constant factor, for the UC-k-means.

The problem of maximizing a normalized monotone non-submodular set function subject to a cardinality constraint arises in the context of extracting information from massive streaming data. In this paper, we present four streaming algorithms for this problem by utilizing the concept of diminishing-return ratio. We analyze these algorithms to obtain the corresponding approximation ratios, which generalize the previous results for the submodular case. The numerical experiments show that our algorithms have better solution quality and competitive running time when compared to an existing algorithm.

In many kinds of games with economic significance, it is very important to study the submodularity of functions. In this paper, we mainly study the problem of maximizing a concave function over an intersection of two matroids. We obtain that the submodularity may not be preserved, but it involves one maximal submodular problem (or minimal supermodular problem) with some conditions. Moreover, we also present examples showing that these conditions can be satisfied.

Maximizing constrained submodular functions lies at the core of substantial machine learning and data mining. Specially, the case that the data come in a streaming fashion receives more attention in recent decades. In this work, we study the approximation algorithm for maximizing a non-decreasing set function under d-knapsack constraint. Based on the diminishing-return ratio for set functions, a non-trivial algorithm is devised for maximizing the set function without submodularity. Our results cover some known results and provide an effective method for the maximization on set functions no matter they are submodular or not. We also run the algorithm to handle the application of support selection for sparse linear regression. Numerical results show that the output quality of the algorithm is good.

In this paper, we investigate the problem of minimizing the ratio of normalized non-negative monotone non-submodular set function f and normalized non-negative monotone set function g. We take advantage of the greedy technique and get a performance guarantee depending on the generalized curvature and inverse generalized curvature of f, as well as the submodularity ratio of g. Our results generalize the works of Bai et al. (Algorithms for optimizing the ratio of submodular functions. In: Proceedings of the 33rd International Conference on Machine Learning, 2016) and Qian et al. (Optimizing ratio of monotone set functions. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence, 2017).

In this paper, we consider a variant of the classical uncapacitated facility location problem, so-called squared metric two-stage stochastic facility location problem (SM-2-SFLP) which can treat the uncertainty of the set of clients and facility costs. We assume that the connection cost is squared metric, a variant of the metric case which is widely researched. We give a new 0–1 integer linear programming for SM-2-SFLP. Based on the new formulation, we apply two known algorithms to SM-2-SFLP, and analyze the approximation ratio and per-scenario bound respectively.

Belief Propagation (BP), a distributed, message-passing algorithm, has been widely used in different disciplines including information theory, artificial intelligence, statistics and optimization problems in graphical models such as Bayesian networks and Markov random fields. Despite BP algorithm has a great success in many application fields and many progress about BP algorithm has been made, the rigorous analysis about the correctness and convergence of BP algorithm are known in only a few cases for arbitrary graph. In this paper, we will investigate the correctness and convergence of BP algorithm for determining the optimal solutions of the Chinese postman problem in both undirected and directed graphs. As a main result, we prove that BP algorithm converges to the optimal solution of the undirected Chinese postman problem within O(n) iterations where n represents the number of vertices, provided that the optimal solution is unique. For the directed case, we consider the directed Chinese postman problem with capacity and show that BP algorithm also converges to its optimal solution after O(n) iterations, as long as its corresponding linear programming relaxation has the unique optimal solution.

In this paper, we study the sum of squares facility location problem (SOS-FLP) which is an important variant of k-means clustering. In the SOS-FLP, we are given a client set $$ \mathcal {C} \subset \mathbb {R}^p$$ and a uniform center opening cost $$f>0$$ . The goal is to open a finite center subset $$F \subset \mathbb {R}^p$$ and to connect each client to the closest open center such that the total cost including center opening cost and the sum of squares of distances is minimized. The SOS-FLP is introduced firstly by Bandyapadhyay and Varadarajan (in: Proceedings of SoCG 2016, Article No. 14, pp 14:1–14:15, 2016) which present a PTAS for the fixed dimension case. Using local search and scaling techniques, we offer the first constant approximation algorithm for the SOS-FLP with general dimension. We further consider the discrete version of SOS-FLP, in which we are given a finite candidate center set with nonuniform opening cost comparing with the aforementioned (continue) SOS-FLP. By exploring the structures of local and optimal solutions, we claim that the approximation ratios are $$7.7721+ \epsilon $$ and $$9+ \epsilon $$ for the continue and discrete SOS-FLP respectively.

We investigate the maximum directed cut (MaxDC) problem by designing a spectral partitioning algorithm. Given a directed graph with nonnegative arc weights, we wish to obtain a bipartition of the vertices such that the total weight of the directed cut arcs is maximized. Relaxing the MaxDC problem as a quadratic program allows us to explore combinatorial properties of the optimal solution, leading to a 0.272-approximation algorithm via the technique of spectral partitioning rounding.

Active friending is a problem in social networks that is to assist a user to build a relationship to a target user by sending invitations to a set of intermediate users; the goal is to maximize the acceptance probability at the target node taking advantage of the social influence through the network formed by the intermediate nodes. In this paper, we convert the original formulated active friending problem of nonsubmodular maximization subject to cardinality constraint into a submodular cost submodular knapsack problem in the IC model, and we show that the two problems are equivalent. We similarly make the conversion on the active friending in the LT model. Then we give a general combinatorial optimization algorithm to solve active friending problems in both the IC model and the LT model with a guaranteed approximation. We analyze the computational complexity of the problem and the algorithm performance. The effectiveness of the generalized method is verified on real data sets.

In this paper, we study the k-means problem with (nonuniform) penalties (k-MPWP) which is a natural generalization of the classic k-means problem. In the k-MPWP, we are given an n-client set $$ {\mathcal {D}} \subset {\mathbb {R}}^d$$ , a penalty cost $$p_j>0$$ for each $$j \in {\mathcal {D}}$$ , and an integer $$k \le n$$ . The goal is to open a center subset $$F \subset {\mathbb {R}}^d$$ with $$ |F| \le k$$ and to choose a client subset $$P \subseteq {\mathcal {D}} $$ as the penalized client set such that the total cost (including the sum of squares of distance for each client in $$ {\mathcal {D}} \backslash P $$ to the nearest open center and the sum of penalty cost for each client in P) is minimized. We offer a local search $$( 81+ \varepsilon )$$ -approximation algorithm for the k-MPWP by using single-swap operation. We further improve the above approximation ratio to $$( 25+ \varepsilon )$$ by using multi-swap operation.

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 $$\mathcal {C}$$ and a facility set $$\mathcal {F} $$ from a metric space, a facility opening cost $$f_i \ge 0$$ for each $$ i \in \mathcal {F}$$ , and an integer k. The goal is to open a facility subset $$F \subseteq \mathcal {F}$$ with $$ |F| \le 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.

In this paper, we consider the robust facility leasing problem (RFLE), which is a variant of the well-known facility leasing problem. In this problem, we are given a facility location set, a client location set of cardinality n, time periods $$\{1, 2, \ldots , T\}$$ and a nonnegative integer $$q < n$$ . At each time period t, a subset of clients $$D_{t}$$ arrives. There are K lease types for all facilities. Leasing a facility i of a type k at any time period s incurs a leasing cost $$f_i^{k}$$ such that facility i is opened at time period s with a lease length $$l_k$$ . Each client in $$D_t$$ can only be assigned to a facility whose open interval contains t. Assigning a client j to a facility i incurs a serving cost $$c_{ij}$$ . We want to lease some facilities to serve at least $$n-q$$ clients such that the total cost including leasing and serving cost is minimized. Using the standard primal–dual technique, we present a 6-approximation algorithm for the RFLE. We further offer a refined 3-approximation algorithm by modifying the phase of constructing an integer primal feasible solution with a careful recognition on the leasing facilities.

In this paper, we consider the maximum and minimum versions of degree-concentrated fault-tolerant spanning subgraph problem which has many applications in network communications. We prove that both this two problems are NP-hard. For the maximum version, we use DC programming relaxation to propose a heuristic algorithm. Numerical tests indicate that the proposed algorithm is efficient and effective. For the minimum version, we also formulate it as a DC program, and show that the DC algorithm does not perform well for this problem.

The single-dipped domain can be used to model any allocation problem where a single output must be chosen in an interval with the assumption that agents’ preferences have a single most loathful point (the dip) in the interval, and the preferences are increasing as one moves away from that dip. Practical domains like this appear in political voting system where each voter has his most-hated candidate and alternative candidates are evaluated by their proximity to this candidate or in obnoxious location problem, where each agent prefers to have the obnoxious location to be distant from his own location, among others. We first characterize deterministic and anonymous strategy-proof and group strategy-proof mechanisms on single-dipped public policy domain, complementing the well-known results on single-peaked policy domain first investigated by Moulin (Pub. Choice 35:437–455, 1980). Then we consider the tradeoff between strategy-proofness and efficiency by applying our characterization. As concrete applications of our results, we extend existing models and results, and resolve several open questions related to the obnoxious facility location game from the algorithmic mechanism design literature.

We present a $$(20+{5}/{n})$$(20+5/n)-approximation algorithm for the non-uniform soft capacitated k-facility location problem, violating the capacitated constrains by no more than a factor of 25. The main technique is based on the primal---dual algorithm for the soft capacitated facility location problem, and the exploitation of the combinatorial structure of the fractional solution for the soft capacitated k-facility location problem.

In the uniform capacitated k-facility location problem (UC-k-FLP), we are given a set of facilities and a set of clients. Every client has a demand. Every facility have an opening cost and an uniform capacity. For each client–facility pair, there is an unit service cost to serve the client with unit demand by the facility. The total demands served by a facility cannot exceed the uniform capacity. We want to open at most k facilities to serve all the demands of the clients without violating the capacity constraint such that the total opening and serving cost is minimized. The main contribution of this work is to present the first combinatorial bi-criteria approximation algorithm for the UC-k-FLP by violating the cardinality constraint.

In this work, we consider the robust/soft-capacitated 2-level facility location problems. For the robust version, we propose a primal-dual based $$(3+\epsilon )$$ -approximation algorithm via construction of an adapted instance which explores some open facilities in the optimal solution. For the soft-capacitated version, we propose a $$ (4+ 1/ (e-1) +\epsilon )$$ -approximation algorithm via construction of the associated uncapacitated version whose connection cost is re-defined appropriately.

In this article, we investigate the dynamic (multi-period) facility location problem with potentially unserved clients or outliers. We propose a 3-approximation primal-dual algorithm based on an integer linear program formulation of the problem. We further improve the approximation ratio to 2 by combining the cost scaling and greedy improvement techniques.

In this paper, we consider the generalized prize-collecting Steiner forest problem, extending the prize-collecting Steiner forest problem. In this problem, we are given a connected graph $$G = (V, E)$$ and a set of vertex sets $${\mathcal {V}} = \{V_1, V_2,\cdots , V_{l}\}$$ . Every edge in E has a nonnegative cost, and every vertex set in $${\mathcal {V}}$$ has a nonnegative penalty cost. For a given edge set $$F\subseteq E$$ , vertex set $$V_i\in {\mathcal {V}}$$ is said to be connected by edge set F if $$V_i$$ is in a connected component of the F-spanned subgraph. The objective is to find such an edge set F such that the total edge cost in F and the penalty cost of the vertex sets not connected by F is minimized. Our main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method.

In this paper, we consider the k-prize-collecting Steiner tree problem (k-PCST), extending both the prize-collecting Steiner tree problem (PCST) and the k-minimum spanning tree problem (k-MST). In this problem, we are given a connected graph \(G = (V, E)\), a root vertex r and an integer k. Every edge in E has a nonnegative cost. Every vertex in V has a nonnegative penalty cost. We want to find an r-rooted tree F that spans at least k vertices such that the total cost, including the edge cost of the tree F and the penalty cost of the vertices not spanned by F, is minimized. Our main contribution is to present a 5-approximation algorithm for the k-PCST via the methods of primal–dual and Lagrangean relaxation.

Enhanced indexation aims to construct a portfolio to track and outperform the performance of a stock market index by employing both passive and active fund management strategies. This paper presents a novel sparse enhanced indexation model with chance and cardinality constraints. Its goal is to maximize the excess return that can be attained with a high probability, while the model allows a fund manger to limit the number of stocks in the portfolio and specify the maximum tolerable relative market risk. In particular, we model the asset returns as random variables and estimate their probability distributions by the Capital Asset Pricing Model or Fama-French 3-factor model, and measure the relative market risk with the coherent semideviation risk function. We deal with the chance constraint via distributionally robust approach and present a second-order cone programming and a semidefinite programming safe approximation for the model under different sets of potential distribution functions. A hybrid genetic algorithm is applied to solve the NP-hard problem. Numerical tests are conducted on the real data sets from major international stock markets, including USA, UK, Germany and China. The results demonstrate that the proposed model and the method can efficiently solve the enhanced indexation problem and our approach can generally achieve sparse tracking portfolios with good out-of-sample excess returns and high robustness.

In this paper, we consider an extension of the classical facility location problem, namely k-facility location problem with linear penalties. In contrast to the classical facility location problem, this problem opens no more than k facilities and pays a penalty cost for any non-served client. We present a local search algorithm for this problem with a similar but more technical analysis due to the extra penalty cost, compared to that in Zhang (Theoretical Computer Science 384:126–135, 2007). We show that the approximation ratio of the local search algorithm is $$2 + 1/p + \sqrt{3+ 2/p+ 1/p^2} + \epsilon $$ , where $$p \in {\mathbb {Z}}_+$$ is a parameter of the algorithm and $$\epsilon >0$$ is a positive number.

We study a precedence-constrained identical parallel machine scheduling problem with rejection. There is a communication delay between any two jobs connected in the precedence network where jobs may be rejected with penalty. The goal is to minimize the sum of the makespan and the rejection cost. We propose two 3-approximation algorithms for this problem under linear and submodular rejection costs respectively. These two algorithms are both based on linear programming rounding technique.

We consider the nth power metric facility location problem with linear penalties (M $$^n$$ FLPLP) in this work, extending both the nth power metric facility location problem (M $$^n$$ FLP) and the metric facility location problem with linear penalties (MFLPLP). We present an LP-rounding based approximation algorithm to the M $$^n$$ FLPLP with bi-factor approximation ratio $$(\gamma _f, \gamma _c)$$ , where $$\gamma _f$$ and $$\gamma _c$$ are the ratios corresponding to facility, and connection and penalty costs respectively. Finally we show that the bi-factor curve is close to the lower bound $$(\gamma _f, 1 + (3^n - 1) e^{-\gamma _f})$$ when the facility factor $$\gamma _f > 2$$ for the M $$^2$$ FLPLP.

The universal facility location problem generalizes several classical facility location problems, such as the uncapacitated facility location problem and the capacitated location problem (both hard and soft capacities). In the universal facility location problem, we are given a set of demand points and a set of facilities. We wish to assign the demands to facilities such that the total service as well as facility cost is minimized. The service cost is proportional to the distance that each unit of the demand has to travel to its assigned facility. The open cost of facility i depends on the amount z of demand assigned to i and is given by a cost function $$f_i(z)$$fi(z). In this work, we extend the universal facility location problem to include linear penalties, where we pay certain penalty cost whenever we refuse serving some demand points. As our main contribution, we present a ($$7.88+\epsilon $$7.88+∈)-approximation local search algorithm for this problem.

The fracture of the distal ulna and radius is a kind of fracture that results in high morbidity and occurrence rate and contributes to about one-sixth of the entire body’s fracture. In this study, we implemented the improved palmar wrist surgery by a volar wrist dual channel approach. Between 2011 and 2014, we have treated 67 distal radius fracture patients. We divided them into two parts randomly, and treat them by the Carpometacarpal direct approach solution and dual wrist palmar surgical approach solution respectively. After the surgery, the differences in the incidence of median nerve irritation are significant (P

Graph partition problems have been investigated extensively in combinatorial optimization. In this work, we consider an important graph partition problem which has applications in the design of VLSI circuits, namely, the balanced Max-3-Uncut problem. We formulate the problem as a discrete linear program with complex variables and propose an approximation algorithm with an approximation ratio of 0.3456 using a semidefinite programming rounding technique along with a greedy swapping step afterwards to guarantee the balanced constraint. Our analysis utilizes a bivariate function, rather than the univariate function in previous work.

The purpose of the study was to describe the anatomical variations of the connection between the flexor hallucis longus (FHL) and flexor digitorum longus (FDL) tendons in the knot of Henry in Asians, and quantify the length of FHL tendon graft with different incisions.Sixty-four embalmed feet of 32 cadavers were analyzed anatomically with respect to the individual cross-links in the planta pedis. Single incision technique graft length was measured from the musculotendinous junction of FHL and the point at sustentaculum tali. Double incision technique was measured from musculotendinous junction of FHL and the level of the master knot of Henry. Additionally, minimally invasive incision technique was measured from musculotendinous junction of FHL to the first interphalangeal joint. These three techniques were then combined to determine the total potential tendon graft length obtainable using different approach.Only two different configurations were found. Type 1, a tendinous slip branched from the FHL to the FDL (62 of 64 feet). Type 2, a slip branched from the FHL to the FDL and another slip from the FDL to FHL (2 of 64). The average length of the FHL graft available from a single incision measured 5.08 cm (range 3.32-10.35, SD = 1.09), double incision technique measured 6.72 cm (range 4.69-12.09, SD = 1.03), and minimally invasive incision measured 17.49 cm (range 13.51-20.52, SD = 1.80). The difference between the lengths obtained from these three techniques was statistically significant (p0.001).The absence of no attachment and FDL tendon to the FHL between the two tendons in the foot may be more frequent than previously reported. Only two configurations of the anatomical relationship were found in this study. In over 96 % of the feet, a proximal to distal connection from the FHL to the FDL was found, which might contribute to the residual function of the lesser toes after FDL transfer.

This paper considers the priority facility location problem with penalties. The authors develop a primal-dual 3-approximation algorithm for this problem. Combining with the greedy augmentation procedure, the authors further improve the previous ratio 3 to 1.8526.

We study the two-stage stochastic facility location problem (2-SFLP) by proposing an LP (location problem)-rounding approximation algorithm with 2.3613 per-scenario bound for this problem, improving the previously best per-scenario bound of 2.4957.