Abstract. We consider the problem of characterizing degree sequences that can be realized by a bipartite graph. If a partition of the sequence into the two sides of the bipartite graph is given as part of the input, then there is a complete characterization that was established more than 60 years ago. However, the general question, in which a partition and a realizing graph need to be determined, is still open. We investigate the role of an important class of special partitions, called High-Low partitions, which separate the degrees of a sequence into two groups, the high degrees and the low degrees. We show that when the High-Low partition exists and satisfies some natural properties, analyzing the High-Low partition resolves the bigraphic realization problem. For sequences that are known to be not realizable by a bipartite graph or that are undecided, we provide approximate realizations based on the High-Low partition.

Necessary and sufficient conditions for a pair of integer sequences to be the degree sequences of the two sides of a bipartite graph were established more than six decades ago by Gale and Ryser. In contrast, the general question of deciding whether a single sequence is bigraphic, namely, can be realized by a bipartite graph, is still open. We consider even sequences, in which the multiplicity of any integer in the degree sequence is even. One can always partition an even sequence into two identical sequences, resulting in an equal partition. We show that if a given even sequence d is graphic, then there are only two options: either d is bigraphic, or d is 2-bigraphic, namely, can be realized by a bipartite multigraph with maximum multiplicity 2. For an r -graphic sequence we show that it is t -bigraphic for some t ≤ 2 r , and we also show that the analysis is tight, namely that t = 2 r is possible. In addition, we show that given an r -graphic sequence d , there exists an even sequence d ′ which is similar to d in a well-defined sense such that d ′ is even and r -graphic, and therefore t -bigraphic for some t ≤ 2 r .

A sequence d = (d_1,d_2, …, d_n) of positive integers is graphic if it is the degree sequence of some simple graph G, and planaric if it is the degree sequence of some simple planar graph G. It is known that if ∑ d ≤ 2n - 2, then d has a realization by a forest, hence it is trivially planaric. In this paper, we seek bounds on ∑ d that guarantee that if d is graphic then it is also planaric. We show that this holds true when ∑ d ≤ 4n-4-2ω₁, where ω₁ is the number of 1’s in d. Conversely, we show that there are graphic sequences with ∑ d = 4n-2ω₁ that are non-planaric. For the case ω₁ = 0, we show that d is planaric when ∑ d ≤ 4n-4. Conversely, we show that there is a graphic sequence with ∑ d = 4n-2 that is non-planaric. In fact, when ∑ d ≤ 4n-6-2ω₁, d can be realized by a graph with a 2-page book embedding.

Abstract We study the Online Multiset Submodular Cover problem (OMSC), where we are given a universe U of elements and a collection of subsets $$\mathcal {S}\subseteq 2^U$$ S ⊆ 2 U . Each element $$u_j \in U$$ u j ∈ U is associated with a nonnegative, nondecreasing, submodular polynomially computable set function $$f_j$$ f j . Initially, the elements are uncovered, and therefore we pay a penalty per each unit of uncovered element. Subsets with various coverage and cost arrive online. Upon arrival of a new subset, the online algorithm must decide how many copies of the arriving subset to add to the solution. This decision is irrevocable, in the sense that the algorithm will not be able to add more copies of this subset in the future. On the other hand, the algorithm can drop copies of a subset, but such copies cannot be retrieved later. The goal is to minimize the total cost of subsets taken plus penalties for uncovered elements. We present an $$O(\sqrt{\rho _{\max }})$$ O ( ρ max ) -competitive algorithm for OMSC that does not dismiss subset copies that were taken into the solution, but relies on prior knowledge of the value of $$\rho _{\max }$$ ρ max , where $$\rho _{\max }$$ ρ max is the maximum ratio, over all subsets, between the penalties covered by a subset and its cost. We provide an $$O\left( \log (\rho _{\max }) \sqrt{\rho _{\max }} \right) $$ O log ( ρ max ) ρ max -competitive algorithm for OMSC that does not rely on advance knowledge of $$\rho _{\max }$$ ρ max but uses dismissals of previously taken subsets. Finally, for the capacitated versions of the Online Multiset Multicover problem, we obtain an $$O(\sqrt{\rho _{\max }'})$$ O ( ρ max ′ ) -competitive algorithm when $$\rho _{\max }'$$ ρ max ′ is known and an $$O\left( \log (\rho _{\max }') \sqrt{\rho _{\max }'} \right) $$ O log ( ρ max ′ ) ρ max ′ -competitive algorithm when $$\rho _{\max }'$$ ρ max ′ is unknown, where $$\rho _{\max }'$$ ρ max ′ is the maximum ratio over all subset incarnations between the penalties covered by this incarnation and its cost.

Containers technology has become very popular in recent years, since it allows users to focus on designing their applications in a modular way and abstracting away the environments in which they actually run. Cloud providers such as AWS (Amazon Web Services) and GCP (Google Cloud Platform) offer their users managed containers platforms that orchestrate, schedule and execute multiple containers over a multi-tenant cloud infrastructure. As these services gain popularity, it is becoming more and more challenging to manage them in a way that effectively utilized the existing resources. The latter has a significant economical impact on cloud providers when it comes to their compute infrastructure investment costs and the price they can offer to their customers. In this paper, we approach this challenge by developing multidimensional container resource allocation algorithms designed to be deployed in dynamic cloud environments with different types of applications under varying loads scenarios. Our algorithms allocate for each container an available engine to execute it, in a way that maximizes the overall revenue. We design our algorithms and provide a constant worst-case approximation bound using the Local Ratio technique. Our evaluation, based on real-world scenarios, indicates that the performance of our algorithms is up to a factor of two better than the performance of existing scheduling algorithms, when the available resources are scarce.

The classical degree realization problem is defined as follows: Given a sequence d̄ = (d_1,…,d_n) of positive integers, construct an n-vertex graph in which each vertex u_i has degree d_i (or decide that no such graph exists). In this article, we present and study the related selected neighbor degree realization problem, which requires that each vertex u_i of G has a neighbor of degree d_i. We solve the problem when G is required to be acyclic (i.e., a forest), and present a sufficient and necessary condition for a given sequence to be realizable.

We consider the problem of realizable interval sequences. An interval sequence is comprised of $n$ integer intervals $[a_i,b_i]$ such that $0\le a_i\leq b_i \le n-1$ and is said to be graphic/realizable if there exists a graph with degree sequence, say, $D=(d_1,\ldots,d_n),$ satisfying the condition $a_i\leq d_i\leq b_i$ for each $i\in[1,n]$. There is a characterization (also implying an $O(n)$ verifying algorithm) known for realizability of interval sequences, which is a generalization of the Erdös--Gallai characterization for graphic sequences. However, given any realizable interval sequence, there is no known algorithm for computing a corresponding graphic certificate in $o(n^2)$ time. In this paper, we provide an $O(n \log n)$ time algorithm for computing a graphic sequence for any realizable interval sequence. In addition, when the interval sequence is nonrealizable, we show how to find a graphic sequence having minimum deviation with respect to the given interval sequence in the same time. Finally, we consider variants of the problem, such as computing the most-regular graphic sequence and computing a minimum extension of a length $p$ nongraphic sequence to a graphic one.

This paper presents and studies a generalization of the microscopic image reconstruction problem (MIR) introduced by Frosini and Nivat [Andrea Frosini and Maurice Nivat, 2007; Nivat, 2002]. Consider a specimen for inspection, represented as a collection of points typically organized on a grid in the plane. Assume each point x has an associated physical value l_x, which we would like to determine. However, it might be that obtaining these values precisely (by a surgical probe) is difficult, risky, or impossible. The alternative is to employ aggregate measuring techniques (such as EM, CT, US or MRI), whereby each measurement is taken over a larger window, and the exact values at each point are subsequently extracted by computational methods. In this paper we extend the MIR framework in a number of ways. First, we consider a generalized setting where the inspected object is represented by an arbitrary graph G, and the vector l in R^n assigns a value l_v to each node v. A probe centered at a vertex v will capture a window encompassing its entire neighborhood N[v], i.e., the outcome of a probe centered at v is P_v = sum_{w in N[v]} l_w. We give a criterion for the graphs for which the extended MIR problem can be solved by extracting the vector l from the collection of probes, P^- = {P_v | v in V}. We then consider cases where such reconstruction is impossible (namely, graphs G for which the probe vector P is inconclusive, in the sense that there may be more than one vector l yielding P). Let us assume that surgical probes (whose outcome at vertex v is the exact value of l_v) are technically available to us (yet are expensive or risky, and must be used sparingly). We show that in such cases, it may still be possible to achieve reconstruction based on a combination of a collection of standard probes together with a suitable set of surgical probes. We aim at identifying the minimum number of surgical probes necessary for a unique reconstruction, depending on the graph topology. This is referred to as the Minimum Surgical Probing problem (MSP). Besides providing a solution for the above problems for arbitrary graphs, we also explore the range of possible behaviors of the Minimum Surgical Probing problem by determining the number of surgical probes necessary in certain specific graph families, such as perfect k-ary trees, paths, cycles, grids, tori and tubes.

We bound the performance guarantees that follow from Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, a randomized approach of Boppana forms a simple 1-round distributed algorithm, as well as a streaming and preemptive online algorithm. We show it gives a tight (Δ+1)/2-approximation in unweighted graphs of maximum degree Δ, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a (Δ+1)-approximation, but a simple modification results in an asymptotic expected 0.529(Δ+1)-approximation.

We present a new extension of the generalized caching/paging problem that allows the adversary to arbitrarily change the cost or weight of the currently requested page. We present modifications of previous algorithms for generalized caching to handle varying page weights and page costs. In particular, a deterministic algorithm based on~\citeYoung02,CaoIrani97 for an $(h,k)$-competitive algorithm with competitive ratio $k/(k-h+1)$ is presented. In addition, a randomized algorithm based on~\citeBansalBN12,AdamaszekCER12 with competitive ratio $O(łog k)$ is presented. We present three applications that can be supported via reductions to generalized caching with varying page weights and page costs. These applications are: (1)~support of subsets of pages that must be simultaneously present in the cache before entry to a critical section (i.e., working sets), (2)~change of page size due to compression and decompression, (3)~variable cache size (i.e., elastic caches).

The dynamic content distribution problem addresses the trade-off between storage and delivery costs in modern virtual content delivery networks (CDNs). That is, a video file can be stored in multiple places so that the request of each user is served from a location that is near the user. This minimizes the delivery costs, but is associated with a storage cost. This problem is NP-hard even in grid networks. In this paper, we present a constant factor approximation algorithm for grid networks. We also present an $O(\log \delta)$-competitive algorithm, where $\delta$ is the normalized diameter of the network, for general networks with general metrics. We show a matching lower bound by using a reduction from online undirected Steiner tree. Our algorithms use a rather intuitive approach that has an elegant representation in geometric terms.

The Maximum Carpool Matching problem is a star packing problem in directed graphs. Formally, given a directed graph G = (V, A), a capacity function c: V -> N, and a weight function w: A -> R^+, a carpool matching is a subset of arcs, M subseteq A, such that every v in V satisfies: (i) d^{in}_M(v) cdot d^{out}_M(v) = 0, (ii) d^{in}_M(v) <= c(v), and (iii) d^{out}_M(v) <= 1. A vertex v for which d^{out}_M(v) = 1 is a passenger, and a vertex for which d^{out}_M(v) = 0 is a driver who has d^{in}_M(v) passengers. In the Maximum Carpool Matching problem the goal is to find a carpool matching M of maximum total weight. The problem arises when designing an online carpool service, such as Zimride, which tries to connect between users based on a similarity function. The problem is known to be NP-hard, even in the unweighted and uncapacitated case. The Maximum Group Carpool Matching problem, is an extension of Maximum Carpool Matching where each vertex represents an unsplittable group of passengers. Formally, each vertex u in V has a size s(u) in N, and the constraint d^{in}_M(v) <= c(v) is replaced with sum_{u:(u,v) in M} s(u) <= c(v). We show that Maximum Carpool Matching can be formulated as an unconstrained submodular maximization problem, thus it admits a 1/2-approximation algorithm. We show that the same formulation does not work for Maximum Group Carpool Matching, nevertheless, we present a local search (1/2 - epsilon)-approximation algorithm for Maximum Group Carpool Matching. For the unweighted variant of both problems when the maximum possible capacity, c_{max}, is bounded by a constant, we provide a local search (1/2 + 1/{2c_{max}} - epsilon)-approximation algorithm. We also show that the problem is APX-hard, even if the maximum degree and c_{max} are at most 3.

Sensor networks are ubiquitously used for detection and tracking and, as a result, covering is one of the main tasks of such networks. We study the problem of maximizing the coverage lifetime of a barrier by mobile sensors with limited battery power, where the coverage lifetime is the time until there is a breakdown in coverage due to the death of a sensor. Sensors are first deployed and then coverage commences. Energy is consumed in proportion to the distance traveled for mobility, while for coverage, energy is consumed in direct proportion to the radius of the sensor raised to a constant exponent. We study two variants which are distinguished by whether the sensing radii are given as part of the input or can be optimized: the fixed radii problem and the variable radii problem. We design parametric search algorithms for both problems for the case where the final order of the sensors is predetermined (e.g., sensors cannot swap locations and the initial order must be preserved) and for the case where sensors are initially located at barrier endpoints. In contrast, we show that the variable radii problem is strongly NP-hard and provide hardness of approximation results for fixed radii for the case where all the sensors are initially colocated at an internal point of the barrier.

We study the Online Budgeted Maximum Coverage (OBMC) problem. Subsets of a weighted ground set U arrive one by one, where each set has a cost. The online algorithm has to select a collection of sets, under the constraint that their cost is at most a given budget. Upon arrival of a set the algorithm must decide whether to accept or to reject the arriving set, and it may also drop previously accepted sets (preemption). Rejecting or dropping a set is irrevocable. The goal is to maximize the total weight of the elements covered by the sets in the chosen collection. We present a deterministic 4/(1-r)-competitive algorithm for OBMC, where r is the maximum ratio between the cost of a set and the total budget. Building on that algorithm, we then present a randomized O(1)-competitive algorithm for OBMC. On the other hand, we show that the competitive ratio of any deterministic online algorithm is Omega(1/(sqrt{1-r})). We also give a deterministic O(Delta)-competitive algorithm, where Delta is the maximum weight of a set (given that the minimum element weight is 1), and if the total weight of all elements, w(U), is known in advance, we show that a slight modification of that algorithm is O(min{Delta,sqrt{w(U)}})-competitive. A matching lower bound of Omega(min{Delta,sqrt{w(U)}}) is also given. Previous to the present work, only the unit cost version of OBMC was studied under the online setting, giving a 4-competitive algorithm [Saha, Getoor, 2009]. Finally, our results, including the lower bounds, apply to Removable Online Knapsack which is the preemptive version of the Online Knapsack problem.

An important problem in the study of sensor networks is how to select a set of sensors that maximizes coverage of other sensors. Given pair wise coverage values, three commonly found functions give some estimate of the aggregate coverage possible by a set of sensors: maximum coverage by any selected sensor (MAX), total coverage by all selected sensors (SUM), and the probability of correct prediction by at least one sensor (PROB). MAX and SUM are two extremes of possible coverage, while PROB, based on an independence assumption, is in the middle. This paper addresses the following question: what guarantees can be made of coverage that is evaluated by an unknown sub-modular function of coverage when sensors are selected according to MAX, SUM, or PROB? We prove that the guarantees are very bad: In the worst case, coverage differs by a factor of sqrt(n), where n is the number of sensors. We show in simulations on synthetic and real data that the differences can be quite high as well. We show how to potentially address this problem using a hybrid of the coverage functions.

We consider the k-Service Assignment problem (k-SA), defined as follows. The input consists of a network that contains servers and clients, and an integer k. Each server has a finite capacity, and each client is associated with a demand and a profit. A feasible solution is an assignment of clients to neighboring servers such that (i) the total demand assigned to a server is at most its capacity, and (ii) a client is assigned either to k servers or to none. The profit of an assignment is the total profit of clients that are assigned to k servers, and the goal is to find a maximum profit assignment. In the r-restricted version of k-SA, no client requires more than an r-fraction of the capacity of any adjacent server. The k-SA problem is motivated by backup placement in networks and by resource allocation in 4G cellular networks. It can also be viewed as machine scheduling on related machines with assignment restrictions. We present a centralized polynomial time greedy (k+1-r)/(1-r)-approximation algorithm for r-restricted k-SA. We then show that a variant of this algorithm achieves an approximation ratio of k+1 using a resource augmentation factor of 1+r. We use the latter to present a (k+1)^2-approximation algorithm for k-SA. In the distributed setting, we present: (i) a (1+epsilon)*(k +1-r)/(1-r)-approximation algorithm for r-restricted k-SA, (ii) a (1+epsilon)(k+1)-approximation algorithm that uses a resource augmentation factor of 1+r for r-restricted k-SA, both for any constant epsilon>0, and (iii) an O{k^2}-approximation algorithm for k-SA (in expectation). The three distributed algorithms compute a solution with high probability and terminate in O(k^2 *log^3(n)) rounds.

We consider the backup placement problem, defined as follows. Some nodes (processors) in a given network have objects (e.g., files, tasks) whose backups should be stored in additional nodes for increased fault resilience. To minimize the disturbance in case of a failure, it is required that a backup copy should be located at a neighbor of the primary node. The goal is to find an assignment of backup copies to nodes which minimizes the maximum load (number or total size of copies) over all nodes in the network. It is known that a natural selfish local improvement policy has approximation ratio Ω(log n / log log n); we show that it may take this policy Ω(√n) time to reach equilibrium in the distributed setting. Our main result in this paper is a distributed algorithm which finds a placement in polylogarithmic time and achieves approximation ratio O(log n/log log n). We obtain this result using a distributed approximation algorithm for f-matching in bipartite graphs that may be of independent interest.

Time-varying graphs (T-graph) consist of a time-evolving set of graph snapshots (or graphlets). A T-graph property with potential applications in both computer and social network forensics is T-reachability, which identifies the nodes reachable from a source node using the T-graph edges over time period T. In this paper, we consider the problem of estimating the T-reachable set of a source node in two different settings - when a time-evolution of a T-graph is specified by a probabilistic model, and when the actual T-graph snapshots are known and given to us offline (“data aware” setting). Since the value of T could be large in many applications, we propose two simple techniques, namely T-graph sampling and T-graph smashing for significantly reducing the complexity of this computation, while minimizing the estimation error. We show that for the data-aware case, both T-graph sampling and smashing problems are NP-hard, but they are amenable to reasonably good approximations. We also show that for the probabilistic setting where each graphlet in a T-graph is an Erdos-Renyi random graph, sampling yields a loose lower bound for the T-reachable set, while different styles of smashing yield more useful upper and lower bounds. Finally, we show that our algorithms (both data-aware and data-oblivious) can estimate the T-reachable set in real world time-varying networks within reasonable accuracy using less than 0.5% of the number of graphlets.

In social swarming applications, participants equipped with 3G and WiFi-capable smartphones are tasked to provide reports (possibly voluminous ones that include full-motion video) about their immediate environment to a central coordinator. In this paper, we consider the problem of timely delivery of these reports: Each report has an associated deadline, and the goal of the system is to retrieve as many reports as possible (or retrieve the most valuable reports), while satisfying each report's deadline. Reporters can use their cellular interface to upload their reports but can also ask neighbors (using their faster WiFi interface) to help upload parts of their reports. Under an assumption that WiFi transmission delays are negligible, we first show that there exists a polynomial time optimal solution using an earliest-deadline-first (EDF) strategy for achieving the goals described above. In practice, WiFi delays are not negligible; in this case, it turns out that the scheduling problem is strongly NP-hard. We formulate two heuristic algorithms, and show, through simulations and experiments on an Android-based implementation, that these heuristics perform 2-4× better than without peer-assistance, and within 60% of an upper-bound on the optimal.

In the Set Once Strip Cover problem n wireless sensors are deployed over a one-dimensional region. Each sensor has a battery that drains in inverse proportion to a radius that can be set just once, but activated at any time. The problem is to find an assignment of radii and activation times that maximizes the length of time during which the entire region is covered. We show that this problem is NP-hard. We also show that the approximation ratio of Round Robin, the algorithm in which the sensors take turns covering the entire region, is 3/2 in both Set Once Strip Cover and the more general Strip Cover problem, in which each radius may be set finitely-many times. Moreover, we show that the more general class of duty cycle algorithms, in which groups of sensors take turns covering the entire region, can do no better. Finally, we give an polynomial time algorithm that solves the related Set Radius Strip Cover problem, in which sensors must be activated immediately.

We study the Storage Allocation Problem (SAP) which is a variant of the Unsplittable Flow Problem on Paths (UFPP). A SAP instance consists of a path P = (V,E) and a set J of tasks. Each edge e ∈ E has a capacity ce and each task j ∈ J is associated with a path Ij in P, a demand dj and a weight wj. The goal is to find a maximum weight subset S ⊆ J of tasks and a height function h:S → ℜ+ such that (i) h(j)|+dj ≤ ce, for every e ∈ Ij; and (ii) if j,i ∈ S such that Ij ∩ Ii ≠ ∅ and h(j) ≥ h(i), then h(j) ≥ h(i) + di. SAP can be seen as a rectangle packing problem in which rectangles can be moved vertically, but not horizontally.

In social swarming applications, participants equipped with 3G and WiFi-capable smart phones are tasked to provide reports (possibly voluminous ones that include full-motion video) about their immediate environment to a central coordinator. In this paper, we consider the problem of timely delivery of these reports: each report has an associated deadline and the goal of the system is to retrieve as many reports as possible (or retrieve the most valuable reports), while satisfying each report's deadline. Reporters can use their cellular interface to upload their reports, but can also ask neighbors (using their faster WiFi interface) to help upload parts of their reports. Under an assumption that WiFi transmission delays are negligible, we first show that there exists a polynomial time optimal solution using an earliest-deadline-first (EDF) strategy for achieving the goals described above. In practice, WiFi delays are not negligible: in this case, it turns out that the scheduling problem is strongly NP-hard. We formulate two heuristic algorithms, and show, through simulations with real-world measurements, that these heuristics perform 2-4× better than without peer-assistance, and within 60% of an upper-bound on the optimal.

As sensor mobility becomes more and more universal, Wireless Sensor Network (WSN) configurations that utilize such mobility will become the norm. We consider the problem of maximizing the lifetime of a wireless connection between a transmitter and a receiver using mobile relays. Initially, all relays are positioned arbitrarily on the line between the transmitter and the receiver and have arbitrary battery capacities. Energy is consumed in proportion to the distance traveled for mobility and in proportion to an exponential function of the distance over which information is sent for communication. Relays can move to different locations as long as they have the energy to do so. The objective is to find positions and thus transmission ranges for the nodes that maximize the lifetime of the network. We study two models. The first is more restrictive, and corresponds to the case where relays are allowed to be set once at time zero (single deployment), while the second model corresponds to the case where relays can be adjusted multiple times (multiple deployments). We show how to compute an optimal solution for the case of no movement cost for both models. We consider a discrete version of the single deployment model, in which relays must be deployed on grid points. We provide two algorithms for this case: a dynamic programming algorithm and a binary search algorithm on potential lifetimes. We prove that both algorithms are FPTASs for the non-discrete problem, if batteries are not too small. Based on these algorithms and on additional ideas we develop a number of heuristics for the multiple deployments model. We evaluate them using simulations and compare them with the lower bound of relays not moving at all and the upper bound of cost-free movement. Our simulations - across a range of mobility and transmission costs, sensible starting locations and battery capacities - demonstrate the benefit of moving over remaining at initial locations even for single deployment.

In online set packing (OSP), elements arrive online, announcing which sets they belong to, and the algorithm needs to assign each element, upon arrival, to one of its sets. The goal is to maximize the number of sets that are assigned all their elements: a set that misses even a single element is deemed worthless. This is a natural online optimization problem that abstracts allocation of scarce compound resources, e.g., multipacket data frames in communication networks. We present a randomized competitive online algorithm for the weighted case with general capacity (namely, where sets may have different values, and elements arrive with different multiplicities). We prove a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximum set size and the maximum number of sets an element belongs to. We also present refined bounds that depend on the uniformity of these parameters.

In the multislope ski rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost (“buying price”) and cost proportional to the duration of the usage (“rental rate”). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best alternative at any point in time. Multislope ski rental is a natural generalization of the classical ski rental problem (where there are only two available alternatives, namely pure rent and pure buy), which is one of the fundamental problems of online computation. The multislope ski rental problem is an abstraction of many problems, where online choices cannot be modeled by just two alternatives, e.g., power management in systems which can be shut down in parts. In this paper we study randomized algorithms for multislope ski rental. Our results include an algorithm that produces the best possible online randomized strategy for any additive instance, where the cost of switching from one alternative to another is the difference in their buying prices, and an e-competitive randomized strategy for any (not necessarily additive) instance.

With the advent of smartphone technology, it has become possible to conceive of entirely new classes of applications. Social swarming, in which users armed with smartphones are directed by a central director to report on events in the physical world, has several real-world applications: search and rescue, coordinated fire-fighting, and the DARPA balloon hunt challenge. In this paper, we focus on the following problem: how does the director optimize the selection of reporters to deliver credible corroborating information about an event. We first propose a model, based on common notions of believability, about the credibility of information. We then cast the problem posed above as a discrete optimization problem, prove hardness results, introduce optimal centralized solutions, and design an approximate solution amenable to decentralized implementation whose performance is about 20 percent off, on average, from the optimal (on real-world data sets derived from Google News) while being three orders of magnitude more computationally efficient. More interesting, a time-averaged version of the problem is amenable to a novel stochastic utility optimization formulation, and can be solved optimally, while in some cases yielding decentralized solutions. To our knowledge, we are the first to propose and explore the problem of extracting credible information from a network of smartphones.

We study an abstract setting, where the basic information units (called “superpackets”) do not fit into a single packet, and are therefore spread over multiple packets. We assume that a superpacket is useful only if the number of its delivered packets is above a certain threshold. Our focus of attention is communication link ingresses, where large arrival bursts result in dropped packets. The algorithmic question we address is which packets to drop so as to maximize goodput. Specifically, suppose that each superpacket consists of k packets, and that a superpacket can be reconstructed if at most β · k of its packets are lost, for some given parameter 0 ≤ β; 0. Finally, we present some simulation results that demonstrate that the behavior of our algorithm in practice is far better than our worst-case analytical bounds.

In the problem of Scheduling with Interval Conflicts, there is a ground set of items indexed by integers, and the input is a collection of conflicts, each containing all the items whose index lies within some interval on the real line. Conflicts arrive in an online fashion. A scheduling algorithm must select, from each conflict, at most one survivor item, and the goal is to maximize the number (or weight) of items that survive all the conflicts they are involved in. We present a centralized deterministic online algorithm whose competitive ratio is O(log sigma), where sigma is the size of the largest conflict. For the distributed setting, we present another deterministic algorithm whose competitive ratio is 2 log sigma, in the special contiguous case, in which the item indices constitute a contiguous interval of integers. Our upper bounds are complemented by two lower bounds: one that shows that even in the contiguous case, all deterministic algorithms (centralized or distributed) have competitive ratio Omega(log sigma), and that in the non-contiguous case, no deterministic oblivious algorithm (i.e., a distributed algorithm that does not use communication) can have a bounded competitive ratio.

We consider a scenario where large data frames are broken into a few packets and transmitted over the network. Our focus is on a bottleneck router: the model assumes that in each time step, a set of packets (a burst) arrives, from which only one packet can be served, and all other packets are lost. A data frame is considered useful only if none of its constituent packets is lost, and otherwise it is worthless. We abstract the problem as a new type of online set packing, present a randomized distributed algorithm and a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximal burst size and the maximal number of packets per frame. We also present refined bounds that depend on the uniformity of these parameters.

We study the partial capacitated vertex cover problem (PCVC) in which the input consists of a graph G and a covering requirement L. Each edge e in G is associated with a demand (or load) $\ell(e)$, and each vertex v is associated with a (soft) capacity $c(v)$ and a weight $w(v)$. A feasible solution is an assignment of edges to vertices such that the total demand of assigned edges is at least L. The weight of a solution is $\sum_{v}\alpha(v)w(v)$, where $\alpha(v)$ is the number of copies of v required to cover the demand of the edges that are assigned to v. The goal is to find a solution of minimum weight. We consider three variants of PCVC. In PCVC with separable demands the only requirement is that the total demand of edges assigned to v is at most $\alpha(v)c(v)$. In PCVC with inseparable demands there is an additional requirement that if an edge is assigned to v, then it must be assigned to one of its copies. The third variant is the unit demands version. We present 3-approximation algorithms for both PCVC with separable demands and PCVC with inseparable demands. We also present a 2-approximation algorithm for PCVC with unit demands. We show that similar results can be obtained for PCVC in hypergraphs and for the prize collecting version of capacitated vertex cover. Our algorithms are based on a unified approach for designing and analyzing approximation algorithms for capacitated covering problems. This approach yields simple algorithms whose analyses rely on the local ratio technique and sophisticated charging schemes.

The Nemhauser–Trotter theorem provides an algorithm which is frequently used as a subroutine in approximation algorithms for the classical Vertex Cover problem. In this paper we present an extension of this theorem so it fits a more general variant of Vertex Cover, namely, the Generalized Vertex Cover problem, where edges are allowed not to be covered at a certain predetermined penalty. We show that many applications of the original Nemhauser–Trotter theorem can be applied using our extension to Generalized Vertex Cover. These applications include a $(2-2/d)$-approximation algorithm for graphs of bounded degree d, a polynomial-time approximation scheme (PTAS) for planar graphs, a $(2-\lg\lg n/2\lg n)$-approximation algorithm for general graphs, and a $2k$ kernel for the parameterized Generalized Vertex Cover problem.

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more then one interval associated with it. We initiate the study of optimization problems in multiple-interval graphs by considering three classical problems: Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique. We describe applications for each one of these problems, and then proceed to discuss approximation algorithms for them. Our results can be summarized as follows: Let t be the number of intervals associated with each vertex in a given multiple-interval graph. For Minimum Vertex Cover, we give a (2−1/ t )-approximation algorithm which also works when a t -interval representation of our given graph is absent. Following this, we give a t 2 -approximation algorithm for Minimum Dominating Set which adapts well to more general variants of the problem. We then proceed to prove that Maximum Clique is NP -hard already for 3-interval graphs, and provide a ( t 2 − t +1)/2-approximation algorithm for general values of t ≥ 2, using bounds proven for the so-called transversal number of t -interval families.

Many network applications that need to distribute content and data to a large number of clients use a hybrid scheme in which one (or more) multicast channel is used in parallel to a unicast dissemination. This way the application can distribute data using one of its available multicast channels or by sending one or more unicast transmissions. In such a model the utilization of the multicast channels is critical for the overall performance of the system. We study the scheduling algorithm of the sender in such a model. We describe this scheduling problem as an optimization problem where the objective is to maximize the utilization of the multicast channel. Our model captures the fact that it may be beneficial to multicast an object more than once (e.g., page update). Thus, the benefit depends, among other things, on the last time the object was sent, which makes the problem much more complex than previous related scheduling problems. We show that our problem is NP-hard. Then, using the local ratio technique we obtain a 4-approximation algorithm for the case where the objects are of fixed size and a 10-approximation algorithm for the general case. We also consider a special case which may be of practical interest, and prove that a simple greedy algorithm is a 3-approximation algorithm in this case.

We consider the optimization problem of providing a set of video streams to a set of clients, where each stream has costs in m possible measures (such as communication bandwidth, processing bandwidth etc.), and each client has its own utility function for each stream. We assume that the server has a budget cap on each of the m cost measures; each client has an upper bound on the utility that can be derived from it, and potentially also upper bounds in each of the m cost measures. The task is to choose which streams the server will provide, and out of this set, which streams each client will receive. The goal is to maximize the overall utility subject to the budget constraints. We give an efficient approximation algorithm with approximation factor of O(m) with respect to the optimal possible utility for any input, assuming that clients have only a bound on their maximal utility. If, in addition, each client has at most mc capacity constraints, then the approximation factor increases by another factor of O(mclog n), where n is the input length. We also consider the special case of "small" streams, namely where each stream has cost of at most O(1/ log n) fraction of the budget cap, in each measure. For this case we present an algorithm whose approximation ratio is O(log n).

In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost (``buying price''), and cost proportional to the duration of the usage (``rental rate''). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best option at any point in time. Multislope Ski Rental is a natural generalization of the classical Ski Rental problem (where the only options are pure rent and pure buy), which is one of the fundamental problems of online computation. The Multislope Ski Rental problem is an abstraction of many problems where online decisions cannot be modeled by just two options, e.g., power management in systems which can be shut down in parts. In this paper we study randomized algorithms for Multislope Ski Rental. Our results include the best possible online randomized strategy for any additive instance, where the cost of switching from one option to another is the difference in their buying prices; and an algorithm that produces an $e$-competitive randomized strategy for any (non-additive) instance.

In the rectangle stabbing problem, we are given a set of axis parallel rectangles and a set of horizontal and vertical lines, and our goal is to find a minimum size subset of lines that intersect all the rectangles. In this article, we study the capacitated version of this problem in which the input includes an integral capacity for each line. The capacity of a line bounds the number of rectangles that the line can cover. We consider two versions of this problem. In the first, one is allowed to use only a single copy of each line ( hard capacities ), and in the second, one is allowed to use multiple copies of every line, but the multiplicities are counted in the size (or weight) of the solution ( soft capacities ). We present an exact polynomial-time algorithm for the weighted one dimensional case with hard capacities that can be extended to the one dimensional weighted case with soft capacities. This algorithm is also extended to solve a certain capacitated multi-item lot-sizing inventory problem with joint set-up costs. For the case of d -dimensional rectangle stabbing with soft capacities, we present a 3 d -approximation algorithm for the unweighted case. For d -dimensional rectangle stabbing problem with hard capacities, we present a bi-criteria algorithm that computes 4 d -approximate solutions that use at most two copies of every line. Finally, we present hardness results for rectangle stabbing when the dimension is part of the input and for a two-dimensional weighted version with hard capacities.

We discuss two approximation paradigms that were used to construct many approximation algorithms during the last two decades, the primal-dual schema and the local ratio technique. Recently, primal-dual algorithms were devised by first constructing a local ratio algorithm and then transforming it into a primal-dual algorithm. This was done in the case of the 2-approximation algorithms for the feedback vertex set problem and in the case of the first primal-dual algorithms for maximization problems. Subsequently, the nature of the connection between the two paradigms was posed as an open question by Williamson [Math. Program., 91 (2002), pp. 447--478]. In this paper we answer this question by showing that the two paradigms are equivalent.

The growing gap between the speed of memory access and cache access has made cache misses an influential factor in program efficiency. Much effort has been spent recently on reducing the number of cache misses during program run. This effort includes wise rearranging of program code, cache-conscious data placement, and algorithmic modifications that improve the program cache behavior. In this work we investigate the complexity of finding the optimal placement of objects (or code) in the memory, in the sense that this placement reduces the cache misses to the minimum. We show that this problem is one of the toughest amongst the interesting algorithmic problems in computer science. In particular, suppose one is given a sequence of memory accesses and one has to place the data in the memory so as to minimize the number of cache misses for this sequence. We show that if P ≠ NP, then one cannot efficiently approximate the optimal solution even up to a very liberal approximation ratio. Thus, this problem joins the small family of extremely inapproximable optimization problems. The other two famous members in this family are minimum coloring and maximum clique.