Worst-case analysis of a dynamic channel assignment strategy

We consider the problem of channel assignment in cellular networks with arbitrary reuse distance. We show upper and lower bounds for the competitive ratio of a previously proposed and widely studied version of dynamic channel assignment, which we refer to as the greedy algorithm. We study two versions of this algorithm: one that performs reassignment of channels, and one that never reassigns channels to calls. For reuse distance 2, we show tight bounds on the competitive ratio of both versions of the algorithm. For reuse distance 3, we show non-trivial lower bounds for both versions of the algorithm.     

Greedy-type resistance of combinatorial problems

This paper gives a sufficient condition for a combinatorial problem to be greedy-type resistant, i.e. such that, on some instances of the problem, any greedy-type algorithm will output the unique worst possible solution. The condition is used to show that the Equipartition, the k-Clique, the Asymmetric Traveling Salesman, the Hamiltonian Path, the Min–Max Matching, and the Assignment Problems are all greedy-type resistant.     

Greedy algorithm, arithmetic progressions, subset sums and divisibility

We consider a number of density problems for integer sequences with certain divisibility properties and sequences free of arithmetic progressions. Sequences of the latter type that are generated by a computer using modifications of the greedy algorithm are also provided.     

Sparse spectral clustering method based on the incomplete Cholesky decomposition

A novel sparse spectral clustering method using linear algebra techniques is proposed. Spectral clustering methods solve an eigenvalue problem containing a graph Laplacian. The proposed method exploits the structure of the Laplacian to construct an approximation, not in terms of a low rank approximation but in terms of capturing the structure of the matrix. With this approximation, the size of the eigenvalue problem can be reduced. To obtain the indicator vectors from the eigenvectors the method proposed by Zha et al. (2002) [26], which computes a pivoted LQ$LQ$ factorization of the eigenvector matrix, is adapted. This formulation also gives the possibility to extend the method to out-of-sample points.     

The complexity of detecting fixed-density clusters

We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let γ:N→Q₊ be any density function, i.e., γ is computable in polynomial time and satisfies γ(k)?k-1 for all k∈N. Then γ-CLUSTER is the problem of deciding, given an undirected graph G and a natural number k, whether there is a subgraph of G on k vertices that has average degree at least γ(k). For γ(k)=k-1, this problem is the same as the well-known CLIQUE problem, and thus NP-complete. In contrast to this, the problem is known to be solvable in polynomial time for γ(k)=2. We ask for the possible functions γ such that γ-CLUSTER remains NP-complete or becomes solvable in polynomial time. We show a rather sharp boundary: γ CLUSTER is NP-complete if γ=2+Ω(1/k^1-ε) for some ε>0 and has a polynomial-time algorithm for γ=2+O(1/k). The algorithm also shows that for γ=2+O(1/k^1-o(1)), γ-CLUSTER is solvable in subexponential time 2^no(1).     

ABS ALGORITHMS FOR SOLVING LINEAR INEQUALITIES

We consider a class of ABS type algorithms for solving system of linear inequalities, where the number of inequalities does not exceed the number of variables.     

Computerized generation of operational strategies for the management of temporary storage of drainage water from several polders in a network of small lakes and canals

We study the computerized generation of operational strategies for the management of temporary storage of drainage water from several polders in a network of small lakes and canals (Dutch: polder–boezem system). This network of lakes and canals functions as an intermediate storage reservoir. Pumps empty the intermediate reservoir into rivers or the sea. We suggest a way of prioritizing the allocation of pumping capacity when a prediction of future drainage to the intermediate reservoir is provided. We show that there is a greedy algorithm that allocates pump capacity for several time steps in advance and that respects the priority rules.     

The behavior of the QR-factorization algorithm with column pivoting

A bound on the performance of QR-factorization with column pivoting is derived and two classes of matrices are constructed for which the bound is sharp or asymptotically sharp.     

Automatic selection of indicators in a fully saturated regression

We consider selecting a regression model, using a variant of the general-to-specific algorithm in PcGets, when there are more variables than observations. We look at the special case where the variables are single impulse dummies, one defined for each observation. We show that this setting is unproblematic if tackled appropriately, and obtain the asymptotic distribution of the mean and variance in a location-scale model, under the null that no impulses matter. Monte Carlo simulations confirm the null distributions and suggest extensions to highly non-normal cases. An erratum to this article can be found at     

Convex Modeling of Interactions With Strong Heredity

We consider the task of fitting a regression model involving interactions among a potentially large set of covariates, in which we wish to enforce strong heredity. We propose FAMILY, a very general framework for this task. Our proposal is a generalization of several existing methods, such as VANISH, hierNet, the all-pairs lasso, and the lasso using only main effects. It can be formulated as the solution to a convex optimization problem, which we solve using an efficient alternating directions method of multipliers (ADMM) algorithm. This algorithm has guaranteed convergence to the global optimum, can be easily specialized to any convex penalty function of interest, and allows for a straightforward extension to the setting of generalized linear models. We derive an unbiased estimator of the degrees of freedom of FAMILY, and explore its performance in a simulation study and on an HIV sequence dataset. Supplementary materials for this article are available online.     

Online coloring graphs with high girth and high odd girth

We give an upper bound for the online chromatic number of graphs with high girth and for graphs with high odd girth generalizing Kierstead’s algorithm for graphs that contain neither a C₃ or C₅ as an induced subgraph.     

On greedy algorithms for series parallel graphs

This note describes some sufficient conditions for the maximum or minimum of a weighted flow (the weights are on paths, and are derived from weights on the edges of the path), of given volume in a series parallel graph to be found by a greedy algorithm.     

An improved approximation algorithm for requirement cut

This note presents improved approximation guarantees for the requirement cut problem: given an n-vertex edge-weighted graph G=(V,E), and g groups of vertices X₁,…,X_g⊆V with each group X_i having a requirement r_i between 0 and |X_i|, the goal is to find a minimum cost set of edges whose removal separates each group X_i into at least r_i disconnected components. We give a tight Θ(logg) approximation ratio for this problem when the underlying graph is a tree, and show how this implies an O(logk⋅logg) approximation ratio for general graphs, where .     

Tree-edges deletion problems with bounded diameter obstruction sets

We study the following problem: given a tree G and a finite set of trees H, find a subset O of the edges of G such that G-O does not contain a subtree isomorphic to a tree from H, and O has minimum cardinality. We give sharp boundaries on the tractability of this problem: the problem is polynomial when all the trees in H have diameter at most 5, while it is NP-hard when all the trees in H have diameter at most 6. We also show that the problem is polynomial when every tree in H has at most one vertex with degree more than 2, while it is NP-hard when the trees in H can have two such vertices.The polynomial-time algorithms use a variation of a known technique for solving graph problems. While the standard technique is based on defining an equivalence relation on graphs, we define a quasiorder. This new variation might be useful for giving more efficient algorithm for other graph problems.     

A note on coloring sparse random graphs

Coja-Oghlan and Taraz [Amin Coja-Oghlan, Anusch Taraz, Exact and approximative algorithms for coloring , Random Structures and Algorithms 24 (3) (2004) 259-278] presented a graph coloring algorithm that has expected linear running time for random graphs with edge probability p satisfying np≤1.01. In this work, we develop their analysis by exploiting generating function techniques. We show that, in fact, their algorithm colors G_n,p with the minimal number of colors and has expected linear running time, provided that np≤1.33.