The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
In this article, we study algorithms for online routing and machine scheduling problems. The problems are “online” because the problem instances are revealed incrementally. We first study algorithms for the online Traveling Repairman Problem (TRP), where a single server is to visit a set of locations in a network with the objective of minimizing the sum of weighted completion times. We then analyze...
Routing problems, which include a QoS‐based path control, play a key role in broadband communication networks. We analyze here an algorithmic procedure based on branch‐and‐price algorithm and on the flow deviation method to solve a nonlinear k‐splittable flow problem. The model can support end‐to‐end delay bounds on each path and we compare the behavior of the algorithm with and without these constraints...
In this article, we consider the k‐edge connected subgraph problem from a polyhedral point of view. We introduce further classes of valid inequalities for the associated polytope and describe sufficient conditions for these inequalities to be facet defining. We also devise separation routines for these inequalities and discuss some reduction operations that can be used in a preprocessing phase for...
In the Traveling Salesman Problem with Pickup and Delivery (TSPPD) a single vehicle must serve a set of customer requests, each defined by an origin location where a load must be picked up, and a destination location where the load must be delivered. The problem consists of determining a shortest Hamiltonian cycle through all locations while ensuring that the pickup of each request is performed before...
This article presents a fast algorithm for a class of parametric assignment problems. Moreover, it is shown how this algorithm can be applied to a problem arising in the so‐called max‐algebra which results as an analogue of classical linear algebra by replacing the classical addition and multiplication by a ⊕ b = max(a,b) and a ⊗ b = a + b, respectively. An instance of the linear parametric assignment...
Reliable communication has become crucial in today's information society. Modern communication networks are required to deliver reliable communication to their customers. Unfortunately, protection against network failures significantly hampers efficient utilization of network investments, because the associated routing problems become much harder. In this article we present a rigorous mathematical...
An edge set S is a k‐restricted edge cut of a connected graph G if G‐S is no longer connected and every component of G‐S has at least k vertices. The k‐restricted edge connectivity of G, denoted by λk(G), is the cardinality of a minimum k‐restricted edge cut. A graph G with λk(G) = ξk(G) is called λk‐optimal, where ξk(G) = min{∣U,Ū∣ ∣ U ⊂ V(G),∣U∣ = k and GU is connected}, ∣U,Ū∣ is the number of edges...
We consider combinatorial optimization problems arising in radiation therapy. Given a matrix I with non‐negative integer entries, we seek a decomposition of I as a weighted sum of binary matrices having the consecutive ones property, such that the total sum of the coefficients is minimized. The coefficients are restricted to be non‐negative integers. Here, we investigate variants of the problem with...
In this article we consider a class of Cayley graphs that are generated by certain 3‐cycles on the alternating group An. These graphs are generalizations of the alternating group graph AGn. We look at the case when the 3‐cycles form a “tree‐like structure,” and analyze its fault resiliency. We present a number of structural theorems and prove that even with linearly many vertices deleted, the remaining...
We consider a metric uncapacitated facility location problem where we must assign each customer to a facility and meet the demand of the customer in future time periods through production and inventory decisions at the facility. We show that the problem, in general, is as hard to approximate as the set cover problem. We therefore focus on developing approximation algorithms for special cases of the...
In this article we prove 𝒩𝒫‐hardness of two well‐known optimization problems related to the design of multicommodity flow networks with two different methods for providing network resiliency against failures: path diversity and flow restoration. Path diversity is a static mechanism that consists of using, for each demand, a number of paths and oversizing the flows assigned to these paths so that...
We study the β‐reliable minimax and maximin location problems on a network when the weights associated with the nodal points are random variables. In the β‐reliable minimax (maximin) problem, we locate a single facility so as to minimize (maximize) the upper (lower) bound on the maximum (minimum) weighted distance from the nodes to the facility with a probability greater than or equal to a pre‐specified...
We consider the offline problem of routing a permutation of tokens on the nodes of a d‐dimensional hypercube, under a queueless MIMD communication model (in which we have the constraints that each hypercube edge may only communicate one token per communication step, and each node may only be occupied by a single token between communication steps). For a d‐dimensional hypercube, it is easy to see that...
In the Maximum Cut with Limited Unbalance problem, we want to partition the vertices of a weighted graph into two sets of sizes differing at most by a given threshold B, so that the sum of the weights of the crossing edges is maximum. This problem has been introduced in (Galbiati and Maffioli, Theor Comput Sci 385 (2007), 78–87) where polynomial time randomized approximation algorithms are proposed...
We consider the problem of setting revenue‐maximizing tolls on a subset of arcs of a transportation network, assuming that the users of the network are assigned to shortest paths with respect to the sum of tolls and initial costs. Our main results are concerned with a polyhedral study of the problem, i.e., the design of valid inequalities and facets for this pricing problem and some of its variants...
In this article, a detection strategy based on variable neighborhood search (VNS) and semidefinite relaxation of the multiuser model maximum likelihood (ML) is investigated. The VNS method provides a good method for solving the ML problem while keeping the integer constraints. A SDP relaxation is used as an efficient way to generate an initial solution in a limited amount of time, in particular using...
In this article, we introduce the regenerator location problem (RLP), which deals with a constraint on the geographical extent of transmission in optical networks. Specifically, an optical signal can only travel a maximum distance of dmax before its quality deteriorates to the point that it must be regenerated by installing regenerators at nodes of the network. As the cost of a regenerator is high,...
The expected number of vertices that remain joined to the root vertex s of a rooted graph Gs when edges are prone to fail is a polynomial EV(Gs; p) in the edge probability p that depends on the location of s. We show that optimal locations for the root can vary arbitrarily as p varies from 0 to 1 by constructing a graph in which every permutation of k‐specified vertices is the “optimal” ordering for...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.