Given an undirected graph G=(V,E) with weighted vertices and edges, a set J of n=|V| independent jobs and m unrelated machines, each vertex v∈V corresponds to a job Jj∈J. The combination of prize-collecting vertex c...
详细信息
In this paper we obtain improved approximation algorithms for the Capacitated Min-Max Graph Cover Problems and the first constant-factor approximation algorithms for the Capacitated Minimum Graph Cover Problems. These...
详细信息
This article addresses the scheduling problem of coflows in identical parallel networks, a well-known NPNP-hard problem. We consider both flow-level scheduling and coflow-level scheduling problems. In the flow-level s...
详细信息
In recent years, k-submodular functions have garnered significant attention due to their natural extension of submodular functions and their practical applications, such as influence maximization and sensor placement....
详细信息
In recent years, k-submodular functions have garnered significant attention due to their natural extension of submodular functions and their practical applications, such as influence maximization and sensor placement. Influence maximization involves selecting a set of nodes in a network to maximize the spread of information, while sensor placement focuses on optimizing the locations of sensors to maximize coverage or detection efficiency. This paper first proposes two randomized algorithms aimed at improving the approximation ratio for maximizing monotone k-submodular functions under matroid constraints and individual size constraints. Under the matroid constraints, we design a randomized algorithm with an approximation ratio of nk2nk-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{nk}{2nk-1}$$\end{document} and a complexity of O(rn(RO+kEO))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(rn(\text {RO}+k\text {EO}))$$\end{document}, where n represents the total number of elements in the ground set, k represents the number of disjoint sets in a k-submodular function, r denotes the size of the largest independent set, RO\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {RO}$$\end{document} indicates the time required for the matroid's independence oracle, and EO\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usep
Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under variou...
详细信息
Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement-odd, even, or unconstrained-of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse T-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. We also consider the parity-constrained k-center problem, the bottleneck optimization variant of parity-constrained facility location. We present the first constant-factor approximation algorithm also for this problem.
In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min{O(log n), f\} approximation factor. (Throughout, n, m, f, and C are parameters denoting ...
详细信息
In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min{O(log n), f\} approximation factor. (Throughout, n, m, f, and C are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when f = \Omega (log n), this was achieved by a deterministic O(log n)-approximation algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537550]. In this paper we consider the low-frequency range, when f = O(log n), and obtain deterministic algorithms with a (1 + \epsilon )f-approximation ratio and the following guarantees on the update time. (1) O ((f /\epsilon ) \cdot log(Cn)) amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was O(f2) of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206--218]. In contrast, the only result with O(f)-approximation was that of Abboud et al. [Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114--125], who designed a randomized (1 + \epsilon )f-approximation algorithm with O((f2/\epsilon ) \cdot log n) amortized update time. (2) O \bigl(f2/\epsilon3 + (f/\epsilon2) \cdot log C\bigr) amortized update time: This result improves the above update time bound for most values off in the low-frequency range, i.e., f = o(log n). It is also the first result that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically maintaining a (2 + \epsilon )-approximate minimum vertex cover in O(1/\epsilon2) amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872--1885] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). (3) O((f/\epsilon3) \cdot log2(Cn)) worst-ca
We introduce and study two natural generalizations of the Connected Vertex Cover (VC) problem: the p-Edge-Connected and p-Vertex-Connected VC problem (where p >= 2 is a fixed integer). We obtain an 2O(pk)nO(1)-time...
详细信息
We introduce and study two natural generalizations of the Connected Vertex Cover (VC) problem: the p-Edge-Connected and p-Vertex-Connected VC problem (where p >= 2 is a fixed integer). We obtain an 2O(pk)nO(1)-time algorithm for p-Edge-Connected VC and an 2O(k2)nO(1)-time algorithm for p-Vertex-Connected VC. Thus, like Connected VC, both constrained VC problems are FPT. Furthermore, like Connected VC, neither problem admits a polynomial kernel unless NP subset of coNP/poly, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. Finally, we describe a 2(p + 1)-approximation algorithm for the p-Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning p- vertex/edge-connected subgraphs of a p-vertex/edge-connected graph by Nishizeki and Poljak (1994) [30] and Nagamochi and Ibaraki (1992) [27].(c) 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).
Target-based computer-assisted orchestration can be thought of as the process of searching for combina-tions of orchestral sounds in a database of sound samples to match a given sound (called target ) while respecting...
详细信息
Target-based computer-assisted orchestration can be thought of as the process of searching for combina-tions of orchestral sounds in a database of sound samples to match a given sound (called target ) while respecting specific symbolic constraints (such as the musical instruments that we can use). It is modeled as a combinatorial optimization problem, where the feasible solutions are subsets of orchestral sounds, and the function to minimize measures a distance between the chosen subset of orchestral sounds and the target. In this article, we focus on this optimization problem and analyse it through the lens of com-putational complexity and approximation algorithms. We first study the so-called static case where there is no temporality in the target sound (we want to reproduce a 'single' constant sound). We show that the problem is already NP-hard, but is solvable by a pseudo-polynomial-time algorithm. We also provide an approximation algorithm with additive error. We then consider the more general case with tempo-rality, when the target sound can be seen as a sequence of sounds over a time horizon. We show how the previous results in the static case generalize in this temporal case. We conclude our study with some experiments on real target sounds.(c) 2022 Elsevier B.V. All rights reserved.
Moldable tasks allow schedulers to determine the number of processors assigned to each task, thus enabling efficient use of large-scale parallel processing systems. We consider the problem of scheduling independent mo...
详细信息
Moldable tasks allow schedulers to determine the number of processors assigned to each task, thus enabling efficient use of large-scale parallel processing systems. We consider the problem of scheduling independent moldable tasks on processors and propose a new perspective of the existing speedup models: as the number pof processors assigned to a task increases, the speedup is linear if pis small and becomes sublinear after pexceeds a threshold. Based on this, we propose an efficient approximation algorithm to minimize the makespan. As a by-product, we also propose an approximation algorithm to maximize the sum of values of tasks completed by a deadline;this scheduling objective is considered for moldable tasks for the first time while similar works have been done for other types of parallel tasks. (C) 2023 Elsevier B.V. All rights reserved.
In Two-dimensional Bin Packing (2BP), we are given n rectangles as input and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. 2BP admits no AP...
详细信息
In Two-dimensional Bin Packing (2BP), we are given n rectangles as input and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. 2BP admits no APTAS and the current best approximation ratio is 1.406 by Bansal and Khan (ACM-SIAM symposium on discrete algorithms (SODA), pp 13-25, 2014. https://***/ 10.1137/1.9781611973402.2). A well-studied variant of 2BP is Guillotine Two-dimensional Bin Packing (G2BP), where rectangles must be packed in such a way that every rectangle in the packing can be obtained by applying a sequence of end-to-end axis-parallel cuts, also called guillotine cuts. Bansal et al. (Symposium on foundations of computer science (FOCS). IEEE, pp 657-666, 2005. https://***/ 10.1109/SFCS.2005.10) gave an APTAS for G2BP. Let lambda be the smallest constant such that for every set I of items, the number of bins in the optimal solution to G2BP for I is upper bounded by lambda opt(I) + c, where opt( I) is the number of bins in the optimal solution to 2BP for I and c is a constant. It is known that 4/3 <= lambda <= 1.692. Bansal and Khan (2014) conjectured that lambda = 4/3. The conjecture, if true, will imply a (4/3 + epsilon)-approximation algorithm for 2BP. Given a small constant delta > 0, a rectangle is called large if both its height and width are at least d, else it is called skewed. We make progress towards the conjecture by showing that lambda = 4/3 when all input rectangles are skewed. We also give an APTAS for 2BP for skewed items, though general 2BP does not admit an APTAS.
暂无评论