Search

We consider the single-machine time-dependent scheduling problem with linearly deteriorating jobs arriving over time. Each job i is associated with a release time r i and a processing time p i (s i) = α i + β i s i , where α i , β i > 0 are parameters and s i is the job's start time. In this setting, the approximability of both single-machine minimum makespan and total completion time problems remains open. We develop new bounds and approximation results for the special case of the problems with uniform deterioration, i.e. β i = β , for each i. The main contribution is a O (1 + 1 / β) -approximation algorithm for the makespan problem and a O (1 + 1 / β 2) approximation algorithm for the total completion time problem. Further, we propose greedy constant-factor approximation algorithms for instances with β = O (1 / n) and β = Ω (n) , where n is the number of jobs. Our analysis is based on an approach for comparing computed and optimal schedules via bounding pseudomatchings. [ABSTRACT FROM AUTHOR]

K-best enumeration , which asks to output k -best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, k -best enumeration tends to be intractable since, in many cases, finding one optimum solution is NP-hard. To overcome this difficulty, we combine k -best enumeration with a concept of enumeration algorithms called approximation enumeration algorithms. As a main result, we propose a 4-approximation algorithm for minimal connected edge dominating sets which outputs k minimal solutions with cardinality at most 4 ⋅ OPT ‾ , where OPT ‾ is the cardinality of a minimum solution which is not outputted by the algorithm. Our proposed algorithm runs in O (n m 2 Δ) delay, where n , m , Δ are the number of vertices, the number of edges, and the maximum degree of an input graph. [ABSTRACT FROM AUTHOR]

Damian and Pemmaraju (2002) [8] introduced leaf sector covers for circle graphs and presented an O (n 2) -time algorithm to find this data structure. They subsequently employed it as an algorithmic tool, leading to the development of an 8-approximation algorithm for the dominating set problem, a (2 + ε) -approximation scheme for the dominating set problem, and a (3 + ε) -approximation scheme for the total dominating set problem. In this paper, we have improved the time complexity from O (n 2) to O (n + m) for finding a leaf sector cover. Furthermore, we employed leaf sector covers as a powerful algorithmic tool to design a 10-approximation algorithm for the total dominating set problem and a 12-approximation algorithm for the paired-dominating set problem. Moreover, we also proposed a (2 + ε) -approximation scheme for the total dominating set problem and a (4 + ε) -approximation scheme for the paired-dominating set problem. The results presented above are currently the best algorithms for circle graphs. [ABSTRACT FROM AUTHOR]

Let T be a tessellation composed of equilateral triangular regions, where each region has an associated positive weight. We present two methods that discretize the space based on the placement of Steiner points in the cells of T. Using such a discretization, we can use Dijkstra's algorithm for computing the shortest path in the geometric graph obtained. This will lead us to two approximation algorithms for solving the Weighted Region Problem. For a given parameter ε ∈ (0 , 1 ] , the first discretization scheme provides an approximate path that is (1 + 0.428 ε) times better than the approximation given by Aleksandrov et al. (2005) [5]. The other discretization scheme uses at least ( ε + 2 ε + 4 ε + 4) log 2 ⁡ e fewer points per segment of the triangulation with the same approximation factor. [ABSTRACT FROM AUTHOR]

The fair k -center problem has been paid lots of attention recently. In the fair k -center problem, we are given a set X of points in a metric space and a parameter k ∈ Z + , where the points in X are divided into several groups, and each point is assigned a color to denote which group it is in. The goal is to partition X into k clusters such that the number of cluster centers with each color is equal to a given value, and the k -center problem objective is minimized. In this paper, we consider the fair k -center problem with outliers and capacity constraints, denoted as the fair k -center with outliers (F k CO) problem and the capacitated fair k -center (CF k C) problem, respectively. The outliers constraints allow up to z outliers to be discarded when computing the objective function, while the capacity constraints require that each cluster has size no more than L. In this paper, we design an Fixed-Parameter Tractability (FPT) approximation algorithm and a polynomial approximation algorithm for the above two problems. In particular, our algorithms give (1 + ϵ) -approximations with FPT time for the F k CO and CF k C problems in doubling metric space. Moreover, we also propose a 3-approximation algorithm in polynomial time for the F k CO problem with some reasonable assumptions. [ABSTRACT FROM AUTHOR]

We consider the product of determinantal point processes (DPPs), a point process whose probability mass is proportional to the product of principal minors of multiple matrices, as a natural, promising generalization of DPPs. We study the computational complexity of computing its normalizing constant , which is among the most essential probabilistic inference tasks. Our complexity-theoretic results (almost) rule out the existence of efficient algorithms for this task unless the input matrices are forced to have favorable structures. In particular, we prove the following: • Computing ∑ S det ⁡ (A S , S) p exactly for every (fixed) positive even integer p is UP -hard and Mod 3 P -hard, which gives a negative answer to an open question posed by Kulesza and Taskar [51]. • ∑ S det ⁡ (A S , S) det ⁡ (B S , S) det ⁡ (C S , S) is NP -hard to approximate within a factor of 2 O (| I | 1 − ε) or 2 O (n 1 / ε) for any ε > 0 , where | I | is the input size and n is the order of the input matrix. This result is stronger than the # P -hardness for the case of two matrices derived by Gillenwater [36]. • There exists a k O (k) n O (1) -time algorithm for computing ∑ S det ⁡ (A S , S) det ⁡ (B S , S) , where k is the maximum rank of A and B or the treewidth of the graph formed by nonzero entries of A and B. Such parameterized algorithms are said to be fixed-parameter tractable. These results can be extended to the fixed-size case. Further, we present two applications of fixed-parameter tractable algorithms given a matrix A of treewidth w : • We can compute a 2 n 2 p − 1 -approximation to ∑ S det ⁡ (A S , S) p for any fractional number p > 1 in w O (w p) n O (1) time. • We can find a 2 n -approximation to unconstrained maximum a posteriori inference in w O (w n) n O (1) time. [ABSTRACT FROM AUTHOR]

The coordination among drones and ground vehicles for last-mile delivery has gained significant interest in recent years. In this paper, we study multiple drone delivery scheduling problem (MDSP) [1] for last-mile delivery, where we have a set of drones with an identical battery budget and a set of delivery locations; along with profit for delivery, cost, and delivery time intervals. The objective of the MDSP is to find conflict-free schedules for each drone such that the total profit gained is maximum subject to the battery constraint of the drones. This paper proposes an optimal pseudo-polynomial algorithm and a fully polynomial time approximation scheme (FPTAS) for the single drone delivery scheduling problem (SDSP). Also, we propose two approximation algorithms of factor 1 3 for the MDSP with some constraints on the number of drones. We formulate the problem for the heterogeneous case, where the drones have non-identical battery capacities, and propose a 1 6 ρ -approximation algorithm, where ρ is the ratio between the minimum and maximum battery capacity of the drones. • An optimal pseudo-polynomial algorithm and FPTAS for the single drone delivery scheduling problem is proposed. • Two approximation algorithms for the multiple drone delivery scheduling problem are proposed. • An approximation algorithm for the multiple heterogeneous drone delivery scheduling problem is proposed. • We analyzed the approximation factors of all the aforementioned proposed algorithms and time complexities. [ABSTRACT FROM AUTHOR]

The maximization of non-negative monotone submodular functions under a certain constraint is intensively studied. However, there are few works considering the maximization of non-monotone non-submodular functions, which even might be negative. These functions also have many applications, such as optimal marketing for revenue maximization over social networks, budget allocation problems, and Epidemic transmission, etc. In our paper, we discuss the maximization of the non-monotone non-submodular functions under a knapsack constraint, which even might be negative, and explore the performance under the greedy algorithm. We obtain some improved approximate ratios, for the functions with different properties, such as the non-negative weak-monotone weak-submodular functions, and the weak-submodular weak-supermodular functions that might be negative. Moreover, we generalize the results to the functions with weak subadditivity and curvature. [ABSTRACT FROM AUTHOR]

We study a constrained version of the Geometric Hitting Set problem where we are given a set of points, partitioned into pairwise disjoint subsets, and a set of intervals. The objective is to hit all the intervals with a minimum number of points such that if we select a point from a subset, we must select all the points from that subset. We consider two special cases of the problem where each subset can have at most 2 and 3 points. If each subset contains at most 2 points and the intervals are disjoint, we show that the problem admits a polynomial-time algorithm. On the contrary, if each subset contains at most t points, where t ≥ 2 , and the intervals are overlapping, we show that the problem becomes NP - Hard. Further, when each subset contains at most t points where t ≥ 3 , and the intervals are disjoint, we prove that the problem is NP - Hard , and we provide two constant factor approximation algorithms for this problem. We also study the problem from the parameterized complexity perspective. If the intervals are disjoint, then we prove that the problem is in FPT when parameterized by the size of the solution. We also complement this result by giving a lower bound in the size of the kernel for disjoint intervals, and we also provide a polynomial kernel when the size of all subsets is bounded by a constant. [ABSTRACT FROM AUTHOR]

We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u , v) is determined by how many nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u , v) and a packet of weight x going from u to v , node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u , v) decreases by x. Correspondingly, v 's capacity on (u , v) increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is "rechargeable" in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1 + ε) ⋅ (1 + 3) for some arbitrary ε > 0. [ABSTRACT FROM AUTHOR]

We consider 2-connectivity network design problems in which we are given a graph and seek a min-size 2-connected subgraph that satisfies a prescribed property. • In the 1 -Connectivity Augmentation problem the goal is to augment a connected graph by a minimum size edge subset of a specified edge set such that the augmented graph is 2-connected. We breach the natural approximation ratio 2 for this problem, and also for the more general Crossing Family Cover problem. • In the 2 -Connected Dominating Set problem, we seek a minimum size 2-connected subgraph that dominates all nodes. We give the first non-trivial approximation algorithm with expected approximation ratio O (σ (n) ⋅ log 3 ⁡ n) , where σ (n) = O (log ⁡ n ⋅ log ⁡ log ⁡ n ⋅ (log ⁡ log ⁡ log ⁡ n) 3). The unifying technique of both results is a reduction to the Subset Steiner Connected Dominating Set problem. Such a reduction was known for edge-connectivity, and we extend it to 2-node connectivity problems. We show that the same method can be used to obtain easily polylogarithmic approximation ratios that are not too far from the best known ones for several other problems. [ABSTRACT FROM AUTHOR]

This paper investigates two flow shop scheduling problems with two machines A and B , and a single transporter V. In the first problem, the transporter V is located at machine A initially, each job has to be processed first on A , then transported to B for further processing. While in the second problem, the transporter V is located at machine B initially, each job needs to be processed first on A , then on B , finally transported to the destination. In both problems, the transporter V can carry up to c (where c is a constant and c ≥ 1) jobs at a time and the objective is to minimize the makespan. For the former problem, the best approximation algorithm guarantees a worst-case ratio bound of (5 3 + ε) , while for the latter one, the best approximation algorithm provides a worst-case ratio bound of 2. For each problem, we design a polynomial-time approximation scheme (PTAS). [ABSTRACT FROM AUTHOR]

The fair k -median problem is one of the important clustering problems. The current best approximation ratio is 4.675 for this problem with 1-fairness violation, which was proposed by Bercea et al. [APPROX-RANDOM'2019]. To our best knowledge, there is no available approximation algorithm for this problem without any fairness violation in doubling metrics. In this paper, we consider the fair k -median problem in doubling metrics and general metrics. We provide the first QPTAS for the fair k -median problem based on the hierarchical decomposition and dynamic programming process in doubling metrics. For applying a dynamic programming process to solve this problem, the distances from portals to facilities cannot be directly enumerated since each client may not be assigned to its closest open facility. To overcome the difficulties caused by the fairness constraints, we construct an auxiliary graph and use minimum weighted perfect matching to get the cost between the portals of each block and the ones in its children. In order to satisfy the fairness constraints, we bound the fairness constraints of each open facility in the leaves of the split-tree based on the relation between the subproblem and the subproblems of its children. To obtain the assignment of the given instance and remove the fairness violation, we construct a new b -value min-cost max-flow model based on the set of open facilities. For the fair k -median problem in general metrics, we present a polynomial-time approximation algorithm with ratio O (log ⁡ k). Our approximation algorithm for the fair k -median problem in doubling metrics is the first result for the corresponding problem without any fairness violation in doubling metrics. [ABSTRACT FROM AUTHOR]

A k -submodular function takes k distinct, non-overlapping subsets of a ground set as input and outputs a value. It is a generalization of the well-known submodular function, which is the case when k = 1 and takes a single subset as input. We study the problem of maximizing a non-negative k -submodular function under a knapsack constraint. Greedy+Singleton is an algorithm that chooses the better solution between the fully greedy solution and the best single-element solution, with query complexity and running time of O (n 2 k). We show that Greedy+Singleton has an approximation ratio of 0.273 for monotone functions, which improves the previous analysis of 0.158 in the literature. Moreover, we give the first analysis of Greedy+Singleton for non-monotone k -submodular functions, and prove an approximation ratio of 0.219. [ABSTRACT FROM AUTHOR]

The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. As evidence that adding advice to adaptive priority algorithms extends both adaptive priority algorithms and online algorithms with advice, we present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7 n / 22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7 n / 22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way. [ABSTRACT FROM AUTHOR]

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 − o (1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1 / 6 − ϵ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the diversity-aware fair k -supplier problem, which involves selecting k facilities from a set F that consists of m disjoint groups, subject to a constraint on the maximum number of facilities selected from each group. The goal is to ensure fairness in the selection process and avoids any demographic group from over-representation. While the classical k -supplier problem is known to be NP-hard to solve and is even NP-hard to approximate within a factor of less than 3, we present an efficient 5-approximation algorithm for the diversity-aware k -supplier problem based on maximum matching. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) without an isolated edge, a set D ⊆ E is an edge total dominating set of G if every edge e ∈ E is adjacent to at least one edge of D. The Minimum Edge Total Dominating Set problem is to compute a minimum cardinality edge total dominating set of G. It is known that the decision version of the problem is NP-complete for bipartite graphs, chordal graphs, and planar graphs. On the positive side, the problem is efficiently solvable for trees. In this paper, we further study the complexity of this problem in other graph classes. We design a linear-time algorithm to compute a minimum cardinality edge total dominating set in chain graphs, a subclass of bipartite graphs. We also propose linear-time algorithms for two subclasses of chordal graphs, namely, split graphs and proper interval graphs with no cut vertices. In addition, we show that the problem is APX-complete for graphs with maximum degree 3 and propose an approximation algorithm for the problem in k -regular graphs, where k ≥ 4. We discuss the complexity difference between the Minimum Edge Dominating Set problem and Minimum Edge Total Dominating Set problem which seem to be closely related. [ABSTRACT FROM AUTHOR]

In this work, we investigate the problem of maximizing nonmonotone DR-submodular function (possibly negative) subject to cardinality constraints on an integer lattice space. We propose a M -Threshold Decrease Algorithm that uses a compensation constant M from a special decomposition h (x) = f (x) − g (x) , which achieves a 1 − e − δ − ϵ approximation guarantee. To ensure that the algorithm ends in finite time, the supremum of δ is δ (ϵ) = ϵ max s ∈ Ω ⁡ h (χ s | 0) 2 k max s ∈ Ω ⁡ g (χ s | 0) + ϵ max s ∈ Ω ⁡ h (χ s | 0). If max s ∈ Ω ⁡ h (χ s | 0) > 2 k max s ∈ Ω ⁡ g (χ s | 0) , there exists ϵ ⁎ = arg ⁡ max ϵ ∈ (0 , 1) ⁡ 1 − e − δ (ϵ) − ϵ such that 1 − e − δ (ϵ ⁎) − ϵ ⁎ > 0. This implies that there is a valid δ such that 1 − e − δ − ϵ > 0. To accelerate the algorithm, we employ a random subset to replace the ground set and propose a Random M -Threshold Decrease Algorithm, where δ (ϵ) = ϵ r max s ∈ Ω ⁡ h (χ s | 0) 2 n k max s ∈ Ω ⁡ g (χ s | 0) + [ k (n − r) + ϵ r ] max s ∈ Ω ⁡ h (χ s | 0) with r being the size of the random subset and n being the size of the ground set. Furthermore, we demonstrate that, based on the DR-ratio γ d and the DS decomposition, the M -Threshold Decrease Algorithm is also suitable for solving the monotone non-DR-submodular maximization problem, achieving a 1 − e − γ d δ − O (ϵ) approximation guarantee. Because γ d is a challenging metric to calculate, we refine the M -Threshold Decrease Algorithm, which can return an estimate of γ d. To the best of our knowledge, this is the first time that a single factor approximation ratio has been proposed for the nonmonotone DR-submodular maximization problem (possibly negative) subject to cardinality constraints. • This paper adopts the decomposition structure to compensate the non-monotonicity and non-negativity for DR-submodular maximization. • Using a compensation constant M , we design a 1 − e − δ − ϵ approximation algorithm, namely M -Threshold Decrease Algorithm. • Based on the DR-ratio γ d , our algorithm is a 1 − e − δ γ d − O (ϵ) approximation algorithm for monotone non-DR-submodular maximization. [ABSTRACT FROM AUTHOR]