Given a fleet of drones with different speeds and a set of package delivery requests, the collaborative delivery problem asks for a schedule for the drones to collaboratively carry out all package deliveries, with the objective of minimizing the total travel time of all drones. We show that the best non-preemptive schedule (where a package that is picked up at its source is immediately delivered to its destination by one drone) is within a factor of three of the best preemptive schedule (where several drones can participate in the delivery of a single package). Then, we present a constant-factor approximation algorithm for the problem of computing the best non-preemptive schedule. The algorithm reduces the problem to a tree combination problem and uses a primal-dual approach to solve the latter. We have implemented a version of the algorithm optimized for practical efficiency and report the results of experiments on large-scale instances with synthetic and real-world data, demonstrating that our algorithm is scalable and delivers schedules of excellent quality.

A temporal graph 𝒢 = (G,λ) can be represented by an underlying graph G = (V,E) together with a function λ that assigns to each edge e ∈ E the set of time steps during which e is present. The reachability graph of 𝒢 is the directed graph D = (V,A) with (u,v) ∈ A if and only if there is a temporal path from u to v. We study the Reachability Graph Realizability (RGR) problem that asks whether a given directed graph D = (V,A) is the reachability graph of some temporal graph. The question can be asked for undirected or directed temporal graphs, for reachability defined via strict or non-strict temporal paths, and with or without restrictions on λ (simple, proper, or both). Answering an open question posed by Casteigts et al. (TCS 2024), we show that all variants of the problem are NP-complete, except for two variants that become trivial in the directed case. For undirected temporal graphs, we consider the complexity of the problem with respect to the solid graph, that is, the graph containing all edges that could potentially receive a label in any realization. We show that the RGR problem is fixed-parameter tractable for the feedback edge set number of the solid graph. As we show, the latter parameter can presumably not be replaced by smaller parameters like feedback vertex set number or treedepth, since the problem is W[2]-hard for them.

The paper considers the problem of file sharing among peers who are connected to a common core network through links of differing upload and download capacities, as is the case in networks provisioned according to the hose model. The file is assumed to be divided into equal-sized chunks, and a peer can start sending a "chunk" of the file to another peer only after it has received the entire chunk. The objective is to share a chunk, initially residing on one of the peers, with all other peers in the least time possible. Peers can simultaneously send/receive parts of a chunk to/from multiple peers, subject to the upload and download capacity constraints. We only consider the problem of broadcasting one chunk to all peers. We consider two different models - in the migratory model, a peer can receive the chunk from multiple peers, while in the non-migratory model, any peer can receive the chunk only from one peer. For the migratory model, introduced in this paper, we show a novel integer program and use the optimum solution to the LP-relaxation to give a schedule with makespan e^{1/e} OPT+P where P is the time required by the slowest peer to download the chunk. Minimising makespan in the non-migratory model is known to be NP-hard. We give a solution with makespan 18OPT+P and this is the first approximation algorithm for heterogeneous and asymmetric upload/download capacities. We also consider 2 special cases. For uniform download capacities, we obtain a solution with makespan 2OPT extending a result due to Liu [Pangfeng Liu, 2002]. For uniform upload capacities, we give the first approximation algorithm, producing makespan at most 2OPT+2P.

In the periodic temporal graph realization problem introduced by Klobas et al. [SAND '24] one is given a period Δ and an n × n matrix D of desired fastest travel times, and the task is to decide if there is a simple periodic temporal graph with period Δ such that the fastest travel time between any pair of vertices matches the one specified by D . We generalize the problem from simple temporal graphs to temporal graphs where each edge can appear up to ℓ times in each period, for some given integer ℓ . For the resulting problem Multi-Label Periodic TGR , we show that it is fixed-parameter tractable for parameter n and for parameter vc + Δ , where vc is the vertex cover number of the underlying graph. We also show the existence of a polynomial kernel for parameter nu + d max , where nu is the number of non-universal vertices of the underlying graph and d max is the largest entry of D . Furthermore, we show that the problem is NP -hard for each ℓ ≥ 5 , even if the underlying graph is a tree, a case that was known to be solvable in polynomial time if the task is to construct a simple periodic temporal graph, that is, if ℓ = 1 .

We study the two-sided stable matching problem with one-sided uncertainty for two sets of agents A and B, with equal cardinality. Initially, the preference lists of the agents in A are given but the preferences of the agents in B are unknown. An algorithm can make queries to reveal information about the preferences of the agents in B. We examine three query models: comparison queries, interviews, and set queries. Using competitive analysis, our aim is to design algorithms that minimize the number of queries required to solve the problem of finding a stable matching or verifying that a given matching is stable (or stable and optimal for the agents of one side). We present various upper and lower bounds on the best possible competitive ratio as well as results regarding the complexity of the offline problem of determining the optimal query set given full information.

Motivated by settings such as medical treatments or aircraft maintenance, we consider a scheduling problem with jobs that consist of two operations, a test and a processing part. The time required to execute the test is known in advance while the time required to execute the processing part becomes known only upon completion of the test. We use competitive analysis to study algorithms for minimizing the sum of completion times for $n$ given jobs on a single machine. As our main result, we prove using a novel analysis technique that the natural $1$-SORT algorithm has competitive ratio at most 1.861. For the special case of uniform test times, we show that a simple threshold-based algorithm has competitive ratio at most 1.585. We also prove a lower bound that shows that no deterministic algorithm can be better than $\sqrt{2}$-competitive even in the case of uniform test times.

Temporal graphs are graphs where the edge set can change in each time step, and the vertex set stays the same. Exploration of temporal graphs whose snapshot in each time step is a connected graph, called connected temporal graphs, has been widely studied. We extend the concept of graph automorphisms from static graphs to temporal graphs and show that symmetries enable faster exploration: We prove that a connected temporal graph with $n$ vertices and orbit number $r$ (i.e., $r$ is the number of automorphism orbits) can be explored in $O(r n^{1+ε})$ time steps, for any fixed $ε>0$. For $r=O(n^c)$ for constant $c<1$, this is a significant improvement over the known tight worst-case bound of $Θ(n^2)$ time steps for arbitrary connected temporal graphs. We also give two lower bounds for exploration, showing that $Ω(n \log n)$ time steps are required for some inputs with $r=O(1)$ and that $Ω(rn)$ time steps are required for some inputs for any $r$ with $1\le r\le n$. The techniques we develop for fast exploration are used to derive the following result for rendezvous in connected temporal graphs: Two agents are placed by an adversary at arbitrary vertices and given full information about the temporal graph, except that they do not have consistent vertex labels. The agents can meet at a common vertex after $O(n^{1+ε})$ time steps, for any $ε>0$. For some connected temporal graphs with constant orbit number we present a complementary lower bound of $Ω(n\log n)$ time steps. Finally, we give a randomized algorithm to construct a temporal walk $W$ that visits all vertices of a given orbit with probability at least $1-ε$ for any $0<ε<1$ such that $W$ spans $O((n^{5/3}+rn)\log n)$ time steps. The runtime of this algorithm consists of $O(n^{1/3} \log (n/ε))$ linear-time scans of the snapshots that exist in this time span.

We introduce a cops and robbers game with one cop and one robber on a special type of time-varying graphs (TVGs), namely edge-periodic graphs. These are TVGs in which, for each edge e, a binary string τ(e) is given such that the edge e is present in time step t if and only if τ(e) contains a 1 at position tmod|τ(e)|. This periodicity allows for a compact representation of infinite TVGs. We prove that even for very simple underlying graphs, i.e., directed and undirected cycles, the problem of deciding whether a cop-winning strategy exists is NP-hard and W[1]-hard parameterized by the number of vertices. Furthermore, we show that this decision problem can be solved on general edge-periodic graphs in PSPACE. Finally, we present tight bounds on the minimum length of a directed or undirected cycle that guarantees the cycle to be robber-winning.

Learning-augmented algorithms have been attracting increasing interest, but have only recently been considered in the setting of explorable uncertainty where precise values of uncertain input elements can be obtained by a query and the goal is to minimize the number of queries needed to solve a problem. We study learning-augmented algorithms for sorting and hypergraph orientation under uncertainty, assuming access to untrusted predictions for the uncertain values. Our algorithms provide improved performance guarantees for accurate predictions while maintaining worst-case guarantees that are best possible without predictions. For sorting, our algorithm uses the optimal number of queries for accurate predictions and at most twice the optimal number for arbitrarily wrong predictions. For hypergraph orientation, for any γ≥2, we give an algorithm that uses at most 1+1/γ times the optimal number of queries for accurate predictions and at most γ times the optimal number for arbitrarily wrong predictions. These tradeoffs are the best possible. We also consider different error metrics and show that the performance of our algorithms degrades smoothly with the prediction error in all the cases where this is possible.

Abstract In computing with explorable uncertainty, one considers problems where the values of some input elements are uncertain, typically represented as intervals, but can be obtained using queries. Previous work has considered query minimization in the settings where queries are asked sequentially (adaptive model) or all at once (non-adaptive model). We introduce a new model where k queries can be made in parallel in each round, and the goal is to minimize the number of query rounds. Using competitive analysis, we present upper and lower bounds on the number of query rounds required by any algorithm in comparison with the optimal number of query rounds for the given instance. Given a set of uncertain elements and a family of m subsets of that set, we study the problems of sorting all m subsets and of determining the minimum value (or the minimum element(s)) of each subset. We also study the selection problem, i.e., the problem of determining the i-th smallest value and identifying all elements with that value in a given set of uncertain elements. Our results include 2-round-competitive algorithms for sorting and selection and an algorithm for the minimum value problem that uses at most $$(2+\varepsilon ) \cdot \mathrm {opt}_k+\mathrm {O}\left( \frac{1}{\varepsilon } \cdot \lg m\right) $$ ( 2 + ε ) · opt k + O 1 ε · lg m query rounds for every $$0<\varepsilon <1$$ 0 < ε < 1 , where $$\mathrm {opt}_k$$ opt k is the optimal number of query rounds.

We study the fixed-parameter tractability of the problem of deciding whether a given temporal graph admits a temporal walk that visits all vertices (temporal exploration) or, in some variants, a certain subset of the vertices. In the strict variant, edges must be traversed in strictly increasing timesteps; in the non-strict variant, any number of edges can be traversed in each timestep. For both variants, we give FPT algorithms for finding a temporal walk that visits a given set X of vertices, parameterized by |X|, and for finding a temporal walk that visits at least k distinct vertices, parameterized by k. We also show W[2]-hardness for a set version of temporal exploration. For the non-strict variant, we give an FPT algorithm for temporal exploration parameterized by the lifetime, and show that temporal exploration can be solved in polynomial time if the graph in each timestep has at most two connected components.

We study how to utilize (possibly erroneous) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. Our aim is to minimize the number of queries needed to solve the minimum spanning tree problem, a fundamental combinatorial optimization problem that has been central also to the research area of explorable uncertainty. For all integral $γ\ge 2$, we present algorithms that are $γ$-robust and $(1+\frac{1}γ)$-consistent, meaning that they use at most $γOPT$ queries if the predictions are arbitrarily wrong and at most $(1+\frac{1}γ)OPT$ queries if the predictions are correct, where $OPT$ is the optimal number of queries for the given instance. Moreover, we show that this trade-off is best possible. Furthermore, we argue that a suitably defined hop distance is a useful measure for the amount of prediction error and design algorithms with performance guarantees that degrade smoothly with the hop distance. We also show that the predictions are PAC-learnable in our model. Our results demonstrate that untrusted predictions can circumvent the known lower bound of~$2$, without any degradation of the worst-case ratio. To obtain our results, we provide new structural insights for the minimum spanning tree problem that might be useful in the context of query-based algorithms regardless of predictions. In particular, we generalize the concept of witness sets -- the key to lower-bounding the optimum -- by proposing novel global witness set structures and completely new ways of adaptively using those.

For the problem of delivering a package from a source node to a destination node in a graph using a set of drones, we study the setting where the movements of each drone are restricted to a certain subgraph of the given graph. We consider the objectives of minimizing the delivery time (problem DDT) and of minimizing the total energy consumption (problem DDC). For general graphs, we show a strong inapproximability result and a matching approximation algorithm for DDT as well as NP-hardness and a 2-approximation algorithm for DDC. For the special case of a path, we show that DDT is NP-hard if the drones have different speeds. For trees, we give optimal algorithms under the assumption that all drones have the same speed or the same energy consumption rate. The results for trees extend to arbitrary graphs if the subgraph of each drone is isometric.

Abstract A temporal graph with lifetime L is a sequence of L graphs $$G_1, \ldots ,G_L$$ G 1 , … , G L , called layers, all of which have the same vertex set V but can have different edge sets. The underlying graph is the graph with vertex set V that contains all the edges that appear in at least one layer. The temporal graph is always connected if each layer is a connected graph, and it is k -edge-deficient if each layer contains all except at most k edges of the underlying graph. For a given start vertex s , a temporal exploration is a temporal walk that starts at s , traverses at most one edge in each layer, and visits all vertices of the temporal graph. We show that always-connected, k -edge-deficient temporal graphs with sufficient lifetime can always be explored in $$O(kn \log n)$$ O ( k n log n ) time steps. We also construct always-connected, k -edge-deficient temporal graphs for which any exploration requires $$\varOmega (n \log k)$$ Ω ( n log k ) time steps. For always-connected, 1-edge-deficient temporal graphs, we show that O ( n ) time steps suffice for temporal exploration.

A temporal graph is a graph whose edge set can change over time. We only require that the edge set in each time step forms a connected graph. The temporal exploration problem asks for a temporal walk that starts at a given vertex, moves over at most one edge in each time step, visits all vertices, and reaches the last unvisited vertex as early as possible. We show in this paper that every temporal graph with n vertices can be explored in O(n^{1.75}) time steps provided that either the degree of the graph is bounded in each step or the temporal walk is allowed to make two moves per step. This result is interesting because it breaks the lower bound of Omega(n^2) steps that holds for the worst-case exploration time if only one move per time step is allowed and the graph in each step can have arbitrary degree. We complement this main result by a logarithmic inapproximability result and a proof that for sparse temporal graphs (i.e., temporal graphs with O(n) edges in the underlying graph) making O(1) moves per time step can improve the worst-case exploration time at most by a constant factor.

We study an on-line scheduling problem that is motivated by applications such as car-sharing for trips between an airport and a group of hotels. Users submit ride requests, and the scheduler aims to accept requests of maximum total profit using k servers (cars). Each ride request specifies the pick-up time, the pick-up location, and the drop-off location, where one of the two locations must be the airport. A request must be submitted a fixed amount of time before the pick-up time. The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted (booking time). In the unit travel time variant, the travel time between the airport and any hotel is a fixed value t. We give a 2-competitive algorithm for the case in which the booking interval (pick-up time minus booking time) is at least t and the number of servers is even. In the arbitrary travel time variant, the travel time between the airport and a hotel may have arbitrary length between t and L t for some L >= 1. We give an algorithm with competitive ratio O(log L) if the number of servers is at least ceil[log L]. For both variants, we prove matching lower bounds on the competitive ratio of any deterministic on-line algorithm.

We introduce a novel model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by an a priori unknown amount) by testing the job. Testing a job j takes one unit of time and may reduce its processing time from the given upper limit p'_j (which is the time taken to execute the job if it is not tested) to any value between 0 and p'_j. This setting is motivated e.g. by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times on a single machine. All jobs are available from the start, but the reduction in their processing times as a result of testing is unknown, making this an online problem that is amenable to competitive analysis. The need to balance the time spent on tests and the time spent on job executions adds a novel flavor to the problem. We give the first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized online algorithms.

Consider a problem where 4k given vectors need to be partitioned into k clusters of four vectors each. A cluster of four vectors is called a quad, and the cost of a quad is the sum of the component-wise maxima of the four vectors in the quad. The problem is to partition the given 4k vectors into k quads with minimum total cost. We analyze a straightforward matching-based algorithm and prove that this algorithm is a 3/2-approximation algorithm for this problem. We further analyze the performance of this algorithm on a hierarchy of special cases of the problem and prove that, in one particular case, the algorithm is a 5/4-approximation algorithm. Our analysis is tight in all cases except one.

We study an on-line scheduling problem that is motivated by applications such as car-sharing, in which users submit ride requests, and the scheduler aims to accept requests of maximum total profit using k servers (cars). Each ride request specifies the pick-up time and the pick-up location (among two locations, with the other location being the destination). The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted (booking time). We consider two variants of the problem with respect to constraints on the booking time: In the fixed booking time variant, a request must be submitted a fixed amount of time before the pick-up time. In the variable booking time variant, a request can be submitted at any time during a certain time interval (called the booking horizon) that precedes the pick-up time. We present lower bounds on the competitive ratio for both variants and propose a balanced greedy algorithm (BGA) that achieves the best possible competitive ratio. We prove that, for the fixed booking time variant, BGA is 1.5-competitive if k=3i ( i in N) and the fixed booking length is not less than the travel time between the two locations; for the variable booking time variant, BGA is 1.5-competitive if k=3i ( i in N) and the length of the booking horizon is less than the travel time between the two locations, and BGA is 5/3-competitive if k=5i ( i in N) and the length of the booking horizon is not less than the travel time between the two locations.

A temporal graph can be viewed as a sequence of static graphs indexed by discrete time steps. The vertex set of each graph in the sequence remains the same; however, the edge sets are allowed to differ. A natural problem on temporal graphs is the Temporal Exploration problem (TEXP): given, as input, a temporal graph G of order n, we are tasked with computing an exploration schedule (i.e., a temporal walk that visits all vertices in G), such that the time step at which the walk arrives at the last unvisited vertex is minimised (we refer to this time step as the arrival time). It can be easily shown that general temporal graphs admit exploration schedules with arrival time no greater than O(n^2). Moreover, it has been shown previously that there exists an infinite family of temporal graphs for which any exploration schedule has arrival time Omega(n^2), making these bounds tight for general TEXP instances. We consider restricted instances of TEXP, in which the temporal graph given as input is, in every time step, of maximum degree d; we show an O(n^2/log n) bound on the arrival time when d is constant, and an O(d log d * n^2/log n) bound when d is given as some function of n.

In this paper, we consider an on-line scheduling problem that is motivated by applications such as car sharing, in which users submit ride requests, and the scheduler aims to accept requests of maximum total profit using two servers (cars). Each ride request specifies the pick-up time and the pick-up location (among two locations, with the other location being the destination). The length of the time interval between the submission of a request (booking time) and the pick-up time is fixed. The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted. We present lower bounds on the competitive ratio for this problem and propose a smart greedy algorithm that achieves the best possible competitive ratio.

Although cloud computing greatly utilises virtualised environments for applications to be executed efficiently in low-cost hosting, it has turned energy wasting and overconsumption issues into major concerns. Cloud infrastructure is built on a great amount of server equipment, including high performance computing (HPC), and the servers are naturally prone to failures. In this paper, we report on an energy optimisation approach for scheduling HPC applications, applied to decentralised clouds system, that takes dataset transmission energy into account. The optimisation supports combining two conflicting objectives: minimising energy consumption in conjunction with the avoidance of application deadline violations caused by resource failures. Furthermore, we propose two decision strategies for weighing these conflicting objectives dynamically to account for their significance towards producing an ideal energy efficiency and resource utilisation. Through our developed simulation and experimental analysis using real parallel workloads from large-scale systems, the results illustrate that our approach provides promising energy savings with acceptable level of resource reliability.

The increased computational needs in many sectors place huge demands on cloud computing. Power consumption and resource pool capacity are two of the challenges faced by the next generation of high performance computing (HPC). This paper aims at minimising the computing-energy consumption in decentralised multi-cloud systems using Dynamic Voltage and Frequency Scaling (DVFS) when scheduling dependent HPC tasks under deadline constraints. We propose an energy-aware scheduling algorithm EAGS. To demonstrate the efficiency of our algorithm EAGS, we compare it with the Cloud min-min Scheduling (CMMS) algorithm in different experiments. The simulation results show that our algorithm can produce energy consumption lower than CMMS by an average of 63.9%.

Mobile sinks have been used recently, mainly to minimize energy consumption and to resolve some other issues including data collection from disconnected networks, energy depletion from sensor nodes which are close to the sink, etc. In this paper, we address the problem of finding an optimal path for the mobile sink to traverse through the sensing field, to collect a single packet from each sensor and return back to its initial point (starting point) such that the total energy use is minimized and subject to the length constraint L. We refer to this as the minimum energy cost mobile sink restricted tour problem (MMRTP), and show that this problem is NP-hard. Second, we propose two algorithms. The first algorithm is a heuristic one based on the maximum ratio criteria, while the second algorithm is based on the dynamic programming technique. We consider two scenarios for each algorithm. In the first scenario, there is no restriction on the transmission range of the nodes, whereas in the second scenario, the maximum transmission range is Rmax. Finally, we evaluate the performance of our proposed algorithms based on the MATLAB simulations for two different network sizes and show their effectiveness in terms of energy consumption. Moreover, the simulation results show that our second proposed algorithm has significant impact on energy consumption in comparison with the algorithm of [20] for the same parameters (i.e. Lengths and transmission ranges).

Data collection is one of the predominant operations in wireless sensor networks. This paper focuses on the problem of efficient data collection in a setting where some nodes may not possess data each time data is collected. In that case, idle listening slots may occur, which lead to a waste of energy and an increase in latency. To alleviate these problems, successive-slot schedules were proposed by Zhao and Tang (Infocom 2011). In this paper, we introduce a so-called extra-bit technique to reduce idle listening further. Each packet includes an extra bit that informs the receiver whether further data packets will follow or not. The extra-bit technique leads to significantly reduced idle listening and improved latency in many cases. We prove that every successive-slot schedule is also an extra-bit schedule. We then consider the special case of linear networks and prove that the optimal length of a successive-slot schedule (or extra-bit schedule) is 4N - 6 time slots, where N ≥ 3 is the number of nodes excluding the sink. Then the proposed extra-bit technique is compared with the successive-slot technique with respect to the expected amount of idle listening, and it is shown that the extra-bit technique reduces idle listening substantially.

We study the problem of maximising the lifetime of a sensor network for fault-tolerant target coverage in a setting with composite events. Here, a composite event is the simultaneous occurrence of a combination of atomic events, such as the detection of smoke and high temperature. We are given sensor nodes that have an initial battery level and can monitor certain event types, and a set of points at which composite events need to be detected. The points and sensor nodes are located in the Euclidean plane, and all nodes have the same sensing radius. The goal is to compute a longest activity schedule with the property that at any point in time, each event point is monitored by at least two active sensor nodes. We present a (6+ε)-approximation algorithm for this problem by devising an approximation algorithm with the same ratio for the dual problem of minimising the weight of a fault-tolerant sensor cover and applying the Garg-Könemann algorithm. Our algorithm for the minimum-weight fault-tolerant sensor cover problem generalises previous approximation algorithms for geometric set cover with weighted unit disks and is obtained by enumerating properties of the optimal solution that guide a dynamic programming approach.

Broadcast Scheduling is a popular method for disseminating information in response to client requests. There are n pages of information, and clients request pages at different times. However, multiple clients can have their requests satisfied by a single broadcast of the requested page. In this article, we consider several related broadcast scheduling problems. One central problem we study simply asks to minimize the maximum response time (over all requests). Another related problem we consider is the version in which every request has a release time and a deadline, and the goal is to maximize the number of requests that meet their deadlines. While approximation algorithms for both these problems were proposed several years back, it was not known if they were NP-complete. One of our main results is that both these problems are NP-complete. In addition, we use the same unified approach to give a simple NP-completeness proof for minimizing the sum of response times. A very complicated proof was known for this version. Furthermore, we give a proof that FIFO is a 2-competitive online algorithm for minimizing the maximum response time (this result had been claimed earlier with no proof) and that there is no better deterministic online algorithm (this result was claimed earlier as well, but with an incorrect proof).

Titlepage, Table of Contents, Preface, Organization.

Compliance with the Gao-Rexford conditions [1] is perhaps the most realistic explanation of Internet routing stability, although BGP is renowned to be prone to oscillations. Informally, the Gao-Rexford conditions assume that (i) the business relationships between Internet Service Providers (ISPs) yield a hierarchy, (ii) each ISP behaves in a rational way, i.e., it does not offer transit to other ISPs for free, and (iii) each ISP ranks routes through customers better than routes through providers and peers.

Abstract—If a set K of nodes in a wireless network want to set up a routing structure that allows them to communicate with each other, one possible approach is to use a Steiner tree that spans all the nodes in K. However, a tree can be disconnected by the failure of a single link, and so it is desirable to employ other routing structures that are fault-tolerant. Furthermore, many real-world wireless networks are heterogeneous, meaning that the suitability of nodes for inclusion in the routing structure varies significantly. Therefore, it is meaningful to assign weights to the nodes and aim to compute a fault-tolerant routing structure of minimum total weight. In this paper, we model this problem as the problem of computing a minimum-weight 2-edge-connected Steiner subgraph spanning a given set of terminals, and we propose a constant-factor approximation algorithm for this problem in wireless networks that are modelled as unit disk graphs or quasi unit disk graphs. I.

Broadcasting is a fundamental operation underlying different routing, multicasting and address resolution protocols. Broadcasting in a network requires that all the nodes in the network receive the broadcast packet. Mobility in the network induces link failures which cause some nodes to lose the broadcast packets. Objective of all broadcasting protocols is to achieve high reachability while keeping the broadcast redundancy as low as possible. In this paper we propose a cross layer protocol, called cross layer mobility adaptive broadcasting (CMAB) to handle the mobility in mobile ad hoc networks (MANETs). CMAB uses two Disjoint Sets of Broadcast Relay Gateways (BRGs1 and BRG2) to ensure high reliability in case of high mobility. Our approach minimizes broadcast redundancy by activating the second set of BRG2s only in highly mobile scenarios. A further reduction in broadcast redundancy is achieved by forcing the second Disjoint BRG2 to rebroadcast only if it is covering a maximum number of 2-hop neighbors of upstream sender or source to be covered by BRG1. The proposed protocol balances the retransmission redundancy avoiding the broadcast storm problem and increasing reachability in highly mobile and denser network scenarios. Simulation results show that CMAB provides high delivery ratio, low forwarding ratio and low end-to-end delay in highly mobile and denser network scenarios.

For t >0 and g ≥0, a vertex-weighted graph of total weight W is ( t , g ) -trimmable if it contains a vertex-induced subgraph of total weight at least (1−1/ t ) W and with no simple path of more than g edges. A family of graphs is trimmable if for every constant t >0, there is a constant g ≥0 such that every vertex-weighted graph in the family is ( t , g )-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. We also show that every family of directed graphs of bounded layer bandwidth (a less restrictive condition than bounded directed bandwidth) is trimmable. As an application of these results, we derive polynomial-time approximation schemes for various forms of the problem of labeling a subset of given weighted point features with nonoverlapping sliding axes-parallel rectangular labels so as to maximize the total weight of the labeled features, provided that the ratios of label heights or the ratios of label lengths are bounded by a constant. This settles one of the last major open questions in the theory of map labeling.

For a given number L , an L -length-bounded edge-cut (node-cut, respectively) in a graph G with source s and sink t is a set C of edges (nodes, respectively) such that no s - t -path of length at most L remains in the graph after removing the edges (nodes, respectively) in C . An L -length-bounded flow is a flow that can be decomposed into flow paths of length at most L . In contrast to classical flow theory, we describe instances for which the minimum L -length-bounded edge-cut (node-cut, respectively) is Θ( n 2/3 )-times (Θ(√ n )-times, respectively) larger than the maximum L -length-bounded flow, where n denotes the number of nodes; this is the worst case. We show that the minimum length-bounded cut problem is NP -hard to approximate within a factor of 1.1377 for L ≥ 5 in the case of node-cuts and for L ≥ 4 in the case of edge-cuts. We also describe algorithms with approximation ratio O (min{ L , n/L }) ⊆ O √ n in the node case and O (min { L , n 2 / L 2 ,√ m } ⊆ O 2/3 in the edge case, where m denotes the number of edges. Concerning L -length-bounded flows, we show that in graphs with unit-capacities and general edge lengths it is NP -complete to decide whether there is a fractional length-bounded flow of a given value. We analyze the structure of optimal solutions and present further complexity results.

This paper addresses the problem of exploring the fault tolerance potential of the routing primitive called path splicing. This routing mechanism has been recently introduced in order to improve the reliability level of networks. The idea is to provide for each destination node in a network several different routing trees, called slices, by running different routing protocols simultaneously. The possibility for the traffic to switch between different slices at any hop on the way to the destination makes it possible to achieve a level of reliability that is close to the ideal level achieved by the underlying network. In this work we show that there is a method for computing just two slices that achieves fault tolerance against all single-link failures that do not disconnect the underlying network. We present an experimental evaluation of our approach, showing that for a number of realistic topologies our method of computing the slices achieves the same level of fault tolerance that is achieved by a much larger number of slices using the previously proposed method.

Multicast communication in a wireless ad-hoc network can be established using a tree that spans the multicast sender and receivers as well as other intermediate nodes. If the network is modelled as a graph, the multicast tree is a Steiner tree, the multicast sender and receivers correspond to terminals, and other nodes participating in the tree are Steiner nodes. As Steiner nodes are nodes that participate in the multicast tree by forwarding packets but do not benefit from the multicast, it is a natural objective to compute a tree that minimizes the total cost of the Steiner nodes. We therefore consider the problem of computing, for a given node-weighted graph and a set of terminals, a Steiner tree with Steiner nodes of minimum total weight. For graph classes that admit spanning trees of maximum degree at most d, we obtain a 0.775d-approximation algorithm. We show that this result implies a 3.875-approximation algorithm for unit disk graphs, an O(1/α2)-approximation algorithm for α-unit disk graphs, and an O(λ)-approximation algorithm for (λ + 1)-claw-free graphs.

In the online capacitated interval coloring problem, a sequence of requests arrive online. Each request is an interval $I_j\subseteq\{1,2,\dots,n\}$ with bandwidth $b_j$. We are initially given a vector of capacities $(c_1,c_2,\dots,c_n)$. Each color can support a set of requests such that the total bandwidth of intervals containing i is at most $c_i$. The goal is to color the requests using a minimum number of colors. We present a constant competitive algorithm for the case where the maximum bandwidth $b_{\mathrm{max}}=\max_j b_j$ is at most the minimum capacity $c_{\mathrm{min}}=\min_i c_i$. For the case $b_{\mathrm{max}}>c_{\mathrm{min}}$, we give an algorithm with competitive ratio $O(\log\frac{b_{\mathrm{max}}}{c_{\mathrm{min}}})$ and, using resource augmentation, a constant competitive algorithm. We also give a lower bound showing that a constant competitive ratio cannot be achieved in the general case without resource augmentation.

Consider the problem of discovering (or verifying) the edges and non-edges of a network, modeled as a connected undirected graph, using a minimum number of queries. A query at a vertex v discovers (or verifies) all edges and non-edges whose endpoints have different distance from v. In the network discovery problem, the edges and non-edges are initially unknown, and the algorithm must select the next query based only on the results of previous queries. We study the problem using competitive analysis and give a randomized on-line algorithm with competitive ratio $O(\sqrt{nlogn})$ for graphs with n vertices. We also show that no deterministic algorithm can have competitive ratio better than 3. In the network verification problem, the graph is known in advance and the goal is to compute a minimum number of queries that verify all edges and non-edges. This problem has previously been studied as the problem of placing landmarks in a graph or determining the metric dimension of a graph. We show that there is no approximation algorithm for this problem with ratio o(log n) unless $\mathcal{P} = \mathcal{NP}$ .

A disk graph is the intersection graph of a set of disks with arbitrary diameters in the plane. For the case that the disk representation is given, we present polynomial-time approximation schemes (PTASs) for the maximum weight independent set problem (selecting disjoint disks of maximum total weight) and for the minimum weight vertex cover problem in disk graphs. These are the first known PTASs for $\mathcal{NP}$-hard optimization problems on disk graphs. They are based on a novel recursive subdivision of the plane that allows applying a shifting strategy on different levels simultaneously, so that a dynamic programming approach becomes feasible. The PTASs for disk graphs represent a common generalization of previous results for planar graphs and unit disk graphs. They can be extended to intersection graphs of other "disk-like" geometric objects (such as squares or regular polygons), also in higher dimensions.

A virtual private network (VPN) provides private network connections over a publicly accessible shared network. Bandwidth provisioning for VPNs leads to challenging optimization problems. In the hose model proposed by Duffield et al., each VPN endpoint specifies bounds on the total amount of traffic that it will send or receive at any time. The network provider must provision the VPN so that there is sufficient bandwidth for any traffic matrix that is consistent with these bounds. While previous work has considered tree routing and single-path routing between the VPN endpoints, we demonstrate that the use of multipath routing offers significant advantages. On the one band, we present an optimal polynomial-time algorithm that computes a bandwidth reservation of minimum cost using multi-path routing. This is in contrast to tree routing and single-path routing, where the problem is computationally hard. On the other hand, we present experimental results showing that the reservation cost using multi-path routing can indeed be significantly smaller than with tree or single-path routing.

A common approach for establishing connection requests in an optical ring network that uses wavelength-division multiplexing is to first find a routing of the requests that minimizes the congestion and then deal with the wavelength allocation. The congestion of a routing, however, does not reflect its wavelength requirements. Indeed, we observe that for certain instances such an approach can result in considerable waste of network resources. To overcome this, we propose a new routing objective, namely to minimize the maximum clique of the routing, i.e., the maximum number of connections that pairwise share a common fiber. We present optimal algorithms and heuristics for finding minimum clique routings and perform experiments to evaluate their performance.

Many real-time embedded systems involve a collection of independently executing event-driven code blocks, having hard real-time constraints. Tasks in many such systems, like network processors, are either not preemptable or have restrictions on the number of preemptions allowed. All the previous work on the schedulability analysis of such systems either have exponential complexity, or allow unbounded number of preemptions and are usually based on heuristics. In this paper we present the exact necessary and sufficient conditions under EDF, for the schedulability of such a collection of code blocks in a non-preemptive environment, and give efficient algorithms for testing them. We validate our analytical results with experiments and show that the schedulability analysis problem in such systems can be exactly and efficiently solved in practice.

A bidirected tree is the directed graph obtained from an undirected tree by replacing each undirected edge by two directed edges with opposite directions. Given a set of directed paths in a bidirected tree, the goal of the maximum edge-disjoint paths problem is to select a maximum-cardinality subset of the paths such that the selected paths are edge-disjoint. This problem can be solved optimally in polynomial time for bidirected trees of constant degree but is APX-hard for bidirected trees of arbitrary degree. For every fixed $\varepsilon >0$, a polynomial-time $(5/3+\varepsilon)$-approximation algorithm is presented.