Fast searching games on graphs

Given a graph, suppose that intruders hide on vertices or along edges of the graph. The fast searching problem is to find the minimum number of searchers required to capture all the intruders satisfying the constraint that every edge is traversed exactly once and searchers are not allowed to jump. In this paper, we prove lower bounds on the fast search number. We present a linear time algorithm to compute the fast search number of Halin graphs and their extensions. We present a quadratic time algorithm to compute the fast search number of cubic graphs.     

An online algorithm for continuous slab caster scheduling

Lee et al. (Lee, K., Chang, S.Y., and Hong, Y., 2004. Continuous slab caster scheduling and interval graphs. Production Planning & Control, 13 (5), 495–501) have introduced a slab caster scheduling problem and developed an optimal algorithm. Their algorithm is efficient but an offline algorithm that we need the information on all the customer orders a priori to implement. In this article, we propose an online algorithm that we can implement without knowledge of the orders yet to arrive. We show that the offline version of our new algorithm also provides an optimal solution and the online version has the worst case performance ratio of 3. We also give a short proof on the correctness of Lee et al.'s algorithm.     

On broadcasting in unicyclic graphs

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Finding the broadcast time of a vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for trees. In this paper we present a linear algorithm that determines the broadcast time of any originator in an arbitrary unicyclic graph. As a byproduct, we find a broadcast center of the unicyclic graph. We also present an O(|V|+k ²) algorithm to find the broadcast time of an arbitrary unicyclic graph, where k is the length of the cycle. In the last section we give tight lower and upper bounds on broadcast time of a spanning tree based on the broadcast time of the unicyclic graph. The results of Sects. 2, 3 and most of the proofs in Sects. 2, 3 of this paper are presented by Harutyunyan and Maraachlian (Proceedings of 13th annual COCOON, pp. 372–383, 2007). All results in Sects. 4, 5 and the complete proof of Theorem 3 are new results.     

An Efficient Algorithm for Delay Buffer Minimization

A data flow machine is said to be synchronized if for any vertex u in the underlying data flow graph, all inputs to vertex u arrive at the same time. An unsynchronized data flow machine with an acyclic underlying data flow graph can be transformed into a synchronized system by adding unit delay buffers to the system. This synchronization process can increase pipelining and throughout. Since the addition of delay buffers introduces hardware and area costs, it is desirable to insert the minimum number of delay buffers to synchronize a given data flow machine. Due to important applications in computer design, various delay buffer minimization problems have been studied by many researchers. Several optimal algorithms and heuristic algorithms have been proposed for slightly different models. In this paper, we introduce the concept of extensions of a directed acyclic graph to generalize and formalize several delay buffer minimization problems studied in the literature and present a polynomial time algorithm for computing the minimum delay buffer synchronization of a given data flow machine. Examples are provided to illustrate our algorithm and to show that our algorithm requires fewer delay buffers than previously published optimal algorithms for various models.     

On risk-averse maximum weighted subgraph problems

In this work, we consider a class of risk-averse maximum weighted subgraph problems (R-MWSP). Namely, assuming that each vertex of the graph is associated with a stochastic weight, such that the joint distribution is known, the goal is to obtain a subgraph of minimum risk satisfying a given hereditary property. We employ a stochastic programming framework that is based on the formalism of modern theory of risk measures in order to find minimum-risk hereditary structures in graphs with stochastic vertex weights. The introduced form of risk function for measuring the risk of subgraphs ensures that optimal solutions of R-MWS problems represent maximal subgraphs. A graph-based branch-and-bound (BnB) algorithm for solving the proposed problems is developed and illustrated on a special case of risk-averse maximum weighted clique problem. Numerical experiments on randomly generated Erdös-Rényi graphs demonstrate the computational performance of the developed BnB.     

Allocation and Pricing of Substitutable Goods: Theory and Algorithm

Motivated by the thriving market of online display advertising, we study a problem of allocating numerous types of goods among many agents who have concave valuations (capturing risk aversion) and heterogeneous substitution preferences across types of goods. The goal is both to provide a theory for optimal allocation of such goods, and to offer a scalable algorithm to compute the optimal allocation and the associated price vectors. Drawing on the economic concept of Pareto optimality, we develop an equilibrium pricing theory for heterogeneous substitutable goods that parallels the pricing theory for financial assets. We then develop a fast algorithm called SIMS (standardization‐and‐indicator‐matrix‐search). Extensive numerical simulations suggest that the SIMS algorithm is very scalable and is up to three magnitudes faster than well‐known alternative algorithms. Our theory and algorithm have important implications for the pricing and scheduling of online display advertisement and beyond.     

A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity

Given an undirected graph G and two vertex subsets H1 and H2, the bi-level augmentation problem is that of adding to G the smallest number of edges such that the resulting graph contains two internally vertex-disjoint paths between every pair of vertices in H1 and two edge-disjoint paths between every pair of vertices in H2. We present an algorithm to solve this problem in linear time. By properly setting H1 and H2, this augmentation algorithm subsumes existing optimal algorithms for several graph augmentation problems.     

The canadian traveller problem and its competitive analysis

From the online point of view, we study the Canadian Traveller Problem (CTP), in which the traveller knows in advance the structure of the graph and the costs of all edges. However, some edges may fail and the traveller only observes that upon reaching an adjacent vertex of the blocked edge. The goal is to find the least-cost route from the source O to the destination D, more precisely, to find an adaptive strategy minimizing the competitive ratio, which compares the performance of this strategy with that of a hypothetical offline algorithm that knows the entire topology in advance. In this paper, we present two adaptive strategies—a greedy or myopic strategy and a comparison strategy combining the greedy strategy and the reposition strategy in which the traveller backtracks to the source every time when he/she sees a failed edge. We prove tight competitive ratios of 2 ^k+1−1 and 2k+1 respectively for the two strategies, where k is the number of failed edges in the graph. Finally, we propose an explanation of why the greedy strategy and the comparison strategy are usually preferred by drivers in an urban traffic environment, based on an argument related to the length of the second-shortest path in a grid graph. We would like to acknowledge the support from NSF of China (No. 70525004, No. 70121001 and No. 60736027), and the support from K.C. Wong Education Foundation, Hong Kong.     

突发性片堵塞下两车信息共享的加拿大旅行者问题

提出突发性片堵塞下两车信息共享的加拿大旅行者问题,即两车欲从起点出发去终点,在运输过程中会遭遇突发性片堵塞,若两车对堵塞信息都能有限预知且车辆间可以信息共享,如何制定路径选择策略使两车花费的总时间尽可能少。针对该问题,采用在线问题与竞争策略的理论和方法,建立突发性片堵塞下两车信息共享的在线路径选择模型,设计混合贪婪策略,结合片堵塞中多条路段同时发生堵塞的特点,以及所选路径是否经过信息预知点到片堵塞起始点的路段（预知路段）等策略不同情形的分析,证明混合贪婪策略竞争比。最后进行实例分析,验证模型和策略的有效性。     

Some graph optimization problems with weights satisfying linear constraints

In this paper, we study several graph optimization problems in which the weights of vertices or edges are variables determined by several linear constraints, including maximum matching problem under linear constraints (max-MLC), minimum perfect matching problem under linear constraints (min-PMLC), shortest path problem under linear constraints (SPLC) and vertex cover problem under linear constraints (VCLC). The objective of these problems is to decide the weights that are feasible to the linear constraints, and find the optimal solutions of corresponding graph optimization problems among all feasible choices of weights. We find that these problems are NP-hard and are hard to be approximated in general. These findings suggest us to explore various special cases of them. In particular, we show that when the number of constraints is a fixed constant, all these problems are polynomially solvable. Moreover, if the total number of distinct weights is a fixed constant, then max-MLC, min-PMLC and SPLC are polynomially solvable, and VCLC has a 2-approximation algorithm. In addition, we propose approximation algorithms for various cases of max-MLC.

     

From theory to practice: maximizing revenues for on-line dial-a-ride

We consider the on-line dial-a-ride problem, where a server fulfills requests that arrive over time. Each request has a source, destination, and release time. We study a variation of this problem where each request also has a revenue that the server earns for fulfilling the request. The goal is to serve requests within a time limit while maximizing the total revenue. We first prove that no deterministic online algorithm can be competitive unless the input graph is complete and edge weights are unit. We therefore focus on these graphs and present a 2-competitive algorithm for this problem. We also consider two variations of this problem: (1) the input graph is complete bipartite and (2) there is a single node that is the source for every request, and present a 1-competitive algorithm for the former and an optimal algorithm for the latter. We also provide experimental results for the complete and complete bipartite graphs. Our simulations support our theoretical findings and demonstrate that our algorithms perform well under settings that reflect realistic dial-a-ride systems.     

The Canadian Tour Operator Problem on paths: tight bounds and resource augmentation

In the prize-collecting travelling salesman problem, we are given a weighted graph \(G=(V,E)\) with edge weights \(\ell :E\rightarrow \mathbb {R}_+\), a special vertex \(r\in V\), penalties \(\pi :V\rightarrow \mathbb {R}_+\) and the goal is to find a closed tour \(T\) such that \(r\in V(T)\) and such that the cost \(\ell (T)+\pi (V\setminus V(T))\), which is the sum of the edges in the tour and the cost of the vertices not spanned by \(T\), is minimized. We consider an online variant of the prize-collecting travelling salesman problem related to graph exploration. In the Canadian Tour Operator Problem the task is to find a closed route for a tourist bus in a given network \(G=(V,E)\) in which some edges are blocked by avalanches. An online algorithm learns from a blocked edge only when reaching one of its endpoints. The bus operator has the option to avoid visiting each node \(v\in V\) by paying a refund of \(\pi (v)\) to the tourists. The goal consists of minimizing the sum of the travel costs and the refunds. We study the problem on a simple (weighted) path and prove tight bounds on the competitiveness of deterministic algorithms. Specifically, we give an algorithm with competitive ratio equal to the golden ratio \(\phi =(1+\sqrt{5})/2\). We also study the effect of resource augmentation, where the online algorithm either pays a discounted cost for traversing edges or for the penalties.     

Lower bounds for positive semidefinite zero forcing and their applications

The positive semidefinite zero forcing number of a graph is a parameter that is important in the study of minimum rank problems. In this paper, we focus on the algorithmic aspects of computing this parameter. We prove that it is NP-complete to find the positive semidefinite zero forcing number of a given graph, and this problem remains NP-complete even for graphs with maximum vertex degree 7. We present a linear time algorithm for computing the positive semidefinite zero forcing number of generalized series–parallel graphs. We introduce the constrained tree cover number and apply it to improve lower bounds for positive semidefinite zero forcing. We also give formulas for the constrained tree cover number and the tree cover number on graphs with special structures.     

Tagged Probe Interval Graphs

A generalization of interval graph is introduced for cosmid contig mapping of DNA. A graph is a tagged probe interval graph if its vertex set can be partitioned into two subsets of probes and nonprobes, and a closed interval can be assigned to each vertex such that two vertices are adjacent if and only if at least one of them is a probe and one end of its corresponding interval is contained in the interval corresponding to the other vertex. We show that tagged probe interval graphs are weakly triangulated graphs, hence are perfect graphs. For a tagged probe interval graph with a given partition, we give a chordal completion that is consistent to any interval completions with respect to the same vertex partition.     

基于邻接网络的频繁项目集发现算法

频繁项目集发现一直都是关联规则研究领域中最繁项目集发现算法,该算法的特别之处在于事先利用有向图进行的一次数据预处理,在预处理过程中将数据库预先存贮为每个结点都有一个域来记录其支持度的项目集邻接网络,从而把复杂的频繁项目集的发现问题转化为简单的图中搜索问题,这就大大提高了频繁项目集发现过程的效率.同时为了有效地解决预处理过程中的项目集支持度计算问题,采用了一种纵向的数据库表示格式.最后对所采用的算法给出实验结果.     

Generalized median graphs and applications

We study the so-called Generalized Median graph problem where the task is to construct a prototype (i.e., a ‘model’) from an input set of graphs. While our primary motivation comes from an important biological imaging application, the problem effectively captures many vision (e.g., object recognition) and learning problems, where graphs are increasingly being adopted as a powerful representation tool. Existing techniques for his problem are evolutionary search based; in this paper, we propose a polynomial time algorithm based on a linear programming formulation. We propose an additional algorithm based on a bi-level method to obtain solutions arbitrarily close to the optimal in (worst case) non-polynomial time. Within this new framework, one can optimize edit distance functions that capture similarity by considering vertex labels as well as he graph structure simultaneously. We first discuss experimental evaluations in context of molecular image analysis problems—he methods will provide the basis for building a topological map of all 23 pairs of the human chromosome. Later, we include (a) applications to other biomedical problems and (b) evaluations on a public pattern recognition graph database. This work was supported by NSF grants CCF-0546509, IIS-0713489, and NIH grant GM 072131-23. The second author was also supported in part by the Department of Biostatistics and Medical Informatics, UW-Madison and UW ICTR, funded through an NIH Clinical and Translational Science Award (CTSA), grant number 1 UL1 RR025011.     

Special cases of the quadratic shortest path problem

The quadratic shortest path problem (QSPP) is the problem of finding a path with prespecified start vertex s and end vertex t in a digraph such that the sum of weights of arcs and the sum of interaction costs over all pairs of arcs on the path is minimized. We first consider a variant of the QSPP known as the adjacent QSPP. It was recently proven that the adjacent QSPP on cyclic digraphs cannot be approximated unless \(\hbox {P}=\hbox {NP}\). Here, we give a simple proof for the same result. We also show that if the quadratic cost matrix is a symmetric weak sum matrix and all s–t paths have the same length, then an optimal solution for the QSPP can be obtained by solving the corresponding instance of the shortest path problem. Similarly, it is shown that the QSPP with a symmetric product cost matrix is solvable in polynomial time. Further, we provide sufficient and necessary conditions for a QSPP instance on a complete symmetric digraph with four vertices to be linearizable. We also characterize linearizable QSPP instances on complete symmetric digraphs with more than four vertices. Finally, we derive an algorithm that examines whether a QSPP instance on the directed grid graph \(G_{pq}\) (\(p,q\ge 2\)) is linearizable. The complexity of this algorithm is \({\mathcal {O}(p^{3}q^{2}+p^{2}q^{3})}\).     

Near optimal algorithms for online weighted bipartite matching in adversary model

Bipartite matching is an important problem in graph theory. With the prosperity of electronic commerce, such as online auction and AdWords allocation, bipartite matching problem has been extensively studied under online circumstances. In this work, we study the online weighted bipartite matching problem in adversary model, that is, there is a weighted bipartite graph \(G=(L,R,E)\) and the left side L is known as input, while the vertices in R come one by one in an order arranged by the adversary. When each vertex in R comes, its adjacent edges and relative weights are revealed. The algorithm should irreversibly decide whether to match this vertex to an unmatched neighbor in L with the objective to maximize the total weight of the obtained matching. When the weights are unbounded, the best algorithm can only achieve a competitive ratio \(\varTheta \left( \frac{1}{n}\right) \), where n is the number of vertices coming online. Thus, we mainly deal with two variants: the bounded weight problem in which all weights are in the range \([\alpha , \beta ]\), and the normalized summation problem in which each vertex in one side has the same total weights. We design algorithms for both variants with competitive ratio \(\varTheta \left( \max \left\{ \frac{1}{\log \frac{\beta }{\alpha }},\frac{1}{n}\right\} \right) \) and \(\varTheta \left( \frac{1}{\log n}\right) \) respectively. Furthermore, we show these two competitive ratios are tight by providing the corresponding hardness results.     

The Travelling Salesman Problem on Permuted Monge Matrices

We consider traveling salesman problems (TSPs) with a permuted Monge matrix as cost matrix where the associated patching graph has a specially simple structure: a multistar, a multitree or a planar graph. In the case of multistars, we give a complete, concise and simplified presentation of Gaikov's theory. These results are then used for designing an O(m3 + mn) algorithm in the case of multitrees, where n is the number of cities and m is the number of subtours in an optimal assignment. Moreover we show that for planar patching graphs, the problem of finding an optimal subtour patching remains NP-complete.     

Multi-start iterated tabu search for the minimum weight vertex cover problem

The minimum weight vertex cover problem (MWVCP) is one of the most popular combinatorial optimization problems with various real-world applications. Given an undirected graph where each vertex is weighted, the MWVCP is to find a subset of the vertices which cover all edges of the graph and has a minimum total weight of these vertices. In this paper, we propose a multi-start iterated tabu search algorithm (MS-ITS) to tackle MWVCP. By incorporating an effective tabu search method, MS-ITS exhibits several distinguishing features, including a novel neighborhood construction procedure and a fast evaluation strategy. Extensive experiments on the set of public benchmark instances show that the proposed heuristic is very competitive with the state-of-the-art algorithms in the literature.