Optimally Cutting a Surface into a Disk

We consider the problem of cutting a subset of the edges of a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length. We show that this problem is NP-hard in general, even for manifolds without boundary and for punctured spheres. We also describe an algorithm with running time n ^O(g+k), where n is the combinatorial complexity, g is the genus, and k is the number of boundary components of the input surface. Finally, we describe a greedy algorithm that outputs a O(log² g)-approximation of the minimum cut graph in O(g ² n log n) time.     

Heuristic Algorithms and Scatter Search for the Cardinality Constrained P||Cmax Problem

We consider the generalization of the classical P||C_max problem (assign n jobs to m identical parallel processors by minimizing the makespan) arising when the number of jobs that can be assigned to each processor cannot exceed a given integer k. The problem is strongly NP-hard for any fixed k > 2. We briefly survey lower and upper bounds from the literature. We introduce greedy heuristics, local search and a scatter search approach. The effectiveness of these approaches is evaluated through extensive computational comparison with a depth-first branch-and-bound algorithm that includes new lower bounds and dominance criteria.     

Increasing the Weight of Minimum Spanning Trees

The problems of computing the maximum increase in the weight of the minimum spanning trees of a graph caused by the removal of a given number of edges, or by finite increases in the weights of the edges, are investigated. For the case of edge removals, the problem is shown to be NP-hard and an Ω(1/log k)-approximation algorithm is presented for it, where (input parameter) k > 1 is the number of edges to be removed. The second problem is studied, assuming that the increase in the weight of an edge has an associated cost proportional to the magnitude of the change. An O(n³m² log(n²/m)) time algorithm is presented to solve it.     

Multiple choice tries and distributed hash tables

In this article we consider tries built from n strings such that each string can be chosen from a pool of k strings, each of them generated by a discrete i.i.d. source. Three cases are considered: k = 2, k is large but fixed, and k ? clog n. The goal in each case is to obtain tries as balanced as possible. Various parameters such as height and fill‐up level are analyzed. It is shown that for two‐choice tries a 50% reduction in height is achieved when compared with ordinary tries. In a greedy online construction when the string that minimizes the depth of insertion for every pair is inserted, the height is only reduced by 25%. To further reduce the height by another 25%, we design a more refined online algorithm. The total computation time of the algorithm is O(nlog n). Furthermore, when we choose the best among k ≥ 2 strings, then for large but fixed k the height is asymptotically equal to the typical depth in a trie. Finally, we show that further improvement can be achieved if the number of choices for each string is proportional to log n. In this case highly balanced trees can be constructed by a simple greedy algorithm for which the difference between the height and the fill‐up level is bounded by a constant with high probability. This, in turn, has implications for distributed hash tables, leading to a randomized ID management algorithm in peer‐to‐peer networks such that, with high probability, the ratio between the maximum and the minimum load of a processor is O(1). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Approximation Algorithms for Dispersion Problems

Given a collection of weighted sets, each containing at most k elements drawn from a finite base set, the k-set packing problem is to find a maximum weight sub-collection of disjoint sets. A greedy algorithm for this problem approximates it to within a factor of k, and a natural local search has been shown to approximate it to within a factor of roughly k − 1. However, neither paradigm can yield approximations that improve on this.We present an approximation algorithm for the weighted k-set packing problem that combines the two paradigms by starting with an initial greedy solution and then repeatedly choosing the best possible local improvement. The algorithm has a performance ratio of 2(k + 1)/3, which we show is asymptotically tight. This is the first asymptotic improvement over the straightforward ratio of k.     

A branch-and-bound method for the minimum k−enclosing ball problem

The minimum k-enclosing ball problem seeks the ball with smallest radius that contains at least k of m given points. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of k points to solve this problem. Our method is able to solve the problem exactly in a short amount of time for small and medium sized datasets.     

A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks

Given a directed edge-weighted graph and k source-sink pairs, the Minimum Directed Multicut Problem is to find an edge subset with minimal weight, that separates each source-sink pair. Determining the minimum multicut in directed or undirected graphs is NP-hard. The fractional version of the minimum multicut problem is dual to the maximum multicommodity flow problem. The integrality gap for an instance of this problem is the ratio of the minimum weight multicut to the minimum weight fractional multicut; trivially this gap is always at least 1 and it is easy to show that it is at most k. In the analogous problem for undirected graphs this upper bound was improved to O(log k).In this paper, for each k an explicit family of examples is presented each with k source-sink pairs for which the integrality gap can be made arbitrarily close to k. This shows that for directed graphs, the trivial upper bound of k can not be improved.* This work was supported in part by NSF grant CCR-9700239 and by DIMACS. This work was done while a postdoctoral fellow at DIMACS.     

Reoptimizing the 0-1 knapsack problem

In this paper we study the problem where an optimal solution of a knapsack problem on n items is known and a very small number k of new items arrive. The objective is to find an optimal solution of the knapsack problem with n+k items, given an optimal solution on the n items (reoptimization of the knapsack problem). We show that this problem, even in the case k=1, is NP-hard and that, in order to have effective heuristics, it is necessary to consider not only the items included in the previously optimal solution and the new items, but also the discarded items. Then, we design a general algorithm that makes use, for the solution of a subproblem, of an α-approximation algorithm known for the knapsack problem. We prove that this algorithm has a worst-case performance bound of , which is always greater than α, and therefore that this algorithm always outperforms the corresponding α-approximation algorithm applied from scratch on the n+k items. We show that this bound is tight when the classical Ext-Greedy algorithm and the algorithm are used to solve the subproblem. We also show that there exist classes of instances on which the running time of the reoptimization algorithm is smaller than the running time of an equivalent PTAS and FPTAS.     

Generalizedk-multiway cut problems

This paper considers the following problem: given an edgeweighted graphG = (V, E, w) and disjointk-subsetsU _p ofV, find a minimum weighted set of edgesE′ ?E such that its removal disconnects the graph intok parts and each part contains exactly one vertex from eachU _p for 1 ≤p ≤r. This generalizes some well-known NP-hard problems. In this paper, we first apply greedy local search algorithm to obtain better approximation solutions. Then we give a randomized local search algorithm which produces a solution within a factor (1 + ε) with the probability at least (1 - 1/e) for any small ε. Simple near-optimum approximation algorithms are also proposed. Analogously, there is a maximumk-multiway cut problem with the same restrictions.     

Exploring the constrained maximum edge-weight connected graph problem

Given an edge weighted graph, the maximum edge-weight connected graph （MECG） is a connected subgraph with a given number of edges and the maximal weight sum. Here we study a special case, i.e. the Constrained Maximum Edge-Weight Connected Graph problem （CMECG）, which is an MECG whose candidate subgraphs must include a given set of k edges, then also called the k-CMECG. We formulate the k-CMECG into an integer linear programming model based on the network flow problem. The k-CMECG is proved to be NP-hard. For the special case 1-CMECG, we propose an exact algorithm and a heuristic algorithm respectively. We also propose a heuristic algorithm for the k-CMECG problem. Some simulations have been done to analyze the quality of these algorithms. Moreover, we show that the algorithm for 1-CMECG problem can lead to the solution of the general MECG problem.     

A 17/10-approximation algorithm fork-bounded space on-line variable-sized bin packing

A version of thek-bounded space on-line bin packing problem, where a fixed collection of bin sizes is allowed, is considered. By packing large items into appropriate bins and closing appropriate bins, we can derive an algorithm with worst-case performance bound 1.7 fork≥3. This research is supported by the Science Foundation under State Education Committee of China. The earlier version was done in Institute of Applied Mathematics, Academia Sinica.     

A new asymmetric inclusion region for minimum weight triangulation

As a global optimization problem, planar minimum weight triangulation problem has attracted extensive research attention. In this paper, a new asymmetric graph called one-sided β-skeleton is introduced. We show that the one-sided circle-disconnected (?2b){(\sqrt{2}\beta)} -skeleton is a subgraph of a minimum weight triangulation. An algorithm for identifying subgraph of minimum weight triangulation using the one-sided (?2b){(\sqrt{2}\beta)} -skeleton is proposed and it runs in O(n^4/3+e+min{klogn, n²logn}){O(n^{4/3+\epsilon}+\min\{\kappa \log n, n^2\log n\})} time, where κ is the number of intersected segmented between the complete graph and the greedy triangulation of the point set.     

ON 3-CHOOSABILITY OF PLANE GRAPHS WITHOUT 6-,7- AND 9-CYCLES

The choice number of a graph G,denoted by X1(G),is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper,it is showed that X1 (G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 7- and 9-cycles.     

New Bounds on the Grundy Number of Products of Graphs

The Grundy number of a graph G is the largest k such that G has a greedy k‐coloring, that is, a coloring with k colors obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this article, we give new bounds on the Grundy number of the product of two graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:78–88, 2012     

Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem

The dynamic programming algorithm of [12.] for the bandwidth minimization problem is improved. It is shown that, for all k > 1, BANDWIDTH(k) can be solved in O(n^k) steps and simultaneous O(n^k) space, where n is the number of vertices in the graph, and that each such problem is in NSPACE(log n). The same improved dynamic programming algorithm approach works to show that the MINCUT LINEAR ARRANGEMENT problem restricted to the fixed value k, denoted by MINCUT(k), is solvable in O(n^k) steps and simultaneous O(n^k) space and is in the class NSPACE(log n).     

The number of depth-first searches of an ordered set

We show that the problems of deciding whether an ordered set has at leastk depth-first linear extensions and whether an ordered set has at leastk greedy linear extensions are NP-hard.Supported by Office of Naval Research contract N00014-85K-0494.Supported by National Science Foundation grant DMS-8713994.     

Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing

We study the average case performance of the Best Fit algorithm for on-line bin packing under the distributionU{j, k}, in which the item sizes are uniformly distributed in the discrete range {1/k, 2/k,…,j/k}. Our main result is that, in the casej = k − 2, the expected waste for an infinite stream of items remains bounded. This settles an open problem posed by Coffmanet al.[[4]]. It is also the first result which involves a detailed analysis of the infinite multidimensional Markov chain underlying the algorithm.     

An optimal time algorithm for finding a maximum weight independent set in a tree

The maximum weight independent set problem for a general graph is NP-hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, Pawagi has presented anO(|V|log|V|) time algorithm for solving this problem on a tree. In this paper, we propose anO(|V|) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor.     

A GRASP algorithm for the multi-criteria minimum spanning tree problem

This paper proposes a GRASP (Greedy Randomized Adaptive Search Procedure) algorithm for the multi-criteria minimum spanning tree problem, which is NP-hard. In this problem a vector of costs is defined for each edge of the graph and the problem is to find all Pareto optimal or efficient spanning trees (solutions). The algorithm is based on the optimization of different weighted utility functions. In each iteration, a weight vector is defined and a solution is built using a greedy randomized constructive procedure. The found solution is submitted to a local search trying to improve the value of the weighted utility function. We use a drop-and-add neighborhood where the spanning trees are represented by Prufer numbers. In order to find a variety of efficient solutions, we use different weight vectors, which are distributed uniformly on the Pareto frontier. The proposed algorithm is tested on problems with r=2 and 3 criteria. For non-complete graphs with n=10, 20 and 30 nodes, the performance of the algorithm is tested against a complete enumeration. For complete graphs with n=20, 30 and 50 nodes the performance of the algorithm is tested using two types of weighted utility functions. The algorithm is also compared with the multi-criteria version of the Kruskal’s algorithm, which generates supported efficient solutions. This work was funded by the Municipal Town Hall of Campos dos Goytacazes city. The used computer was acquired with resource of CNPq.