In this paper, we consider the problem of choosing a minimum cost set of resources for executing a specified set of jobs. Each input job is an interval, determined by its start-time and end-time. Each resource is also an interval determined by its start-time and end-time; moreover, every resource has a capacity and a cost associated with it. We consider two versions of this problem. In the partial covering version, we are also given as input a number k, specifying the number of jobs that must be performed. The goal is to choose k jobs and find a minimum cost set of resources to perform the chosen k jobs (at any point of time the capacity of the chosen set of resources should be sufficient to execute the jobs active at that time). We present an O(log n)-factor approximation algorithm for this problem. We also consider the prize collecting version, wherein every job also has a penalty associated with it. The feasible solution consists of a subset of the jobs, and a set of resources, to perform the chosen subset of jobs. The goal is to find a feasible solution that minimizes the sum of the costs of the selected resources and the penalties of the jobs that are not selected. We present a constant factor approximation algorithm for this problem
In the setting where resources and jobs are embodied as intervals, the objective of finding a minimum cost collection of resources that fulfill the jobs is typically called the full cover problem. Full cover problems in the interval context have been dealt with earlier, in various earlier works @cite_6 @cite_7 @cite_4 . Partial cover problems in the interval context have been considered earlier in @cite_0 . The work in existing literature that is closest in spirit to our result is that of Bar- @cite_6 , and @cite_0 . In @cite_6 , the authors consider the full cover version, and present a @math -approximation algorithm. In this case, all the jobs are to be covered, and therefore the demand profile to be covered is fixed. The goal is to find the minimum cost set of resources, for covering this profile. In our setting, we need to cover only @math of the jobs. A solution needs to select @math jobs to be covered in such a manner that the resources required to cover the resulting demand profile has minimum cost.
@cite_0 @cite_4 @cite_7 @cite_6
45352664 1574334008 2047220011 2003902046
An instance of the generalized partial cover problem consists of a ground set U and a family of subsets @math . Each element e∈U is associated with a profit p(e), whereas each subset @math has a cost c(S). The objective is to find a minimum cost subcollection @math such that the combined profit of the elements covered by @math is at least P, a specified profit bound. In the prize-collecting version of this problem, there is no strict requirement to cover any element; however, if the subsets we pick leave an element e∈U uncovered, we incur a penalty of π(e). The goal is to identify a subcollection @math that minimizes the cost of @math plus the penalties of uncovered elements. Although problem-specific connections between the partial cover and the prize-collecting variants of a given covering problem have been explored and exploited, a more general connection remained open. The main contribution of this paper is to establish a formal relationship between these two variants. As a result, we present a unified framework for approximating problems that can be formulated or interpreted as special cases of generalized partial cover. We demonstrate the applicability of our method on a diverse collection of covering problems, for some of which we obtain the first non-trivial approximability results. We consider the problem of allocating resources to satisfy demand requirements varying over time. The input specifies a demand for each timeslot. Each resource is specified by a start-time, end-time, an associated cost and a capacity. A feasible solution is a multiset of resources such that at any point of time, the sum of the capacities offered by the resources is at least the demand requirement at that point of time. The goal is to minimize the total cost of the resources included in the solution. This problem arises naturally in many scenarios such as workforce management, sensor networks, cloud computing, energy management and distributed computing. We study this problem under the partial cover setting and the zero-one setting. In the former scenario, the input also includes a number k and the goal is to choose a minimum cost solution that satisfies the demand requirements of at least k timeslots. For this problem, we present a 16-approximation algorithm; we show that there exist "well-structured" near-optimal solutions and that such a solution can be found in polynomial time via dynamic programming. In the zero-one setting, a feasible solution is allowed to pick at most one copy of any resource. For this case, we present a 4-approximation algorithm; our algorithm uses a novel LP relaxation involving flow-cover inequalities. In a minimum partial set multi-cover problem (MinPSMC), given an element set E, a collection of subsets ( S 2^E ), a cost (w_S ) on each set (S S ), a covering requirement (r_e ) for each element (e E ), and an integer k, the goal is to find a sub-collection ( F S ) to fully cover at least k elements such that the cost of ( F ) is as small as possible, where element e is fully covered by ( F ) if it belongs to at least (r_e ) sets of ( F ). On the application side, the problem has its background in the seed selection problem in a social network. On the theoretical side, it is a natural combination of the minimum partial (single) set cover problem (MinPSC) and the minimum set multi-cover problem (MinSMC). Although both MinPSC and MinSMC admit good approximations whose performance ratios match those lower bounds for the classic set cover problem, previous studies show that theoretical study on MinPSMC is quite challenging. In this paper, we prove that MinPSMC cannot be approximated within factor (O(n^ 1 2( n)^c ) ) under the ETH assumption. A primal dual algorithm for MinPSMC is presented with a guaranteed performance ratio (O( n ) ) when (r_ ) and f are constants, where (r_ = _ e E r_e ) is the maximum covering requirement and f is the maximum frequency of elements (that is the maximum number of sets containing a common element). We also improve the ratio for a restricted version of MinPSMC which possesses a graph-type structure. In this paper, we study the minimum partial set multi-cover problem (PSMC). Given an element set E, a collection of subsets ( S 2^E ), a cost (c_S ) on each set (S S ), a covering requirement (r_e ) for each element (e E ), and an integer k, the PSMC problem is to find a sub-collection ( F S ) to fully cover at least k elements such that the cost of ( F ) is as small as possible, where element e is fully covered by ( F ) if it belongs to at least (r_e ) sets of ( F ). This paper presents an approximation algorithm using local ratio method achieving performance ratio ( k ( 1 f-r_ + r_ r_ ) , 1 + f r_ + 1 r_ - 1 r_ -1, 1 ), where ( ) is the size of a maximum set, f is the maximum number of sets containing a common element, ( ) is the minimum percentage of elements required to be fully covered during iterations of the algorithm, and (r_ ) and (r_ ) are the maximum and the minimum covering requirement, respectively. In particular, when (r_ ) is a constant, the first term can be omitted. Notice that our ratio coincides with the classic ratio f for both the set multi-cover problem (in which case (k=|E| )) and the partial set single-cover problem (in which case (r_ =1 )). However, when (k 1 ), the ratio might be as large as ( (n) ). This result shows an interesting “shock wave like” feature of approximating PSMC. The purpose of this paper is trying to arouse some interest in such a feature and attract more work on this challenging problem. Given a set @math of m unit disks and a set @math of n points in the plane, the discrete unit disk cover problem is to select a minimum cardinality subset @math to cover @math . This problem is NP-hard [14] and the best previous practical solution is a 38-approximation algorithm by [5]. We first consider the line-separable discrete unit disk cover problem (the set of disk centers can be separated from the set of points by a line) for which we present an O(n(log n + m))-time algorithm that finds an exact solution. Combining our line-separable algorithm with techniques from the algorithm of [5] results in an O(m2n4) time 22-approximate solution to the discrete unit disk cover problem. We study the generalization of covering problems such as the set cover problem to partial covering problems. Here we only want to cover a given number k of elements rather than all elements. For instance, in the k-partial (weighted) set cover problem, we wish to compute a minimum weight collection of sets that covers at least k elements. As a main result, we show that the k-partial set cover problem and its special cases like the k-partial vertex cover problem are all fixed parameter tractable (with parameter k). As a second example, we consider the minimum weight k-partial t-restricted cycle cover problem. Given a collection @math of weighted subsets of a ground set @math , the set cover problem is to find a minimum weight subset of @math which covers all elements of @math . We study a strategic game defined upon this classical optimization problem. Every element of @math is a player which chooses one set of @math where it appears. Following a public tax function, every player is charged a fraction of the weight of the set that it has selected. Our motivation is to design a tax function having the following features: it can be implemented in a distributed manner, existence of an equilibrium is guaranteed and the social cost for these equilibria is minimized. We consider the problem of covering an input graph H with graphs from a fixed covering class G . The classical covering number of H with respect to G is the minimum number of graphs from G needed to cover the edges of H without covering non-edges of H . We introduce a unifying notion of three covering parameters with respect to G , two of which are novel concepts only considered in special cases before: the local and the folded covering number. Each parameter measures "how far" H is from G in a different way. Whereas the folded covering number has been investigated thoroughly for some covering classes, e.g.,?interval graphs and planar graphs, the local covering number has received little attention.We provide new bounds on each covering number with respect to the following covering classes: linear forests, star forests, caterpillar forests, and interval graphs. The classical graph parameters that result this way are interval number, track number, linear arboricity, star arboricity, and caterpillar arboricity. As input graphs we consider graphs of bounded degeneracy, bounded degree, bounded tree-width or bounded simple tree-width, as well as outerplanar, planar bipartite, and planar graphs. For several pairs of an input class and a covering class we determine exactly the maximum ordinary, local, and folded covering number of an input graph with respect to that covering class. The problem of scheduling jobs with interval constraints is a well-studied classical scheduling problem. The input to the problem is a collection of n jobs where each job has a set of intervals on which it can be scheduled. The goal is to minimize the total number of machines needed to schedule all jobs subject to these interval constraints. In the continuous version, the allowed intervals associated with a job form a continuous time segment, described by a release date and a deadline. In the discrete version of the problem, the set of allowed intervals for a job is given explicitly. So far, only an O(log n ( log log n))-approximation is known for either version of the problem, obtained by a randomized rounding of a natural linear programming relaxation of the problem. In fact, we show here that this analysis is tight for both versions of the problem by providing a matching lower bound on the integrality gap of the linear program. Moreover, even when all jobs can be scheduled on a single machine, the discrete case has recently been shown to be spl Omega (log log n)-hard to approximate. In this paper, we provide improved approximation factors for the number of machines needed to schedule all jobs in the continuous version of the problem. Our main result is an O(1)-approximation algorithm when the optimal number of machines needed is bounded by a fixed constant. Thus, our results separate the approximability of the continuous and the discrete cases of the problem. For general instances, we strengthen the natural linear programming relaxation in a recursive manner by forbidding certain configurations which cannot arise in an integral feasible solution. This yields an O(OPT)-approximation, where OPT denotes the number of machines needed by an optimal solution. Combined with earlier results, our work implies an O( spl radic log n (log log n))-approximation for any value of OPT. In this paper we consider the natural generalizations of two fundamental problems, the Set-Cover problem and the Min-Knapsack problem. We are given a hypergraph, each vertex of which has a nonnegative weight, and each edge of which has a nonnegative length. For a given threshold ??, our objective is to find a subset of the vertices with minimum total cost, such that at least a length of ?? of the edges is covered. This problem is called the partial set cover problem. We present an O(|V|2+|H|)-time, ?E-approximation algorithm for this problem, where ?E?2 is an upper bound on the edge cardinality of the hypergraph and |H| is the size of the hypergraph (i.e., the sum of all its edges cardinalities). The special case where ?E=2 is called the partial vertex cover problem. For this problem a 2-approximation was previously known, however, the time complexity of our solution, i.e., O(|V|2), is a dramatic improvement.We show that if the weights are homogeneous (i.e., proportional to the potential coverage of the sets) then any minimal cover is a good approximation. Now, using the local-ratio technique, it is sufficient to repeatedly subtract a homogeneous weight function from the given weight function. Several algorithms with an approximation guarantee of @math are known for the Set Cover problem, where @math is the number of elements. We study a generalization of the Set Cover problem, called the Partition Set Cover problem. Here, the elements are partitioned into @math , and we are required to cover at least @math elements from each color class @math , using the minimum number of sets. We give a randomized LP-rounding algorithm that is an @math approximation for the Partition Set Cover problem. Here @math denotes the approximation guarantee for a related Set Cover instance obtained by rounding the standard LP. As a corollary, we obtain improved approximation guarantees for various set systems for which @math is known to be sublogarithmic in @math . We also extend the LP rounding algorithm to obtain @math approximations for similar generalizations of the Facility Location type problems. Finally, we show that many of these results are essentially tight, by showing that it is NP-hard to obtain an @math -approximation for any of these problems. A longest repeat query on a string, motivated by its applications in many subfields including computational biology, asks for the longest repetitive substring(s) covering a particular string position (point query). In this paper, we extend the longest repeat query from point query to , allowing the search for longest repeat(s) covering any position interval, and thus significantly improve the usability of the solution. Our method for interval query takes a different approach using the insight from a recent work on [1], as the prior work's approach for point query becomes infeasible in the setting of interval query. Using the critical insight from [1], we propose an indexing structure, which can be constructed in the optimal @math time and space for a string of size @math , such that any future interval query can be answered in @math time. Further, our solution can find longest repeats covering any given interval using optimal @math time, where @math is the number of longest repeats covering that given interval, whereas the prior @math -time and space work can find only one candidate for each point query. Experiments with real-world biological data show that our proposal is competitive with prior works, both time and space wise, while providing with the new functionality of interval queries as opposed to point queries provided by prior works. We consider a natural generalization of the Partial Vertex Cover problem. Here an instance consists of a graph G = (V,E), a cost function c: V → ℤ + , a partition P 1, …, P r of the edge set E, and a parameter k i for each partition P i . The goal is to find a minimum cost set of vertices which cover at least k i edges from the partition P i . We call this the Partition-VC problem. In this paper, we give matching upper and lower bound on the approximability of this problem. Our algorithm is based on a novel LP relaxation for this problem. This LP relaxation is obtained by adding knapsack cover inequalities to a natural LP relaxation of the problem. We show that this LP has integrality gap of O(logr), where r is the number of sets in the partition of the edge set. We also extend our result to more general settings. Following the well-studied two-stage optimization framework for stochastic optimization [15,8], we study approximation algorithms for robust two-stage optimization problems with an exponential number of scenarios. Prior to this work, [8] introduced approximation algorithms for two-stage robust optimization problems with explicitly given scenarios. In this paper, we assume the set of possible scenarios is given implicitly, for example by an upper bound on the number of active clients. In two-stage robust optimization, we need to pre-purchase some resources in the first stage before the adversary's action. In the second stage, after the adversary chooses the clients that need to be covered, we need to complement our solution by purchasing additional resources at an inflated price. The goal is to minimize the cost in the worst-case scenario. We give a general approach for solving such problems using LP rounding. Our approach uncovers an interesting connection between robust optimization and online competitive algorithms. We use this approach, together with known online algorithms, to develop approximation algorithms for several robust covering problems, such as set cover, vertex cover, and edge cover. We also study a simple buy-at-oncealgorithm that either covers all items in the first stage or does nothing in the first stage and waits to build the complete solution in the second stage. We show that this algorithm gives tight approximation factors for unweighted variants of these covering problems, but performs poorly for general weighted problems. The well-known @math -disjoint path problem ( @math -DPP) asks for pairwise vertex-disjoint paths between @math specified pairs of vertices @math in a given graph, if they exist. The decision version of the shortest @math -DPP asks for the length of the shortest (in terms of total length) such paths. Similarly the search and counting versions ask for one such and the number of such shortest set of paths, respectively. We restrict attention to the shortest @math -DPP instances on undirected planar graphs where all sources and sinks lie on a single face or on a pair of faces. We provide efficient sequential and parallel algorithms for the search versions of the problem answering one of the main open questions raised by Colin de Verdiere and Schrijver for the general one-face problem. We do so by providing a randomised @math algorithm along with an @math time randomised sequential algorithm. We also obtain deterministic algorithms with similar resource bounds for the counting and search versions. In contrast, previously, only the sequential complexity of decision and search versions of the "well-ordered" case has been studied. For the one-face case, sequential versions of our routines have better running times for constantly many terminals. In addition, the earlier best known sequential algorithms (e.g. ) were randomised while ours are also deterministic. The algorithms are based on a bijection between a shortest @math -tuple of disjoint paths in the given graph and cycle covers in a related digraph. This allows us to non-trivially modify established techniques relating counting cycle covers to the determinant. We further need to do a controlled inclusion-exclusion to produce a polynomial sum of determinants such that all "bad" cycle covers cancel out in the sum allowing us to count "good" cycle covers. We study a generalization of covering problems called partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-partial set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-partial set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-partial vertex cover) in polynomial time. Without making any assumption about the number of sets an element is in, for instances where each set has cardinality at most three, we obtain an approximation of 4 3. We also present better-than-2-approximation algorithms for k-partial vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-partial vertex cover on planar graphs, and for covering k points in Rd by disks. Citation relationship between scientific publications has been successfully used for scholarly bibliometrics, information retrieval and data mining tasks, and citation-based recommendation algorithms are well documented. While previous studies investigated citation relations from various viewpoints, most of them share the same assumption that, if paper1 cites paper2 (or author1 cites author2), they are connected, regardless of citation importance, sentiment, reason, topic, or motivation. However, this assumption is oversimplified. In this study, we employ an innovative "context-rich heterogeneous network" approach, which paves a new way for citation recommendation task. In the network, we characterize 1) the importance of citation relationships between citing and cited papers, and 2) the topical citation motivation. Unlike earlier studies, the citation information, in this paper, is characterized by citation textual contexts extracted from the full-text citing paper. We also propose algorithm to cope with the situation when large portion of full-text missing information exists in the bibliographic repository. Evaluation results show that, context-rich heterogeneous network can significantly enhance the citation recommendation performance. We consider the classical problem of scheduling a set of independent jobs on a set of unrelated machines with costs. We are given a set of n monoprocessor jobs and m machines where each job is to be processed without preemptions. Executing job j on machine i requires time pij ≥ 0 and incurs cost cij . Our objective is to find a schedule obtaining a tradeoff between the makespan and the total cost. We focus on the case where the number of machines is a fixed constant, and we propose a simple FPTAS that computes for any Ɛ > 0 a schedule with makespan at most (1+Ɛ)T and cost at most Copt(T), in time O(n(n Ɛ)m), given that there exists a schedule of makespan T, where Copt(T) is the cost of the minimum cost schedule which achieves a makespan of T. We show that the optimal makespan-cost trade-off (Pareto) curve can be approximated by an efficient polynomial time algorithm within any desired accuracy. Our results can also be applied to the scheduling problem where the rejection of jobs is allowed. Each job has a penalty associated to it, and one is allowed to schedule any subset of jobs. In this case the goal is the minimization of the makespan of the scheduled jobs and the total penalty of the rejected jobs. Robust optimization has traditionally focused on uncertainty in data and costs in optimization problems to formulate models whose solutions will be optimal in the worst-case among the various uncertain scenarios in the model. While these approaches may be thought of defining data- or cost-robust problems, we formulate a new "demand-robust" model motivated by recent work on two-stage stochastic optimization problems. We propose this in the framework of general covering problems and prove a general structural lemma about special types of first-stage solutions for such problems: there exists a first-stage solution that is a minimal feasible solution for the union of the demands for some subset of the scenarios and its objective function value is no more than twice the optimal. We then provide approximation algorithms for a variety of standard discrete covering problems in this setting, including minimum cut, minimum multi-cut, shortest paths, Steiner trees, vertex cover and un-capacitated facility location. While many of our results draw from rounding approaches recently developed for stochastic programming problems, we also show new applications of old metric rounding techniques for cut problems in this demand-robust setting. In a STACS 2003 paper, Talwar analyzes the overpayment the VCG mechanism incurs for ensuring truthfulness in auctions. Among other results, he studies k-Set Cover (given a universe U and a collection of sets S 1 , S 2 , ? , S m , each having a cost c ( S i ) and at most k elements of U, find a minimum cost subcollection - a cover - whose union equals U) and shows that the payment of the VCG mechanism is at most k ? c ( OPT ' ) , where OPT ' is the best cover disjoint from the optimum cover OPT . The VCG mechanism requires finding an optimum cover. For k ? 3 , k-Set Cover is known to be NP-hard, and thus truthful mechanisms based on approximation algorithms are desirable. We show that the payment incurred by two mechanisms based on approximation algorithms (including the Greedy algorithm) is bounded by ( k - 1 ) c ( OPT ) + k ? c ( OPT ' ) . The same approximation algorithms have payment bounded by k ( c ( OPT ) + c ( OPT ' ) ) when applied to more general set systems, which include k-Polymatroid Cover, a problem related to Steiner Tree computations. If q is such that an element in a k-Set Cover instance appears in at most q sets, we show that the total payment based on our algorithms is bounded by q ? k 2 times the total payment of the VCG mechanism.