Aug 2026· Embedded Systems and Applications· pp. 158:1-158:15· 1 citation· 31 references
Computer Science
TL;DR
This paper presents an $\frac{11}{6} \approx 1.83$-competitive algorithm for trees in the more general edge arrival model and gives a 1.5-competitive algorithm and provide a matching lower bound.
Abstract
In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori and the edges arrive one at a time. The goal is to maintain a fractional vertex cover of the tree, i.e., an assignment of fractional weights from [0,1] to the vertices such that the weights of endpoints of every edge sum up to at least one. After each edge arrival, we need to modify the fractional vertex cover to cover the new edge as well. However, we can only increase the values assigned to vertices. The problem was studied before (in the vertex arrival model) by Wang and Wong, who motivated it as a generalization of the ski-rental problem, but also (more importantly) by its close connection to the dual online matching problem. They presented a 1.901-competitive algorithm for general graphs in the vertex arrival model. We present an $\frac{11}{6} \approx 1.83$-competitive algorithm for trees in the more general edge arrival model. In addition, we study the fractional vertex cover problem in an incremental model, where we again seek a fractional vertex cover after every update, but all the updates to the tree are known to the algorithm a priori. In this model, we give a 1.5-competitive algorithm and provide a matching lower bound.
This paper studies fractional matching on general graphs in the fully online model of Huang et al. (JACM 2020), in which all vertices arrive online and remain available for only a limited time, and extends the classic Water-Filling algorithm to the fully online setting, establishing that Water-Filling is not optimal in the fully online setting.
This paper generalises the existing PTAS for complete graphs from a fixed to an arbitrary number of intervals and disprove an existing conjecture, which states that every instance of BIA admits a solution satisfying at least three quarters of all edges.
∗. PeterBlohm, ∗. FlorianChen, A. Gionis et al.· 0 citations
The Minimum Vertex Cover problem is a fundamental combinatorial optimization problem, aiming to identify a minimum subset of vertices in a graph such that every edge is incident to at least one vertex in this subset. Among its variants, the Min-Power-Cover problem stands out due to its practical applications, such as camera placement at intersections: in an edge-weighted graph, an edge is covered if one of its endpoints is assigned a power value at least as large as the edge's weight. In this paper, we introduce the Emergency Vertex Cover (Em-VC) problem where an edge may be covered not only by its endpoints, but also by a distant vertex, provided the vertex is given sufficient power to"cover"the cumulative weight of the edges along a shortest path to one of the edge's endpoints plus the weight of the edge. Em-VC is motivated by different practical scenarios, e.g. the need for urban disaster response, where ensuring accessibility to all road segments (edges of the graph) is crucial for effective aid delivery. We prove that Em-VC is NP-hard, derive lower bounds, and design a polynomial-time algorithm for its continuous version. Moreover, we present a 4/3-approximation algorithm for the discrete case and identify several special graph classes for which the problem can be solved in polynomial time.
Eric Angel, Evangelos Bampas, E. Bampis et al.· 0 citations
It is shown that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order, and under the order-dependent model, where bidirectional Dijkstra is not instance-optimal.
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup et al.· 1 citation
This paper develops an exact algorithm based on the Branch and Bound approach for solving PIDS on chordal graphs, which involves identifying the smallest group of vertices in a given network that maximizes influence throughout the network.
Y A Bekhti, M. Lalou, Méziane Aïder et al.· Pesquisa Operacional· 0 citations
Let be a connected undirected graph, a set of nodes, a set of edges, , and . Given a non‐negative weight function associated with its edges, a set of terminal sets , the Steiner forest problem (SFP) consists of finding a subset of edges with the minimal cost such that all vertices of each (for ) lie in the same connected component in the graph induced by . In this work, as a first contribution, we propose a constructive algorithm for the SFP. Computational experiments on literature instances showed that the results obtained by the constructive algorithm outperformed the state‐of‐the‐art primal‐dual algorithm. Furthermore, as a second contribution, we present two heuristics to solve the SFP: the first, named GRASP‐SFP, based on the GRASP metaheuristic, and the second, called MDM‐GRASP‐SFP, which incorporates a data mining component on GRASP‐SFP. In most test instances provided in the literature, the results obtained by the two proposed algorithms tied for both best and average solution costs. Due to this fact, we generated more challenging SFP instances and the results reached by the proposed hybrid data mining heuristic improved upon those obtained by the original GRASP approach.
Murilo Stockinger, Isabel Rosseti, Simone Martins et al.· International Transactions i...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
