We study Round-UFP and Round-SAP, two generalizations of the classical Bin Packing problem that correspond to the unsplittable flow problem on a path (UFP) and the storage allocation problem (SAP), respectively. We ar...
详细信息
Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least k vertices is considered long....
详细信息
Clustering is one of the most fundamental tools in artificial intelligence, machine learning, and data mining. In this paper, we follow one of the recent mainstream topics of clustering, Sum of Radii (SoR), which natu...
详细信息
ISBN:
(纸本)1577358872
Clustering is one of the most fundamental tools in artificial intelligence, machine learning, and data mining. In this paper, we follow one of the recent mainstream topics of clustering, Sum of Radii (SoR), which naturally arises as a balance between the folklore k-center and k-median. SoR aims to determine a set of k balls, each centered at a point in a given dataset, such that their union covers the entire dataset while minimizing the sum of radii of the k balls. We propose a general technical framework to overcome the challenge posed by varying radii in SoR, which yields fixed-parameter tractable (fpt) algorithms with respect to k (i.e., whose running time is f(k)ploy(n) for some f). Our framework is versatile and obtains fpt approximation algorithms with constant approximation ratios for SoR as well as its variants in general metrics, such as Fair SoR and Matroid SoR, which significantly improve the previous results.
Given an edge-weighted (metric/general) complete graph with n vertices, the maximum weight (metric/general) k-cycle/path packing problem is to find a set of n/k vertex-disjoint k-cycles/paths such that the total weigh...
详细信息
ISBN:
(数字)9789819705665
ISBN:
(纸本)9789819705658;9789819705665
Given an edge-weighted (metric/general) complete graph with n vertices, the maximum weight (metric/general) k-cycle/path packing problem is to find a set of n/k vertex-disjoint k-cycles/paths such that the total weight is maximized. In this paper, we consider approximation algorithms. For metric k-cycle packing, we improve the previous approximation ratio from 3/5 to 7/10 for k = 5, and from 7/8 center dot (1- 1/k)(2) for k > 5 to (7/8 - 0.125/k)(1 - 1/k) for constant odd k > 5 and to 7/8 center dot (1 - 1/k + 1 k(k-1)) for even k > 5. For metric k-path packing, we improve the approximation ratio from 7/8 center dot (1 - 1/k) to 27k(2)- 48k+16/32k(2)-36k-24 for even 10 >= k >= 6. For the case of k = 4, we improve the approximation ratio from 3/4 to 5/6 for metric 4-cycle packing, from 2/3 to 3/4 for general 4-cycle packing, and from 3/4 to 14/17 for metric 4-path packing.
This paper delves into the interpretability of Graph Neural Networks in the context of Boolean Satisfiability. The goal is to demystify the internal workings of these models and provide insightful perspectives into th...
详细信息
ISBN:
(纸本)9798400704369
This paper delves into the interpretability of Graph Neural Networks in the context of Boolean Satisfiability. The goal is to demystify the internal workings of these models and provide insightful perspectives into their decision-making processes. This is done by uncovering connections to two approximation algorithms studied in the domain of Boolean Satisfiability: Belief Propagation and Semi-definite Programming Relaxations. Revealing these connections has empowered us to introduce a suite of impactful enhancements. The first significant enhancement is a curriculum training procedure, which incrementally increases the problem complexity in the training set, together with increasing the number of message passing iterations of the Graph Neural Network. We show that the curriculum, together with several other optimizations, reduces the training time by more than an order of magnitude compared to the baseline without the curriculum. Furthermore, we apply decimation and sampling of initial embeddings, which significantly increase the percentage of solved problems.
A feedback vertex set (FVS) in a digraph is a subset of vertices whose removal makes the digraph acyclic. In other words, it hits all cycles in the digraph. Lokshtanov et al. [TALG '21] gave a factor 2 randomized ...
详细信息
ISBN:
(纸本)9783031555978;9783031555985
A feedback vertex set (FVS) in a digraph is a subset of vertices whose removal makes the digraph acyclic. In other words, it hits all cycles in the digraph. Lokshtanov et al. [TALG '21] gave a factor 2 randomized approximation algorithm for finding a minimum weight FVS in tournaments. We generalize the result by presenting a factor 2a randomized approximation algorithm for finding a minimum weight FVS in digraphs of independence number a;a generalization of tournaments which are digraphs with independence number 1. Using the same framework, we present a factor 2 randomized approximation algorithm for finding a minimum weight Subset FVS in tournaments: given a vertex subset S in addition to the graph, find a subset of vertices that hits all cycles containing at least one vertex in S. Note that FVS in tournaments is a special case of Subset FVS in tournaments in which S = V (T).
We study the load-balanced capacitated vehicle routing problem (LBCVRP): the problem is to design a collection of tours for a fixed fleet of vehicles with capacityQto distribute a supply from a single depot between a ...
详细信息
We study the load-balanced capacitated vehicle routing problem (LBCVRP): the problem is to design a collection of tours for a fixed fleet of vehicles with capacityQto distribute a supply from a single depot between a number of predefined clients, in a way that the total traveling cost is a minimum, and the vehicle loads are balanced. The unbalanced loads cause the decrease of distribution quality especially in business environments and flexibility in the logistics activities. The problem being NP-hard, we propose two approximation algorithms. When the demands are equal, we present a((1-1Q)rho+3/2)-approximation algorithm that finds balanced loads. Here, rho is the approximation ratio for the known metric traveling salesman problem (TSP). This result leads to a 2.5-1/Q approximation ratio for the tree metrics since an optimal solution can be found for the TSP on a tree. We present an improved2- approximation algorithm. When the demands are unequal, we focus on obtaining approximate solutions since finding balanced loads is NP-complete. We propose an algorithm that provides a4-approximation for the balance of the loads. We assume a second approach to get around the difficulties of the feasibility. In this approach, we redefine and convert the problem into a multi-objective problem. The algorithm we propose has a 4 factor of approximation.
A prominent problem in scheduling theory is the weighted flow time problem on one machine. We are given a machine and a set of jobs, each of them characterized by a processing time, a release time, and a weight. The g...
详细信息
ISBN:
(纸本)9781611977936
A prominent problem in scheduling theory is the weighted flow time problem on one machine. We are given a machine and a set of jobs, each of them characterized by a processing time, a release time, and a weight. The goal is to find a (possibly preemptive) schedule for the jobs in order to minimize the sum of the weighted flow times, where the flow time of a job is the time between its release time and its completion time. It had been a longstanding important open question to find a polynomial time O(1)-approximation algorithm for the problem. In a break-through result, Batra, Garg, and Kumar (FOCS 2018) presented such an algorithm with pseudopolynomial running time. Its running time was improved to polynomial time by Feige, Kulkarni, and Li (SODA 2019). The approximation ratios of these algorithms are relatively large, but they were improved to 2 + epsilon by Rohwedder and Wiese (STOC 2022) and subsequently to 1 + epsilon by Armbruster, Rohwedder, and Wiese (STOC 2023). All these algorithms are quite complicated and involve for example a reduction to (geometric) covering problems, dynamic programs to solve those, and LP-rounding methods to reduce the running time to a polynomial in the input size. In this paper, we present a much simpler (6 + epsilon)-approximation algorithm for the problem that does not use any of these reductions, but which works on the input jobs directly. It even generalizes directly to an O(1)-approximation algorithm for minimizing the p-norm of the jobs' flow times, for any 0 < p < infinity (the original problem setting corresponds to p = 1). Prior to our work, for p > 1 only a pseudopolynomial time O(1)-approximation algorithm was known for this variant, and no algorithm for p < 1. For the same objective function, we present a very simple QPTAS for the setting of constantly many unrelated machines for 0 < p < infinity (and assuming quasi-polynomially bounded input data). It works in the cases with and without the possibility to migrate a job
Data collection from the sensors in time is an integral part of many applications of wireless sensor networks (WSNs). Vehicles, referred to as Mobile Sinks (SNKs), may be used to collect data from the sensors by visit...
详细信息
Data collection from the sensors in time is an integral part of many applications of wireless sensor networks (WSNs). Vehicles, referred to as Mobile Sinks (SNKs), may be used to collect data from the sensors by visiting them. Since the sensors have limited memory, the sensed data needs to be collected by the SNKs within a predefined time interval to avoid memory overflow. Periodic data collection by SNKs becomes even more challenging when the sensors are mobile. Moreover, the presence of obstacles in the area makes the path planning for SNKs even more complicated. In this paper, an optimization problem, referred to as Minimum Mobile Sink Aided Periodic Data Collection (MinSnkDC) problem, is formulated, where the objective is to determine the minimum number of SNKs that collect data for every time period from the mobile sensors in the WSN, while avoiding collision with the obstacles in the area. The problem is proved to be NP-complete. Two constant factor approximation algorithms, namely MinSnkDC and Modified MinSnkDC (M-MinSnkDC), are proposed to solve the problem. From the simulation results, it is evident that M-MinSnkDC can produce a better solution compared to the existing obstacle-aware SNK-based data collection algorithms, while using a small number of SNKs.
A vertex cover of a graph is a set of vertices of the graph such that every edge has at least one endpoint in it. In this work, we study WEIGHTED VERTEX COVER with solution size as a parameter. Formally, in the (k, W)...
详细信息
ISBN:
(纸本)9783031556005;9783031556012
A vertex cover of a graph is a set of vertices of the graph such that every edge has at least one endpoint in it. In this work, we study WEIGHTED VERTEX COVER with solution size as a parameter. Formally, in the (k, W)-VERTEX COVER problem, given a graph G, an integer k, a positive rational W, and a weight function w : V (G) -> Q(+), the question is whether G has a VERTEX COVER of size at most k of weight at most W, with k being the parameter. An (a, b)-bi-criteria approximation algorithm for (k, W)-VERTEX COVER either produces a vertex cover S such that |S| <= ak and w(S) <= bW, or decides that there is no vertex cover of size at most k of weight at most W. We obtain the following results. - A simple (2, 2)-bi-criteria approximation algorithm for (k, W)-VERTEX COVER in polynomial time by modifying the standard LP-rounding algorithm. - A simple exact parameterized algorithm for (k, W)-VERTEX COVER running in O* (1.4656(k)) time (Here, the O* notation hides factors polynomial in n.). - A(1+epsilon, 2)-approximation algorithm for (k, W)-VERTEX COVER running in O* (1.4656((1- epsilon)k)) time. - A (1.5, 1.5)-approximation algorithm for (k, W)-VERTEX COVER running in O* (1.414(k)) time. - A (2 - delta, 2 - delta)-approximation algorithm for (k, W)-VERTEX COVER running in O* (Sigma(i= delta k(1-2 delta)/1+2 delta) (delta k(1-2 delta)/2 delta) ((delta k+i)(delta k-2i delta/1-2 delta))) time for any delta < 0.5. For example, for (1.75, 1.75) and (1.9, 1.9)-approximation algorithms, we get running times of O* (1.272k) and O* (1.151k) respectively. Our algorithms (expectedly) do not improve upon the running times of the existing algorithms for the unweighted version of Vertex Cover. When compared to algorithms for the weighted version, our algorithms are the first ones to the best of our knowledge which work with arbitrary weights, and they perform well when the solution size is much smaller than the total weight of the desired solution.
暂无评论