Search

We study an online buffer management problem under the model introduced by Azar and Gilon (2015) [5] recently. Unit-sized packets arrive and are kept in a First-In-First-Out buffer of size B in an online fashion at a network server. Each packet is associated with an arrival time, a value and a processing cycle time in the buffer. The density of a packet is defined to be the ratio of its value to processing time. It is assumed that every packet can be transmitted only after its processing cycle is completed and only the packet at the head of the buffer can be processed. A packet is allowed to be preempted and then discarded from the buffer. But, the value of a packet is attained only if it is successfully transmitted. Under the model, the objective of online buffer management is to maximize the total value of transmitted packets. This model finds applications to packet scheduling in communication networks. In this study, we consider the model with constant density from a theoretical perspective. We first propose some lower bounds for the problem. Azar and Gilon obtained a 4-competitive algorithm for the online buffer management problem for packets with constant density. Here, we present a ( 2 + 1 B − 1 )-competitive algorithm for the case B > 1 as well as its generalization to the multi-buffer model. Moreover, we prove that the competitive ratio of a deterministic online algorithm is at least four when the buffer size is one. We also conduct experiments to demonstrate the superior performance of the proposed online algorithm against the previous approach. [ABSTRACT FROM AUTHOR]

We consider the dynamic map labeling problem: given a set of rectangular labels on the map, the goal is to appropriately select visible ranges for all the labels such that no two consistent labels overlap at every scale and the sum of total visible ranges is maximized. This is also called the active range optimization (ARO) problem defined by Been et al. (2006) [2] . We propose approximation algorithms for several variants of this problem. For the simple ARO problem , we provide a 3 c log ⁡ n -approximation algorithm for unit-width rectangular labels if there is a c -approximation algorithm for the unit-width label placement problem in the plane; and a randomized polynomial-time O ( log ⁡ n log ⁡ log ⁡ n ) -approximation algorithm for arbitrary rectangular labels. For the general ARO problem , we prove that it remains NP-complete even for congruent square labels with equal selectable scale range. Moreover, we contribute 12-approximation algorithms for both arbitrary square labels and unit-width rectangular labels, and a 6-approximation algorithm for congruent square labels, and show that the bounds are tight. [ABSTRACT FROM AUTHOR]

The increasing concern over global warming has led to the rapid development of the electric vehicle industry. Electric vehicles (EVs) have the potential to reduce the greenhouse effect and facilitate more efficient use of energy resources. In this paper, we study several EV route planning problems that take into consideration possible battery charging or swapping operations. Given a road network, the objective is to determine the shortest (travel time) route that a vehicle with a given battery capacity can take to travel between a pair of vertices or to visit a set of vertices with several stops, if necessary, at battery switch stations. We present polynomial time algorithms for the EV shortest travel time path problem and the fixed tour EV touring problem , where the fixed tour problem requires visiting a set of vertices in a given order. Based on the result, we also propose constant factor approximation algorithms for the EV touring problem , which is a generalization of the traveling salesman problem. [ABSTRACT FROM AUTHOR]

With a rapidly growing attention on the development of learning-augmented algorithms, we revisit the classical online traveling salesman problem (OLTSP) from the perspective of such learning approaches. A learning-augmented online algorithm, or simply an online algorithm with predictions, considers how to improve its competitive performance with theoretical guarantees by forecasting the information of future requests, e.g., their release time or locations in the OLTSP. In this study, we investigate the OLTSP on the real line, motivated by the parcel picking problem in a smart warehouse, which aims at scheduling a route for a server (saying, a Kiva robot), starting at the origin, serving all online requests and returning to the origin such that the completion time is minimized. Each online request is released over time on the real line and the server moves back and forth along the line with unit speed. We mainly focus on zealous algorithms, a special type of online algorithms for the OLTSP which never allow the sever to wait if there are still unserved requests, and exploit a specific forecasting strategy, called online predictions, which makes a sequence of predictions one by one in an online manner. In order to ensure better competitive performance, we particularly explore the worst-case scenarios that restrict the power of such predictions. Based on the discussion, we make an assumption in which online predictions are guaranteed to be useful, and devise a learning-augmented algorithm with max 6 λ + 1 4 λ , 2 λ + 1 2 λ -robustness and max 3 2 + η t + η p O P T , 6 + λ 4 + (1 − λ) η p O P T -consistency, 0 < λ ≤ 1 , comparing to the previous lower bound of 7 4 , where η t and η p which indicate prediction errors are sufficiently small constants. Moreover, we also conduct numerical experiments to demonstrate the practical effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Because high-dimensional wafer bin maps (WBMs) cause various features, it is difficult to search the similarity among WBMs via conventional pattern recognition methods. This study develops a novel morphology-based support vector machine for defective wafer detection. The experimental results demonstrate its usefulness in yield improvements on precision and computation cost. [ABSTRACT FROM AUTHOR]

Abstract: The Canadian Traveller Problem (CTP) is to find the shortest route from a source to a destination under uncertain conditions. Some roads may be blocked by accidents, and a traveller only discovers a blockage upon reaching an adjacent site of the road. More precisely, the objective of this problem is to design an adaptive strategy against a malicious adversary who sets up road blockages in order to maximize the gap between the distance cost resulting from the strategy and the distance cost of the static shortest path in which all blockages are known a priori. This study investigates a variation of the Travelling Salesman Problem that involves finding the shortest tour, visiting a set of locations, and returning to the origin under the same uncertainty as that of the CTP. This online routing problem, called the Covering Canadian Traveller Problem (CCTP), has real applications in dynamic navigation systems such as delivery routing in express logistics. We study this problem from a competitive analysis perspective, and present an efficient touring strategy within an -competitive ratio, where the number of blockages is up to k. We also demonstrate the tightness of the competitive analysis. [Copyright &y& Elsevier]

A set S⊆ V is a power dominating set (PDS) of a graph G=( V, E) if every vertex and every edge in G can be observed based on the observation rules of power system monitoring. The power domination problem involves minimizing the cardinality of a PDS of a graph. We consider this combinatorial optimization problem and present a linear time algorithm for finding the minimum PDS of an interval graph if the interval ordering of the graph is provided. In addition, we show that the algorithm, which runs in Θ( nlog n) time, where n is the number of intervals, is asymptotically optimal if the interval ordering is not given. We also show that the results hold for the class of circular-arc graphs. [ABSTRACT FROM AUTHOR]

Orthogonal range search is ubiquitous nowadays, with natural applications in databases, data mining, and text indexing. Very recently, yet another application was discovered, which is to maintain a DFS forest in a dynamic graph. In this paper, we want to extend the above recent study, by applying orthogonal range search to efficient maintenance of a BFS-like forest, called no-back-edge-traversal (NBET) forest, which refers to a spanning forest obtained from a traversal that does not create any back edge. The study of such a problem is motivated by the fact that NBET forest can be used as a strong certificate of 2-connectivity of an undirected graph, which is more general than a spanning forest obtained from a scan-first search traversal. [ABSTRACT FROM AUTHOR]

The spanning star forest problem is an interesting algorithmic problem in combinatorial optimization and finds different applications. We generalize it into the spanning k-tree forest problem, which is to find a maximum spanning forest in which each tree component has a central vertex and other vertices in the component have distance at most k away from the central vertex. We show that this new problem can be approximated with ratio in polynomial time for both undirected and directed graphs. In the weighted distance model, a ½-approximation algorithm is presented for it. [ABSTRACT FROM AUTHOR]

We consider a generalization of the well-known domination problem on graphs. The ( soft) capacitated domination problem with demand constraints is to find a dominating set D of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demands of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies the demand of each vertex in V to be met by the capacities of vertices in D dominating it. In this paper, we study the capacitated domination problem on trees from an algorithmic point of view. We present a linear time algorithm for the unsplittable demand model, and a pseudo-polynomial time algorithm for the splittable demand model. In addition, we show that the capacitated domination problem on trees with splittable demand constraints is NP-complete (even for its integer version) and provide a polynomial time approximation scheme (PTAS). We also give a primal-dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs. [ABSTRACT FROM AUTHOR]

In this paper, we study online algorithms for the Canadian Traveller Problem defined by Papadimitriou and Yannakakis in 1991. This problem involves a traveller who knows the entire road network in advance, and wishes to travel as quickly as possible from a source vertex s to a destination vertex t, but discovers online that some roads are blocked (e.g., by snow) once reaching them. Achieving a bounded competitive ratio for the problem is PSPACE-complete. Furthermore, if at most k roads can be blocked, the optimal competitive ratio for a deterministic online algorithm is 2 k + 1 , while the only randomized result known so far is a lower bound of k + 1 . We show, for the first time, that a polynomial time randomized algorithm can outperform the best deterministic algorithms when there are at least two blockages, and surpass the lower bound of 2 k + 1 by an o(1) factor. Moreover, we prove that the randomized algorithm can achieve a competitive ratio of (1 + 2 2) k + 2 in pseudo-polynomial time. The proposed techniques can also be exploited to implicitly represent multiple near-shortest s-t paths. [ABSTRACT FROM AUTHOR]

In the general max–min fair allocation problem, there are m players and n indivisible resources, each player has his/her own utilities for the resources, and the goal is to find an assignment that maximizes the minimum total utility of resources assigned to a player. The problem finds many natural applications such as bandwidth distribution in telecom networks, processor allocation in computational grids, and even public-sector decision making. We introduce an over-estimation strategy to design approximation algorithms for this problem. When all utilities are positive, we obtain an approximation ratio of c 1 - ϵ , where c is the maximum ratio of the largest utility to the smallest utility of any resource. When some utilities are zero, we obtain an approximation ratio of (1 + 3 c ^ + O (δ c ^ 2)) , where c ^ is the maximum ratio of the largest utility to the smallest positive utility of any resource. [ABSTRACT FROM AUTHOR]

The online car-sharing problem finds many real-world applications. The problem, proposed by Luo, Erlebach and Xu in 2018, mainly focuses on an online model in which there are two locations: 0 and 1, and k total cars. Each request which specifies its pick-up time and pick-up location (among 0 and 1, and the other is the drop-off location) is released in each stage a fixed amount of time before its specified start (i.e. pick-up) time. The time between the booking (i.e. released) time and the start time is enough to move empty cars between 0 and 1 for relocation if they are not used in that stage. The model, called k S2L-F, assumes that requests in each stage arrive sequentially regardless of the same booking time and the decision (accept or reject) must be made immediately. The goal is to accept as many requests as possible. In spite of only two locations, the analysis does not seem easy and the (tight) competitive ratio (CR) is only known to be 2 for k = 2 and 1.5 for a restricted value of k , i.e., a multiple of three. In this paper, we remove all the holes of unknown CR's; namely we prove that the CR is 2 k k + ⌊ k / 3 ⌋ for all k ≥ 2. Furthermore, if the algorithm can delay its decision until all requests have come in each stage, the CR is improved to roughly 4/3. We can take this advantage even further; precisely we can achieve a CR of 2 + R 3 if the number of requests in each stage is at most Rk , 1 ≤ R ≤ 2 , where we do not have to know the value of R in advance. Finally we demonstrate that randomization also helps to get (slightly) better CR's, and prove some lower bounds to show the tightness. [ABSTRACT FROM AUTHOR]

Motivation: The global alignment of protein interaction networks is a widely studied problem. It is an important first step in understanding the relationship between the proteins in different species and identifying functional orthologs. Furthermore, it can provide useful insights into the species’ evolution.Results: We propose a novel algorithm, PISwap, for optimizing global pairwise alignments of protein interaction networks, based on a local optimization heuristic that has previously demonstrated its effectiveness for a variety of other intractable problems. PISwap can begin with different types of network alignment approaches and then iteratively adjust the initial alignments by incorporating network topology information, trading it off for sequence information. In practice, our algorithm efficiently refines other well-studied alignment techniques with almost no additional time cost. We also show the robustness of the algorithm to noise in protein interaction data. In addition, the flexible nature of this algorithm makes it suitable for different applications of network alignment. This algorithm can yield interesting insights into the evolutionary dynamics of related species.Availability: Our software is freely available for non-commercial purposes from our Web site, http://piswap.csail.mit.edu/.Contact: bab@csail.mit.edu or csliao@ie.nthu.edu.twSupplementary information: Supplementary data are available at Bioinformatics online. [ABSTRACT FROM AUTHOR]

This study considers the soft capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-weighted graph G = (V , E) , which allows edge insertions and edge deletions, the goal is to design a data structure that maintains an approximate minimum vertex cover while satisfying the capacity constraint of each vertex. That is, when picking a copy of a vertex v in the cover, the number of v's incident edges covered by the copy is up to a given capacity of v. We extend Bhattacharya et al.'s work [SODA'15 and ICALP'15] to obtain a deterministic primal-dual algorithm for maintaining a constant-factor approximate minimum capacitated vertex cover with O (log n / ϵ) amortized update time, where n is the number of vertices in the graph. The algorithm can be extended to (1) a more general model in which each edge is associated with a non-uniform and unsplittable demand, and (2) the more general capacitated set cover problem. [ABSTRACT FROM AUTHOR]