A note on the generalized min-sum set cover problem

In this paper, we consider the generalized min-sum set cover problem, introduced by Azar, Gamzu, and Yin (STOC 2009). Bansal, Gupta, and Krishnaswamy (SODA 2010) give a 485-approximation algorithm for the problem. We are able to alter their algorithm and analysis to obtain a 28-approximation algorithm, improving the performance guarantee by an order of magnitude. We use concepts from α-point scheduling to obtain our improvements.     

A weighted sum over generalized Tesler matrices

We generalize previous definitions of Tesler matrices to allow negative matrix entries and negative hook sums. Our main result is an algebraic interpretation of a certain weighted sum over these matrices, which we call the Tesler function. Our interpretation uses a new class of symmetric function specializations which are defined by their values on Macdonald polynomials. As a result of this interpretation, we obtain a Tesler function expression for the Hall inner product \(\langle \Delta _f e_n, p_{1^{n}}\rangle \), where \(\Delta _f\) is the delta operator introduced by Bergeron, Garsia, Haiman, and Tesler. We also provide simple formulas for various special cases of Tesler functions which involve q, t-binomial coefficients, ordered set partitions, and parking functions. These formulas prove two cases of the recent Delta Conjecture posed by Haglund, Remmel, and the author.     

Global optimization for sum of generalized fractional functions

This paper considers the solution of generalized fractional programming (GFP) problem which contains various variants such as a sum or product of a finite number of ratios of linear functions, polynomial fractional programming, generalized geometric programming, etc. over a polytope. For such problems, we present an efficient unified method. In this method, by utilizing a transformation and a two-part linearization method, a sequence of linear programming relaxations of the initial nonconvex programming problem are derived which are embedded in a branch-and-bound algorithm. Numerical results are given to show the feasibility and effectiveness of the proposed algorithm.     

Efficient bounds for the stable set,vertex cover and set packing problems

In this paper we describe a collection of efficient algorithms that deliver approximate solution to the weighted stable set, vertex cover and set packing problems. All algorithms guarantee bounds on the ratio of the heuristic solution to the optimal solution.     

关于广义齐性Cochrane和的加权均值

研究了广义齐性Cochrane和的一些加权均值,并利用不完全区间上特征和的性质,Dirichlet函数的均值估计以及周期Bernoulli多项式的性质,得到一些较强的渐近公式．     

Minimum sum set coloring of trees and line graphs of trees

In this paper, we study the minimum sum set coloring (MSSC) problem which consists in assigning a set of x(v) positive integers to each vertex v of a graph so that the intersection of sets assigned to adjacent vertices is empty and the sum of the assigned set of numbers to each vertex of the graph is minimum. The MSSC problem occurs in two versions: non-preemptive and preemptive. We show that the MSSC problem is strongly NP-hard both in the preemptive case on trees and in the non-preemptive case in line graphs of trees. Finally, we give exact parameterized algorithms for these two versions on trees and line graphs of trees.     

Mixing of non-preemptive and preemptive repeat priority disciplines

A single server dispenses service to m priority classes. The arrival process of the ith class, i = 1, 2,…,m, is homogeneous Poisson. Service times of each class are independent, identical, arbitrarily-distributed random variables with a finite second moment. The smaller the index of a class, the higher its priority degree. For i < j, class i has preemptive priority over j if and only if j ? i > d (where d is a predetermined non-negative integer), and non-preemptive priority otherwise. An interrupted service is resumed when the system contains no costomers with higher priority, preemptive and non-preemptive. Within each priority class the FIFO rule is obeyed.The preemptive regimes analyzed are repeat with and without resampling. For a k-customer, k = 1, 2,…,n, steady-state Laplace-Stieltjes transforms, and expectations of the waiting time and the time in the system are calculated.     

Global optimization algorithm for sum of generalized polynomial ratios problem

In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum.     

Global optimization for the generalized polynomial sum of ratios problem

In this paper, a new deterministic global optimization algorithm is proposed for solving a fractional programming problem whose objective and constraint functions are all defined as the sum of generalized polynomial ratios, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. The proposed algorithm is based on reformulating the problem as a monotonic optimization problem, and it turns out that the optimal solution which is provided by the algorithm is adequately guaranteed to be feasible and to be close to the actual optimal solution. Convergence of the algorithm is shown and numerical examples are given to illustrate the feasibility and efficiency of the present algorithm.     

The exceptional set for the sum of a prime and a square

Let E(X) denote the number of natural numbers not exceeding X which cannot be written as a sum of a prime and a square. In this paper we show that for sufficiently large X we have E(X)<< X^0.982. This revised version was published online in June 2006 with corrections to the Cover Date.     

Global optimization for the sum of generalized polynomial fractional functions

In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently, the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed algorithm is feasible and can successfully be used to solve the present problem (P).     

A note on submodular set cover on matroids

We consider a problem related to the submodular set cover on polymatroids, when the ground set is the family of independent sets of a matroid. The achievement here is getting a strongly polynomial running time with respect to the ground set of the matroid even though the family of independent sets has exponential size. We also address the optimization problem of the maximization of submodular set functions on the independent sets of a matroid.     

Restricted parameter range promise set cover problems are easy

The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices.     

Calculating approximation guarantees for partial set cover of pairs

As a part of a heuristic for the fast detection of new word combinations in text streams, we consider the NP-hard Partial Set Cover of Pairs problem. There we wish to cover a maximum number of pairs of elements by a prescribed number of sets from a given set family. While the approximation ratio of the greedy algorithm for the classic Partial Set Cover problem is completely understood, the same question for covering of pairs is intrinsically more complicated, since the pairs insert some graph-theoretic structure. The best approximation guarantee for the first greedy step can be rephrased as a problem in extremal combinatorics: Assume that we may place a fixed number of subsets of fixed and equal size in a set, how many different pairs of elements can we cover? In this paper we introduce a method to calculate optimal approximation guarantees, and we demonstrate its use on the smallest set families.     

Components of generalized Kato resolvent set and single-valued extension property

In this paper, we use the constancy of certain subspace valued mappings on the components of the generalized Kato resolvent set and the equivalences of the single-valued extension property at a point 0 for operators which admit a generalized Kato decomposition to obtain a classification of the components of the generalized Kato resolvent set of operators. We also give some applications of these results.     

Exact and heuristic approaches for the set cover with pairs problem

This work deals with the set cover with pairs problem (SCPP) which is a generalization of the set cover problem (SCP). In the SCPP the elements have to be covered by specific pairs of objects, instead of a single object. We propose a new mathematical formulation using extended variables that is capable of consistently solve instances with up to 500 elements and 500 objects. We also developed an ILS heuristic which was capable of finding better solutions for several tested instances in less computational time.