| 书目名称 | Combinatorial Optimization and Applications | | 副标题 | 16th International C | | 编辑 | Weili Wu,Jianxiong Guo | | 视频video | http://file.papertrans.cn/230/229971/229971.mp4 | | 丛书名称 | Lecture Notes in Computer Science | | 图书封面 |  | | 描述 | The two-volume set LNCS 14461 and LNCS 14462 constitutes the refereed proceedings of the 17th International Conference on Combinatorial Optimization and Applications, COCOA 2023, held in Hawaii, HI, USA, during December 15–17, 2023. .The 73 full papers included in the proceedings were carefully reviewed and selected from 117 submissions. They were organized in topical sections as follows: .Part I: Optimization in graphs; scheduling; set-related optimization; applied optimization and algorithm; Graph planer and others;.Part II: Modeling and algorithms; complexity and approximation; combinatorics and computing; optimization and algorithms; extreme graph and others; machine learning, blockchain and others.. | | 出版日期 | Conference proceedings 2024 | | 关键词 | approximation algorithms; approximation theory; big data; communication systems; computational game theo | | 版次 | 1 | | doi | https://doi.org/10.1007/978-3-031-49611-0 | | isbn_softcover | 978-3-031-49610-3 | | isbn_ebook | 978-3-031-49611-0Series ISSN 0302-9743 Series E-ISSN 1611-3349 | | issn_series | 0302-9743 | | copyright | The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerl |
| 1 |
Front Matter |
|
|
Abstract
|
| 2 |
|
|
|
Abstract
|
| 3 |
An Efficient Local Search Algorithm for Correlation Clustering on Large Graphs |
Nathan Cordner,George Kollios |
|
Abstract
Correlation clustering (CC) is a widely-used clustering paradigm, with many applications to problems such as classification, database deduplication, and community detection. CC instances represent objects as graph nodes, and clustering is performed based on relationships between objects (positive or negative edges between pairs of nodes). The CC objective is to obtain a graph clustering that minimizes the number of incorrectly assigned edges (negative edges within clusters, and positive edges between clusters)..For large CC instances, lightweight algorithms like the Pivot method have been preferred due to their scalability. Because these algorithms do not have state-of-the-art approximation guarantees, LocalSearch (LS) methods have often then been applied to refine their clustering results. Unfortunately, LS does not enjoy the same ability to scale since it is inherently sequential and has the potential to converge slowly..We propose a lightweight, parallelizable LS method called InnerLocalSearch (ILS) to use in conjunction with the Pivot algorithm. We show that ILS still provides a significant improvement to clustering quality while dramatically reducing the additional running tim
|
| 4 |
Algorithms on a Path Covering Problem with Applications in Transportation |
Ruxandra Marinescu-Ghemeci,Alexandru Popa,Tiberiu Sîrbu |
|
Abstract
Given a road network, a source, a destination and . platoon paths, our aim is to reach the destination in a maximum given time using the benefits of traveling along platoons. We consider two objective functions (maximize the total time spent as a member of a platoon or minimize the time traveled without platoons) and for each such objective function, we have two scenarios: in the first one we are given the moments when platoons start to travel, while in second version we can decide these moments. We show several NP-hardness results as well as a dynamic-programming polynomial time algorithm (for the scenario in which the starting times are given). Then we describe an approximation algorithm with a factor 1/. that has running time exponential in ./., with ..
|
| 5 |
Faster Algorithms for Evacuation Problems in Networks with a Single Sink of Small Degree and Bounded |
Yuya Higashikawa,Naoki Katoh,Junichi Teruyama,Yuki Tokuni |
|
Abstract
In this paper, we propose new algorithms for . defined on .. A dynamic flow network is a directed graph in which . nodes are given supplies (i.e., the number of evacuees) and a single . node is given a demand (i.e., the maximum number of acceptable evacuees). The evacuation problem seeks a dynamic flow that sends all supplies from sources to the sink such that its demand is satisfied in the minimum feasible time horizon. For this problem, the current best algorithms are developed by Schlöter (2018) and Kamiyama (2019), which run in strongly polynomial time but with high-order polynomial time complexity because they use submodular function minimization as a subroutine. In this paper, we propose new algorithms that do not explicitly execute submodular function minimization, and we prove that they are faster than the current best algorithms when an input network is restricted such that the sink has a small in-degree and every edge has the same capacity.
|
| 6 |
An ,-Competitive Posted-Price Algorithm for Online Matching on the Line |
Stephen Arndt,Josh Ascher,Kirk Pruhs |
|
Abstract
Motivated by demand-responsive parking pricing systems, we consider posted-price algorithms for the online metric matching problem. We give an .-competitive posted-price randomized algorithm in the case that the metric space is a line. In particular, in this setting we show how to implement the ubiquitous guess-and-double technique using prices.
|
| 7 |
Online Dominating Set and Coloring |
Minati De,Sambhav Khurana,Satyam Singh |
|
Abstract
In this paper, we present online deterministic algorithms for minimum coloring, minimum dominating set and its variants in the context of geometric intersection graphs. We consider a graph parameter: the independent kissing number ., which is a number equal to ‘the size of the largest induced star in the graph .’. For a graph with an independent kissing number at most ., we obtain an algorithm having an optimal competitive ratio of ., for the minimum dominating set and the minimum independent dominating set problems; however, for the minimum connected dominating set problem, we obtain a competitive ratio of at most .. In addition, we prove that for the minimum connected dominating set problem, any deterministic online algorithm has a competitive ratio of at least . for the geometric intersection graph of translates of a convex object in .. Next, for the minimum coloring problem, we present an algorithm having a competitive ratio of . for geometric intersection graphs of bounded scaled .-fat objects in . having a width in between [1, .], where . is the independent kissing number of the geometric intersection graph of bounded scaled .-fat objects having a width in between [1, 2]. Fin
|
| 8 |
Near-Bipartiteness, Connected Near-Bipartiteness, Independent Feedback Vertex Set and Acyclic Vertex |
Maria Luíza L. da Cruz,Raquel S. F. Bravo,Rodolfo A. Oliveira,Uéverton S. Souza |
|
Abstract
In the . problem, we are given a simple graph . and asked whether .(.) can be partitioned into two sets . and . such that . is a stable set and . induces a forest. Alternatively, . can be seen as the problem of determining whether . admits an independent feedback vertex set . or an acyclic vertex cover .. Since such a problem is .-complete even for graphs with diameter three, we first study the property of being near-bipartite on graphs having a dominating edge, a natural subclass of diameter-three graphs. Concerning graphs having a dominating edge, we present a polynomial-time algorithm for . and prove that ., the variant where the forest must be connected, is .-complete. In addition, we show that ., the problem of finding a near-bipartition (.) minimizing ., and ., the problem of finding a near-bipartition (.) minimizing ., are both .-hard when restricted to such a class of graphs. Extending our polynomial-time approach to deal with . on graphs having bounded dominating sets, we obtain a .-time algorithm to solved . on .-free graphs, improving the current .-time state of the art due to Bonamy, Dabrowski, Feghali, Johnson, and Paulusma [Algorithmica, 2019].
|
| 9 |
Exactly , MSTs: How Many Vertices Suffice? |
Apratim Dutta,Rahul Muthu,Anuj Tawari,V. Sunitha |
|
Abstract
In this work, we study the problem of finding a weighted graph with exactly . minimum spanning trees (MSTs, in short) while minimizing the number of vertices. While finding a graph with . MSTs is easy, finding such a graph with the minimum number of vertices remains an interesting open problem. Recently, Stong [.] proved an upper bound within . multiplicative factor of the minimum. In this work, we prove the following results which make further progress on this problem:
|
| 10 |
Minimum Monotone Tree Decomposition of Density Functions Defined on Graphs |
Lucas Magee,Yusu Wang |
|
Abstract
Monotone trees - trees with a function defined on their vertices that decreases the further away from a root node one travels, are a natural model for a process that weakens the further one gets from its source. Given an aggregation of monotone trees, one may wish to reconstruct the individual monotone components. A natural representation of such an aggregation would be a graph. While many methods have been developed for extracting hidden graph structure from datasets, which makes obtaining such an aggregation possible, decomposing such graphs into the original monotone trees is algorithmically challenging..Recently, a polynomial time algorithm has been developed to extract a minimum cardinality collection of monotone trees (M-Tree Set) from a given density tree - but no such algorithm exists for density graphs that may contain cycles. In this work, we prove that extracting such minimum M-Tree Sets of density graphs is NP-Complete. We additionally prove three additional variations of the problem - such as the minimum M-Tree Set such that the intersection between any two monotone trees is either empty or contractible (SM-Tree Set) - are also NP-Complete. We conclude by providing som
|
| 11 |
|
|
|
Abstract
|
| 12 |
Exact and Approximation Algorithms for the Multi-depot Data Mule Scheduling with Handling Time and T |
Minqin Liu,Wei Yu,Zhaohui Liu,Xinmeng Guo |
|
Abstract
In this paper, we investigate the data mule scheduling with handling time and time span constraints (DMSTC) in which the goal is to minimize the number of data mules dispatched from a depot that are used to serve target sensors located on a wireless sensor network. Each target sensor is associated with a handling time and each dispatched data mule must return to the original depot before time span .. We also study a variant of the DMSTC in which the objective is to minimize the total travel distance of the data mules dispatched..We give exact and approximation algorithms for the DMSTC on a path and their multi-depot version. For the first objective, we show an . polynomial time algorithm for the uniform 2-depot DMSTC on a path where at least one depot is on the endpoint (. indicates the number of target sensors). And we present a new 2-approximation algorithm for the non-uniform DMSTC on a path. For the second objective, we derive an .-time algorithm for the uniform multi-depot DMSTC on a path, where . is the number of depots. For the non-uniform multi-depot DMSTC on a path or cycle, we give a 2-approximation algorithm.
|
| 13 |
Two Exact Algorithms for the Packet Scheduling Problem |
Fei Li,Ningshi Yao |
|
Abstract
We consider a classic packet scheduling problem [.] and its variants. This packet scheduling problem has applications in the areas of logistics, road traffic, and more. There is a network and a set of unit-length packets are to be transmitted over the network from their respective sources to their respective destinations. Each packet is associated with a directed path on which it must travel along. Time is discrete. Initially, all the packets stay on the first edges of their respective paths. Packets are pending on the edges at any time. In each time step, a packet can move along its path by one edge, given that edge having no other packets move onto it in the same time step. The objective is to minimize . – the earliest time by which all the packets arrive at their respective destination edges. This problem was proved NP-hard [.] and it has been studied extensively in the past three decades. In this paper, we first provide a semi-online algorithm GRD and show that GRD is optimal for scheduling packets on arborescence and/or anti-arborescence forests. We then provide a parameterized algorithm PDP which finds an optimal makespan for the general case. PDP is a dynamic programming alg
|
| 14 |
Improved Scheduling with a Shared Resource |
Christoph Damerius,Peter Kling,Florian Schneider |
|
Abstract
We consider the following shared-resource scheduling problem: Given a set of jobs ., for each . we must schedule a job-specific processing volume of .. A total resource of 1 is available at any time. Jobs have a resource requirement ., and the resources assigned to them may vary over time. However, assigning them less will cause a proportional slowdown..We consider two settings. In the first, we seek to minimize the makespan in an online setting: The resource assignment of a job must be fixed before the next job arrives. Here we give an optimal .-competitive algorithm with runtime .. In the second, we aim to minimize the total completion time. We use a continuous linear programming (CLP) formulation for the fractional total completion time and combine it with a previously known dominance property from malleable job scheduling to obtain a lower bound on the total completion time. We extract structural properties by considering a geometrical representation of a CLP’s primal-dual pair. We combine the CLP schedule with a greedy schedule to obtain a .-approximation for this setting. This improves upon the so far best-known approximation factor of 2.
|
| 15 |
An Energy-Efficient Scheduling Method for Real-Time Multi-workflow in Container Cloud |
Zaixing Sun,Zhikai Li,Chonglin Gu,Hejiao Huang |
|
Abstract
Cloud computing has a powerful ability to handle a large number of tasks. Correspondingly, it also consumes a lot of energy. Reducing the energy consumption of cloud service platforms while ensuring the quality of service has become a crucial issue. In this paper, we propose a heuristic energy-saving scheduling algorithm named Real-time Multi-workflow Energy-efficient Scheduling (RMES) with the aim to minimize the total energy consumption in container cloud. RMES executes tasks as parallel as possible to enhance the resource utilization of the running machines in cluster, therefore reducing the time of the global process, saving energy as a result. RMES takes advantage of the affinity between containers and machines to meet the resource quantity and performance requirements of containers during scheduling. In order to follow the change of the system state overtime, we introduce the re-scheduling mechanism, which can automatically adjust the scheduling decisions of the tasks that have not yet been executed in the scheduling scheme. The experimental results show that RMES has obvious advantages over other scheduling algorithms in terms of energy consumption and success ratio.
|
| 16 |
|
|
|
Abstract
|
| 17 |
Weakly Nondominated Solutions of Set-Valued Optimization Problems with Variable Ordering Structures |
Zhiang Zhou,Wenbin Wei,Kequan Zhao |
|
Abstract
In this paper, weakly nondominated solutions of set-valued optimization problems with variable ordering structures are investigated in linear spaces. Firstly, the notion of weakly nondominated element of a set with a variable ordering structure is introduced in linear spaces, and the relationship between weakly nondominated element and nondominated element is also given. Secondly, under the assumption of nearly .-subconvexlikeness of set-valued maps, scalarization theorems of weakly nondominated solutions for unconstrained set-valued optimization problems are established. Finally, two duality theorems of constrained set-valued optimization problems are obtained. Some examples are given to illustrate our results. The results obtained in this paper improve and generalize some known results in the literatures.
|
| 18 |
The MaxIS-Shapley Value in Perfect Graphs |
Junqi Tan,Dongjing Miao,Pengyu Chen |
|
Abstract
We investigate the application of the Shapley value to quantifying the contribution of vertices to the maximum independent set (MaxIS) in perfect graphs. The MaxIS problem in perfect graphs can be computed in polynomial time. Many well-studied families of graphs are perfect, for example, bipartite graphs, chordal graphs, forests, etc. The Shapley value is a widely known numerical measure for assessing the contribution of individuals. We study this measure in the context of MaxIS by redefining corresponding concepts. We show that computing the Shapley value with respect to MaxIS in perfect graphs, bipartite graphs, line graphs of bipartite graphs, chordal graphs is #P-complete. We present parameterized algorithm and polynomial-time algorithm for some special cases: perfect graphs whose vertices have a small number of types, and graphs with maximum degree two. We also propose a fully polynomial-time randomized approximation scheme (FPRAS) for general perfect graphs.
|
| 19 |
Asteroidal Sets and Dominating Paths |
Oleksiy Al-saadi,Jamie Radcliffe |
|
Abstract
An independent set of three vertices is called an asteroidal triple (AT) if there exists a path between any two of them that avoids the neighborhood of the third. Asteroidal triple-free (AT-free) graphs are very well-studied, but some of their various superclasses are not. We study two of these superclasses: hereditary dominating pair (HDP) graphs and diametral path graphs. We correct a mistake that has appeared in the literature claiming that the class of diametral path graphs are a superclass of HDP. More specifically, we show that a graph with a dominating shortest path does not necessarily contain a dominating diametral path. We say a graph is a strict dominating pair graph if it contains a dominating pair but has no dominating diametral path, and we show structural and algorithmic properties of these graphs. To study properties of HDP graphs, we introduce the notion of spread in asteroidal triples. Given a dominating pair, we show that all paths between this pair meet the common neighborhood of some pair from each asteroidal triple. We use these results to improve the best known time complexity for the recognition of chordal HDP graphs.
|
| 20 |
A Novel Approximation Algorithm for Max-Covering Circle Problem |
Kaiqi Zhang,Siyuan Zhang,Jirun Gao,Hongzhi Wang,Hong Gao,Jianzhong Li |
|
Abstract
We study the efficient approximation algorithm for max-covering circle problem. Given a set of weighted points in the plane and a circle with specified size, max-covering circle problem is to find the proper place where the center of the circle is located so that the total weight of the points covered by the circle is maximized. Our core approach is to approximate the circle with a symmetrical rectilinear polygon (SRP). We first present a method to construct the circumscribed SRP of a given circle and disclose their area relationship. Then, we convert max-covering SRP problem to SRP intersection problem, which can be efficiently solved with simple partition and modification based on the existing method. Finally, the optimal solution returned from max-covering SRP problem can be used to produce an approximate answer to max-covering circle problem. We prove that for most of the inputs, our algorithm can give a . approximation to the optimal solution, which only needs . time for unit points and . time for weighted points.
|
|
|
|Archiver|手机版|小黑屋|
派博传思国际
( 京公网安备110108008328)
GMT+8, 2025-7-28 16:52
发表于 2025-3-21 18:25:59
