Skip to main content

2017 | Buch

Combinatorial Optimization and Applications

11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II

insite
SUCHEN

Über dieses Buch

The two-volume set LNCS 10627 and 10628 constitutes the refereed proceedings of the 11th International Conference on Combinatorial Optimization and Applications, COCOA 2017, held in Shanghai, China, in December 2017.

The 59 full papers and 19 short papers presented were carefully reviewed and selected from 145 submissions. The papers cover most aspects of theoretical computer science and combinatorics related to computing, including classic combinatorial optimization, geometric optimization, complexity and data structures, and graph theory. They are organized in topical sections on network, approximation algorithm and graph theory, combinatorial optimization, game theory, and applications.

Inhaltsverzeichnis

Frontmatter

Combinatorial Optimization

Frontmatter
Algorithms for the Ring Star Problem

We address the Ring Star Problem (RSP) on a complete graph $$G=(V,E)$$G=(V,E) whose edges are associated with both a nonnegative ring cost and a nonnegative assignment cost. The RSP is to locate a simple ring (cycle) R in G with the objective of minimizing the sum of two costs: the ring cost of (all edges in) R and the assignment cost for attaching nodes in $$V\setminus V(R)$$V\V(R) to their closest ring nodes (in R). We focus on the metric RSP with fixed edge-cost ratio, in which both ring cost function and assignment cost function defined on E satisfy triangle inequalities, and the ratios between the ring cost and assignment cost are the same value $$M\ge 1$$M≥1 for all edges.We show that the star structure is an optimal solution of the RSP when $$M\ge (|V|-1)/2$$M≥(|V|-1)/2. This particularly implies a $$\sqrt{|V|-1}$$|V|-1-approximation algorithm for the general RSP. Heuristics based on some natural strategies are proposed. Simulation results demonstrate that the proposed approximation and heuristic algorithms have very good practical performances. We also consider the capacitated RSP which puts an upper limit k on the number of leaf nodes that a ring node can serve. We present a $$(10+6M/k)$$(10+6M/k)-approximation algorithm for the capacitated generalization.

Xujin Chen, Xiaodong Hu, Zhongzheng Tang, Chenhao Wang, Ying Zhang
Price Fluctuation in Online Leasing

Current theoretical attempts towards understanding real-life leasing scenarios assume the following leasing model. Demands arrive with time and need to be served by leased resources. Different types of leases are available, each with a fixed duration and price, respecting economy of scale (longer leases cost less per unit time). An online algorithm is to serve each arriving demand while minimizing the total leasing costs and without knowing future demands. In this paper, we generalize this model into one in which lease prices fluctuate with time and are not known to the algorithm in advance. Hence, an online algorithm is to perform under the uncertainty of both demands and lease prices. We consider different adversarial models and provide online algorithms, evaluated using standard competitive analysis. For each of these models, we give deterministic matching upper and lower bounds.

Björn Feldkord, Christine Markarian, Friedhelm Meyer Auf der Heide
Novel Scheduling for Energy Management in Microgrid

Microgrids have made more distributed energy resources available, while the effective applications are still hindered by the limited control of both power demand and supply. To address this issue, we propose a novel energy management system based on mobile social app for energy management in microgrids. Specifically, we not only let users share and report their energy consumption patterns via the proposed mobile social app, but also let them modify their plans to balance the energy supply and demand. We mathematically formulate the new energy management into an optimization problem, with the objective of coordinating the energy consumption activities to maximize the utilization of renewable energy resources. Resorting to methods from Combinatorics, we develop an approximation scheduling algorithm by considering the characteristics of renewable power resources. By experimental simulation, we show that the proposed system can significantly improve the energy efficiency of microgrids.

Zaixin Lu, Jd Youngs, Zhi Chen, Miao Pan
Improved Methods for Computing Distances Between Unordered Trees Using Integer Programming

Kondo et al. (DS 2014) proposed integer linear programming formulations for computing the tree edit distance and its variants between unordered rooted trees. They showed that the tree edit distance, segmental distance, and bottom-up segmental distance problems respectively have integer linear programming formulations with O(nm) variables and $$O(n^2m^2)$$O(n2m2) constraints, where n and m are the number of nodes of two input trees. In this work, we propose new integer linear programming formulations for these three distances and the bottom-up distance by combining with dynamic programming. For computing the tree edit distance, we solve O(nm) subproblems, each of which is formulated by an integer linear program with O(nm) variables and $$O(n + m)$$O(n+m) constraints. For the other three distances, each subproblem can be reduced to the maximum weight matching problem in a bipartite graph which is solvable in polynomial time. In order to compute the distances from the solutions of subproblems, we also give a unified integer linear formulation with O(nm) variables and $$O(n + m)$$O(n+m) constraints. We conducted a computational experiment to evaluate the performance of our methods. The experimental results show that our methods remarkably outperformed to the previous methods due to Kondo et al.

Eunpyeong Hong, Yasuaki Kobayashi, Akihiro Yamamoto
Touring Convex Polygons in Polygonal Domain Fences

In the touring polygons problem (TPP), for a given sequence $$(s=P_0,P_1,\dots ,P_k,t=P_{k+1})$$(s=P0,P1,⋯,Pk,t=Pk+1) of polygons in the plane, where s and t are two points, the goal is to find a shortest path that starts from s, visits each of the polygons in order and ends at t. In the constrained version of TPP, there is another sequence $$(F_{0},\dots ,F_{k})$$(F0,⋯,Fk) of polygons called fences, and the portion of the path from $$P_i$$Pi to $$P_{i+1}$$Pi+1 must lie inside the fence $$F_{i}$$Fi. TPP is NP-hard for disjoint non-convex polygons, while TPP and constrained TPP are polynomially solvable when the polygons are convex and the fences are simple polygons. In this work, we present the first polynomial time algorithm for solving constrained TPP when the fences are polygonal domains (polygons with holes). Since, the safari problem is a special case of TPP, our algorithm can be used for solving safari problem inside polygons with holes.

Arash Ahadi, Amirhossein Mozafari, Alireza Zarei
On Interdependent Failure Resilient Multi-path Routing in Smart Grid Communication Network

This paper introduces six new failure-independent multi-path computation problems in complex networks such as smart grid communication network, each of which comes with unique failure interdependency assumptions. Despite the difference of the formulation of the problems, we show that each of the problems can be reduced to another within polynomial time, and therefore they are equivalent in terms of hardness. Then, we show that they are not only $$\mathcal {NP}$$NP-hard, but also cannot be approximated within a certain bound unless $$\mathcal {P}=\mathcal {NP}$$P=NP. Besides, we show that their decision problem versions to determine if there exist two failure independent paths between two given end nodes are still $$\mathcal {NP}$$NP-complete. As a result, this paper opens a new series of research problems with daunting complexity based on important real world applications.

Zishen Yang, Donghyun Kim, Wei Wang
An Improved Branching Algorithm for (n, 3)-MaxSAT Based on Refined Observations

In the MaxSAT problem, we are given a CNF formula (conjunctive normal form) and seek an assignment satisfying the maximum number of clauses. In the parameterized (n, 3)-MaxSAT problem we are given an integer k and a CNF formula such that each variable appears in at most 3 clauses, and are asked to find an assignment that satisfies at least k clauses. Based on refined observations, we propose a branching algorithm for the (n, 3)-MaxSAT problem with significant improvement over the previous results. More precisely, the running time of our algorithm can be bounded by $$O^*(1.175^k)$$O∗(1.175k) and $$O^*(1.194^n)$$O∗(1.194n), respectively, where n is the number of variables in the given CNF formula. Prior to our study, the running time of the best known exact algorithm can be bounded by $$O^*(1.194^k)$$O∗(1.194k) and $$O^*(1.237^n)$$O∗(1.237n), respectively.

Wenjun Li, Chao Xu, Jianxin Wang, Yongjie Yang
Faster Algorithms for 1-Mappability of a Sequence

In the k-mappability problem, we are given a string x of length n and integers m and k, and we are asked to count, for each length-m factor y of x, the number of other factors of length m of x that are at Hamming distance at most k from y. We focus here on the version of the problem where $$k=1$$k=1. The fastest known algorithm for $$k=1$$k=1 requires time $$\mathcal {O}(mn \log n/\log \log n)$$O(mnlogn/loglogn) and space $$\mathcal {O}(n)$$O(n). We present two new algorithms that require worst-case time $$\mathcal {O}(mn)$$O(mn) and $$\mathcal {O}(n \log n \log \log n)$$O(nlognloglogn), respectively, and space $$\mathcal {O}(n)$$O(n), thus greatly improving the state of the art. Moreover, we present another algorithm that requires average-case time and space $$\mathcal {O}(n)$$O(n) for integer alphabets of size $$\sigma $$σ if $$m=\varOmega (\log _\sigma n)$$m=Ω(logσn). Notably, we show that this algorithm is generalizable for arbitrary k, requiring average-case time $$\mathcal {O}(kn)$$O(kn) and space $$\mathcal {O}(n)$$O(n) if $$m=\varOmega (k\log _\sigma n)$$m=Ω(klogσn).

Mai Alzamel, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis, Jakub Radoszewski, Wing-Kin Sung
Lexico-Minimum Replica Placement in Multitrees

In this work, we consider the problem of placing replicas in a data center or storage area network, represented as a digraph, so as to lexico-minimize a previously proposed reliability measure which minimizes the impact of all failure events in the model in decreasing order of severity. Prior work focuses on the special case in which the digraph is an arborescence. In this work, we consider the broader class of multitrees: digraphs in which the subgraph induced by vertices reachable from a fixed node forms a tree. We parameterize multitrees by their number of “roots” (nodes with in-degree zero), and rule out membership in the class of fixed-parameter tractable problems (FPT) by showing that finding optimal replica placements in multitrees with 3 roots is NP-hard. On the positive side, we show that the problem of finding optimal replica placements in the class of untangled multitrees is FPT, as parameterized by the replication factor $$\rho $$ρ and the number of roots k. Our approach combines dynamic programming (DP) with a novel tree decomposition to find an optimal placement of $$\rho $$ρ replicas on the leaves of a multitree with n nodes and k roots in $$O(n^2\rho ^{2k+3})$$O(n2ρ2k+3) time.

K. Alex Mills, R. Chandrasekaran, Neeraj Mittal
Graph Editing to a Given Neighbourhood Degree List is Fixed-Parameter Tractable

Graph editing problems ask whether an input graph can be modified to a graph with a given property by inserting and deleting vertices and edges. We consider the problem Graph Edit to NDL, which asks whether a graph can be modified to a graph with a given neighbourhood degree list (NDL) using at most $$\ell $$ℓ graph edits. The NDL lists the degrees of the neighbours of vertices in a graph, and is a stronger invariant than the degree sequence, which lists the degrees of vertices. In fact, the degree sequence of a graph is determined by its NDL.We show that Graph Edit to NDL is W[1]-hard when parameterized by $$\ell $$ℓ and give an algorithm that runs in fixed-parameter time when parameterized by $$\varDelta +\ell $$Δ+ℓ, where $$\varDelta $$Δ is the maximum degree of the input graph. Furthermore, we adapt our algorithm to solve a harder problem, Constrained Graph Edit to NDL, which imposes constraints on the NDLs of the intermediate graphs produced in the sequence, in fixed-parameter time when parameterized by $$\varDelta +\ell $$Δ+ℓ.Moreover, there exist graph measures such as assortativity [17] and average nearest neighbour degree [18] that can be derived from the NDL, but not the degree sequence. Our algorithm can be adapted to solve the problem of editing to a graph with a given value of such a measure.

Naomi Nishimura, Vijay Subramanya
A New Graph Parameter to Measure Linearity

Since its introduction to recognize chordal graphs by Rose, Tarjan, and Lueker, Lexicographic Breadth First Search (LexBFS) has been used to come up with simple, often linear time, algorithms on various classes of graphs. These algorithms are usually multi-sweep algorithms; that is they compute LexBFS orderings $$\sigma _1, \ldots , \sigma _k$$σ1,…,σk, where $$\sigma _i$$σi is used to break ties for $$\sigma _{i+1}$$σi+1. Since the number of LexBFS orderings for a graph is finite, this infinite sequence $$\{\sigma _i\}$${σi} must have a loop, i.e. a multi-sweep algorithm will loop back to compute $$\sigma _j$$σj, for some j. We study this new graph invariant, LexCycle(G), defined as the maximum length of a cycle of vertex orderings obtained via a sequence of LexBFS$$^+$$+. In this work, we focus on graph classes with small LexCycle. We give evidence that a small LexCycle often leads to linear structure that has been exploited algorithmically on a number of graph classes. In particular, we show that for proper interval, interval, co-bipartite, domino-free cocomparability graphs, as well as trees, there exists two orderings $$\sigma $$σ and $$\tau $$τ such that $$\sigma = \text {LexBFS}^+(\tau )$$σ=LexBFS+(τ) and $$\tau = \text {LexBFS}^+(\sigma )$$τ=LexBFS+(σ). One of the consequences of these results is the simplest algorithm to compute a transitive orientation for these graph classes. It was conjectured by Stacho [2015] that LexCycle is at most the asteroidal number of the graph class, we disprove this conjecture by giving a construction for which $${{\mathrm{LexCycle}}}(G) > an(G)$$LexCycle(G)>an(G), the asteroidal number of G.

Pierre Charbit, Michel Habib, Lalla Mouatadid, Reza Naserasr
Listing Acyclic Subgraphs and Subgraphs of Bounded Girth in Directed Graphs

The girth of a directed graph is the length of its shortest directed cycle. We consider the problem of generating all subgraphs of girth at least g in a directed graph G with n vertices and m edges. This generalizes the problem of generating acyclic subgraphs (i.e., with no directed cycle), that correspond to the subgraphs of girth at least $$n+1$$n+1. The problem of finding the acyclic subgraph with maximum size or weight has been thoroughly studied, however to the best of our knowledge there is no known efficient enumeration algorithm. We propose polynomial delay algorithms for listing both induced and edge subgraphs with girth g in time O(n) per solution; both improve upon a naive solution, respectively by a factor O(nm) and $$O(m^2)$$O(m2). Furthermore, this work is on the line of existing research for extracting acyclic structures from graphs.

Alessio Conte, Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno
Toward Energy-Efficient and Robust Clustering Algorithm on Mobile Ad Hoc Sensor Networks

Nodes in mobile Ad hoc sensor network have characteristics of limited battery energy, dense deploy and low mobility. Therefore, topology control and energy consumption are growing to be critical in enhancing the stability and prolonging the lifetime of the network. Consequently, we propose a robust, energy-efficient weighted clustering algorithm, RE2WCA. To achieve the tradeoff between load balance and node density, the average minimum reachability power has been adopted. For the homogeneous of the energy consumption, the proposed clustering algorithm takes the residual energy and group mobility into consideration by restricting minimum iteration times. Meanwhile, in order to overcome the problem of robustness of the network, a distributed fault detection algorithm and energy-efficient topology maintenance mechanism are presented to achieve the periodic and real-time topology maintenance in order to enhance the robustness of the network. The simulations are conducted to compare the performance with the similar algorithms in terms of cluster characteristics, lifetime, robustness and throughput of the network. The result shows that the proposed algorithm provides better performance than others.

Huamei Qi, Tailong Xiao, Anfeng Liu, Su Jiang

Game Theory

Frontmatter
The Cop Number of the One-Cop-Moves Game on Planar Graphs

Cops and robbers is a vertex-pursuit game played on graphs. In the classical cops-and-robbers game, a set of cops and a robber occupy the vertices of the graph and move alternately along the graph’s edges with perfect information about each other’s positions. If a cop eventually occupies the same vertex as the robber, then the cops win; the robber wins if she can indefinitely evade capture. Aigner and Frommer established that in every connected planar graph, three cops are sufficient to capture a single robber. In this paper, we consider a recently studied variant of the cops-and-robbers game, alternately called the one-active-cop game, one-cop-moves game or the lazy-cops-and-robbers game, where at most one cop can move during any round. We show that Aigner and Frommer’s result does not generalise to this game variant by constructing a connected planar graph on which a robber can indefinitely evade three cops in the one-cop-moves game. This answers a question recently raised by Sullivan, Townsend and Werzanski.

Ziyuan Gao, Boting Yang
The Price of Anarchy in Two-Stage Scheduling Games

We consider a scheduling game, in which both the machines and the jobs are players. A job attempts to minimize its completion time by switching machines, while each machine would like to maximize its workload by choosing a scheduling policy from the given set of policies. We consider a two-stage game. In the first stage every machine simultaneously chooses a policy from some given set of policies, and in the second stage, every job simultaneously chooses a machine. In this work, we use the price of anarchy to measure the efficiency of such equilibria where each machine is allowed to use at most two policies. We provide nearly tight bounds for every combination of two deterministic scheduling policies with respect to two social objectives: minimizing the maximum job completion, and maximizing the minimum machine completion time.

Deshi Ye, Lin Chen, Guochuan Zhang
Selfish Jobs with Favorite Machines: Price of Anarchy vs. Strong Price of Anarchy

We consider the well-studied game-theoretic version of machine scheduling in which jobs correspond to self-interested users and machines correspond to resources. Here each user chooses a machine trying to minimize her own cost, and such selfish behavior typically results in some equilibrium which is not globally optimal: An equilibrium is an allocation where no user can reduce her own cost by moving to another machine, which in general need not minimize the makespan, i.e., the maximum load over the machines.We provide tight bounds on two well-studied notions in algorithmic game theory, namely, the price of anarchy and the strong price of anarchy on machine scheduling setting which lies in between the related and the unrelated machine case. Both notions study the social cost (makespan) of the worst equilibrium compared to the optimum, with the strong price of anarchy restricting to a stronger form of equilibria. Our results extend a prior study comparing the price of anarchy to the strong price of anarchy for two related machines (Epstein [13], Acta Informatica 2010), thus providing further insights on the relation between these concepts. Our exact bounds give a qualitative and quantitative comparison between the two models. The bounds also show that the setting is indeed easier than the two unrelated machines: In the latter, the strong price of anarchy is 2, while in ours it is strictly smaller.

Cong Chen, Paolo Penna, Yinfeng Xu
An Improved Mechanism for Selfish Bin Packing

Selfish bin packing can be viewed as the non-cooperative version of bin packing problem, where every item is a selfish agent and want to minimize his sharing cost with the other items packing in the same bin. In this paper, we focus on designing a new mechanism (a payoff rule) for selfish bin packing, called modified Dutch treatment mechanism. We first show that the pure Nash equilibrium exists and it can be obtained in polynomial time. We then prove that under the new mechanism, the price of anarchy (PoA) is between 1.47407 and 1.4748, improving the known results.

Xin Chen, Qingqin Nong, Qizhi Fang

Approximation Algorithm and Graph Theory

Frontmatter
Hamiltonian Cycles in Covering Graphs of Trees

Hamiltonicity of graphs possessing symmetry has been a popular subject of research, with focus on vertex-transitive graphs, and in particular on Cayley graphs. In this paper, we consider the Hamiltonicity of another class of graphs with symmetry, namely covering graphs of trees. In particular, we study the problem for covering graphs of trees, where the tree is a voltage graph over a cyclic group. Batagelj and Pisanski were first to obtain such a result, in the special case when the voltage assignment is trivial; in that case, the covering graph is simply a Cartesian product of the tree and a cycle. We consider more complex voltage assignments, and extend the results of Batagelj and Pisanski in two different ways; in these cases the covering graphs cannot be expressed as products. We also provide a linear time algorithm to test whether a given assignment satisfies these conditions.

Pavol Hell, Hiroshi Nishiyama, Ladislav Stacho
On k-Strong Conflict–Free Multicoloring

Let $$\mathcal{H}=(\mathcal{V},\mathcal{E})$$H=(V,E) be a hypergraph. A k-strong conflict-free coloring of $$\mathcal{H}$$H is an assignment of colors to the members of the vertex set $$\mathcal{V}$$V such that every hyperedge $$E\in \mathcal{E}$$E∈E, $$|E|\ge k$$|E|≥k, contains k nodes whose colors are pairwise distinct and different from the colors assigned to all the other nodes in E, whereas if $$|E|<k$$|E|<k all nodes in E get distinct colors. The parameter to optimize is the total number of colors. The need for such colorings originally arose as a problem of frequency assignment for cellular networks, but since then it has found applications in a variety of different areas. In this paper we consider a generalization of the above problem, where one is allowed to assign more than one color to each node. When $$k=1$$k=1, our generalization reduces to the conflict-free multicoloring problem introduced by Even et al. [2003], and recently studied by Bärtschi and Grandoni [2015], and Ghaffari et al. [2017]. We motivate our generalized formulation and we point out that it includes a vast class of well known combinatorial and algorithmic problems, when the hypergraph $$\mathcal{H}$$H and the parameter k are properly instantiated. Our main result is an algorithm to construct a k-strong conflict-free multicolorings of an input hypergraph $$\mathcal{H}$$H that utilizes a total number of colors $$O( \min \{(k+\log ({r}/{k}) )\log {\varGamma }+ k( k+\log ^2 ({r}/{k})), \ (k^2 + r ) \log n \})$$O(min{(k+log(r/k))logΓ+k(k+log2(r/k)),(k2+r)logn}), where n is the number of nodes, $$r$$r is the maximum hyperedge size, and $${\varGamma }$$Γ is the maximum hyperedge degree; the expected number of colors per node is $$O(\min \{k+\log {\varGamma }, \ (k + \log ({r}/{k})) \log n \})$$O(min{k+logΓ,(k+log(r/k))logn}). Although derived for arbitrary k, our result improves on the corresponding result by Bärtschi and Grandoni [2015], when instantiated for $$k=1$$k=1. We also provide lower bounds on the number of colors needed in anyk-strong conflict-free multicoloring, thus showing that our algorithm is not too far from being optimal.

Luisa Gargano, Adele A. Rescigno, Ugo Vaccaro
Tropical Paths in Vertex-Colored Graphs

A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the initial graph. In this work we study the problem of finding tropical paths in vertex-colored graphs. There are two versions for this problem: the shortest tropical path problem (STPP), i.e., finding a tropical path with the minimum total weight, and the maximum tropical path problem (MTPP), i.e., finding a path with the maximum number of colors possible. We show that both versions of this problems are NP-hard for directed acyclic graphs, cactus graphs and interval graphs. Moreover, we also provide a fixed parameter algorithm for STPP in general graphs and several polynomial-time algorithms for MTPP in specific graphs, including bipartite chain graphs, threshold graphs, trees, block graphs, and proper interval graphs.

Johanne Cohen, Giuseppe F. Italiano, Yannis Manoussakis, Kim Thang Nguyen, Hong Phong Pham
The Spectral Radius and Domination Number of Uniform Hypergraphs

This paper investigates the spectral radius and signless Laplacian spectral radius of linear uniform hypergraphs. A dominating set in a hypergraph H is a subset D of vertices if for every vertex v not in D there exists $$u\in D$$u∈D such that u and v are contained in a hyperedge of H. The minimum cardinality of a dominating set of H is called the domination number of H. We give lower bounds on the spectral radius and signless Laplacian spectral radius of a linear uniform hypergraph in terms of its domination number.

Liying Kang, Wei Zhang, Erfang Shan
Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals

Graph coloring has been studied extensively in the literature. The classical problem concerns the number of colors used. In this paper, we focus on coloring intervals where the input is a set of intervals and two overlapping intervals cannot be assigned the same color. In particular, we are interested in the setting where there is an increasing cost associated with using a higher color index. Given a set of intervals (on a line) and a coloring, the cost of the coloring at any point is the cost of the maximum color index used at that point and the cost of the overall coloring is the integral of the cost over all points on the line. The objective is to assign a valid color to each interval and minimize the total cost of the coloring. Intuitively, the maximum color index used at each point forms a skyline and so the objective is to obtain a minimum skyline coloring. The problem arises in various applications including optical networks and job scheduling.Alicherry and Bhatia defined in 2003 a more general problem in which the colors are partitioned into classes and the cost of a color depends solely on its class. This problem is NP-hard and the reduction relies on the fact that some color class has more than one color. In this paper we show that when each color class only contains one color, this simpler setting remains NP-hard via a reduction from the arc coloring problem. In addition, we initiate the study of the online setting and present an asymptotically optimal online algorithm. We further study a variant of the problem in which the intervals are already partitioned into sets and the objective is to assign a color to each set such that the total cost is minimum. We show that this seemingly easier problem remains NP-hard by a reduction from the optimal linear arrangement problem.

Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, Prudence W. H. Wong, Shmuel Zaks
Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach

In this paper, we study the k-forest problem in the model of resource augmentation. In the k-forest problem, given an edge-weighted graph G(V, E), a parameter k, and a set of m demand pairs $$\subseteq V \times V$$⊆V×V, the objective is to construct a minimum-cost subgraph that connects at least k demands. The problem is hard to approximate—the best-known approximation ratio is $$O(\min \{\sqrt{n}, \sqrt{k}\})$$O(min{n,k}). Furthermore, k-forest is as hard to approximate as the notoriously-hard densest k-subgraph problem.While the k-forest problem is hard to approximate in the worst-case, we show that with the use of resource augmentation, we can efficiently approximate it up to a constant factor.First, we restate the problem in terms of the number of demands that are not connected. In particular, the objective of the k-forest problem can be viewed as to remove at most $$m-k$$m-k demands and find a minimum-cost subgraph that connects the remaining demands. We use this perspective of the problem to explain the performance of our algorithm (in terms of the augmentation) in a more intuitive way.Specifically, we present a polynomial-time algorithm for the k-forest problem that, for every $$\varepsilon >0$$ε>0, removes at most $$m-k$$m-k demands and has cost no more than $$O(1/\varepsilon ^{2})$$O(1/ε2) times the cost of an optimal algorithm that removes at most $$(1-\varepsilon )(m-k)$$(1-ε)(m-k) demands.

Eric Angel, Nguyen Kim Thang, Shikha Singh
Parameterized Approximation Algorithms for Some Location Problems in Graphs

We develop efficient parameterized, with additive error, approximation algorithms for the (Connected) r-Domination problem and the (Connected) p-Center problem for unweighted and undirected graphs. Given a graph G, we show how to construct a (connected) $$\big (r + \mathcal {O}(\mu ) \big )$$(r+O(μ))-dominating set D with $$|D| \le |D^*|$$|D|≤|D∗| efficiently. Here, $$D^*$$D∗ is a minimum (connected) r-dominating set of G and $$\mu $$μ is our graph parameter, which is the tree-breadth or the cluster diameter in a layering partition of G. Additionally, we show that a $$+ \mathcal {O}(\mu )$$+O(μ)-approximation for the (Connected) p-Center problem on G can be computed in polynomial time. Our interest in these parameters stems from the fact that in many real-world networks, including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others, and in many structured classes of graphs these parameters are small constants.

Arne Leitert, Feodor F. Dragan
Approximation Algorithms for Maximum Coverage with Group Budget Constraints

In this paper, we study the maximum coverage problem with group budget constraints (MCG) that generalizes the maximum coverage problem. Given a ground set U in which $$i\in U$$i∈U has a non-negative weight $$w_{i}$$wi, a positive integer k and a collection of sets $$\mathcal{S}$$S, the maximum coverage problem is to pick k sets of $$\mathcal{S}$$S to maximize the total weight of their union. In MCG, $$\mathcal{S}$$S is partitioned into groups $$\mathcal{G}_{1},\,\dots ,\,\mathcal{G}_{q}$$G1,⋯,Gq, and the goal is to pick k sets from $$\mathcal{S}$$S to maximize the total weight of their union, with at most $$n_{l}\in \mathbb {Z}_{0}^{+}$$nl∈Z0+ sets being picked from group $$\mathcal{G}_{l}$$Gl. For MCG with $$n_{l}=1$$nl=1, $$\forall l$$∀l, we first present a factor $$1-\frac{1}{e}$$1-1e approximation algorithm which runs in exponential time. Then we improve the runtime of the algorithm to $$O((m+n+q)^{3.5}L+k^{3.5}q^{7}L)$$O((m+n+q)3.5L+k3.5q7L) where $$\vert \mathcal{S}\vert =m$$|S|=m, $$\vert U\vert =n$$|U|=n, q is the number of groups, and L is the length of the input. The key idea of the improvement is to model selecting groups for MCG as computing a constrained flow in a corresponding auxiliary graph. It is also shown that the algorithm can be extended to solve MCG with general $$n_{l}$$nl. Later, based on the main idea of partition we further improve the runtime of the algorithm to $$O((m+n+q)^{3.5}L+k\delta ^{10.5}L)$$O((m+n+q)3.5L+kδ10.5L) , while compromise the approximation ratio to $$1-e^{\frac{1}{\delta }-1}$$1-e1δ-1, where $$\delta \ge 2$$δ≥2 is any fixed integer. Consequently, we can balance approximation ratio and runtime of the algorithm by setting the value of $$\delta $$δ. This improves the previous best ratio of 0.5 on MCG due to Chekuri and Kumar [4].

Longkun Guo, Min Li, Dachuan Xu

Application

Frontmatter
A Simple Greedy Algorithm for the Profit-Aware Social Team Formation Problem

Team formation in social networks has attracted much attention due to its many applications such as the online labour market. In this paper, we focus on the problem of forming multiple teams of experts with diverse skills in social network to accomplish complex tasks of required skills. The goal is to maximize the total profit of tasks that these teams can complete. We provide a simple and practical algorithm that improves upon previous results in many situations.

Shengxin Liu, Chung Keung Poon
Doctor Rostering in Compliance with the New UK Junior Doctor Contract

In 2016 the UK government imposed a new contract on junior doctors working for the country’s National Health Service. This new contract significantly changed the way in which hospitals and health trusts create rosters, introducing new constraints and a system of fines levied against employers should a doctor be required to work an undesirable or potentially unsafe shift pattern. In this paper, we present a new rostering problem set based upon this new junior doctor contract that models hospital departments varied in size, cover requirements, and contracted working patterns. We present the results of experiments in creating valid rosters for our problem set using a construction heuristic, and optimised using simulated annealing.

Anna Lavygina, Kris Welsh, Alan Crispin
Bounds for Static Black-Peg AB Mastermind

Mastermind is a famous two-player game introduced by M. Meirowitz (1970). Its combinatorics has gained increased interest over the last years for different variants.In this paper we consider a version known as the Black-Peg AB Game, where one player creates a secret code consisting of c colors on $$p \le c$$p≤c pegs, where each color is used at most once. The second player tries to guess the secret code with as few questions as possible. For each question he receives the number of correctly placed colors. In the static variant the second player doesn’t receive the answers one at a time, but all at once after asking the last question. There are several results both for the AB and the static version, but the combination of both versions has not been considered so far. The most prominent case is $$n:=p=c$$n:=p=c, where the secret code and all questions are permutations. The main result of this paper is an upper bound of $$\mathcal {O}(n^{1.525})$$O(n1.525) questions for this setting. With a slight modification of the arguments of Doerr et al. (2016) we also give a lower bound of $$\varOmega (n\log n)$$Ω(nlogn). Furthermore, we complement the upper bound for $$p=c$$p=c by an optimal $$(\lceil 4c/3 \rceil -1)$$(⌈4c/3⌉-1)-strategy for the special case $$p=2$$p=2 and arbitrary $$c\ge 2$$c≥2 and list optimal strategies for six additional pairs (p, c) .

Christian Glazik, Gerold Jäger, Jan Schiemann, Anand Srivastav
Classification Statistics in RFID Systems

Radio Frequency Identification (RFID) classification statistics problem is defined as classifying the tags into distinct groups and counting the quantity of tags in each group. The issue of time efficiency is significant in classification statistics, especially when the number of tags is large. In such case, the dilemma of short time requirement and massive tags makes traditional one-by-one identification methods impractical. This paper studies the problem of fast classification statistics in RFID systems. To address this problem, we propose a novel Twins Accelerating Gears (TAG) approach. One gear shortens the classification process in frequency domain through subcarrier allocation, when another gear accelerates the statistics process in time domain through geometric distribution based quantity estimation.

Zhenzao Wen, Jiapeng Huang, Linghe Kong, Min-You Wu, Guihai Chen
On the Complexity of Robust Stable Marriage

Robust Stable Marriage (RSM) is a variant of the classical Stable Marriage problem, where the robustness of a given stable matching is measured by the number of modifications required for repairing it in case an unforeseen event occurs. We focus on the complexity of finding an (a, b)-supermatch. An (a, b)-supermatch is defined as a stable matching in which if any a (non-fixed) men/women break up it is possible to find another stable matching by changing the partners of those a men/women and also the partners of at most b other couples. In order to show deciding if there exists an (a, b)-supermatch is $$\mathcal {NP}$$NP-complete, we first introduce a SAT formulation that is $$\mathcal {NP}$$NP-complete by using Schaefer’s Dichotomy Theorem. Then, we show the equivalence between the SAT formulation and finding a (1, 1)-supermatch on a specific family of instances.

Begum Genc, Mohamed Siala, Gilles Simonin, Barry O’Sullivan
The Euclidean Vehicle Routing Problem with Multiple Depots and Time Windows

This paper studies the Euclidean vehicle routing problem with multiple depots and time windows (Euclidean VRP with MDTW). We consider the scenario where there are multiple depots which could dispatch out vehicles, and customers must be serviced within a time window which is chosen from a finite set of consecutive time windows. Specially, in an input instance of Euclidean VRP with MDTW, we require that each customer has the same unit demand, ignore the limit of vehicle number, and give a reasonable service ability to the servicing vehicles. In quasi-polynomial time, our algorithm could generate a solution with the expected length at most $$(1 + O(\epsilon ))OPT$$(1+O(ϵ))OPT.

Liang Song, Hejiao Huang
Online Algorithms for Non-preemptive Speed Scaling on Power-Heterogeneous Processors

In this paper we consider non-preemptive online scheduling of jobs with release times and deadlines on heterogeneous processors with speed scaling. The power needed by processor i to run at speed s is assumed to be $$s^{\alpha _i}$$sαi, where the exponent $$\alpha _i$$αi is a constant that can be different for each processor. We require the jobs to have agreeable deadlines, i.e., jobs with later release times also have later deadlines. The aim is to minimize the energy used to complete all jobs by their deadlines. For the case where the densities of the jobs differ only within a factor of two and the same holds for their interval lengths, we present an algorithm with constant competitive ratio. For arbitrary densities and interval lengths, we achieve a competitive ratio that is poly-logarithmic in the ratio of maximum to minimum density and in the ratio of maximum to minimum interval length.

Aeshah Alsughayyir, Thomas Erlebach
An Efficient Algorithm for Judicious Partition of Hypergraphs

Judicious partition of hypergraphs $$\mathcal {H}$$H=(V, H) is to optimize several quantities simultaneously, and the goal of this paper is to partition the vertex set V into K parts: $$\{V_1,V_2,\dots ,V_K\}$${V1,V2,⋯,VK} so as to minimize the $$\max \{L(V_1),L_(V_2),\dots ,L(V_K)\}$$max{L(V1),L(V2),⋯,L(VK)}, where $$L(V_j)$$L(Vj) is the number of hyperedges incident to the part $$V_j(\mathcal {H})$$Vj(H). The bounds for the objective function are given and the relationship between the maximum hyperdegree and the objective value is analyzed. Before giving an efficient algorithm for the judicious partition of hypergraphs, a sub-problem is obtained, which is proved to be an unweighted set cover problem, apart from a tiny difference. A greedy algorithm is applied to solve the sub-problem. Last but not least, the judicious partition of hypergraphs is successfully divided into a series of sub-problems and an efficient algorithm is developed for the original problem.

Tunzi Tan, Jihong Gui, Sainan Wang, Suixiang Gao, Wenguo Yang
On Structural Parameterizations of the Matching Cut Problem

In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The matching cut problem is the problem of deciding whether a given graph has a matching cut. The matching cut problem can be expressed using a monadic second-order logic (MSOL) formula and hence is solvable in linear time for graphs with bounded tree-width. However, this approach leads to a running time of $$f(\phi , t) n^{O(1)}$$f(ϕ,t)nO(1), where $$\phi $$ϕ is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph.In [Theoretical Computer Science, 2016], Kratsch and Le asked to give a single exponential algorithm for the matching cut problem with tree-width alone as the parameter. We answer this question by giving a $$2^{O(t)} n^{O(1)}$$2O(t)nO(1) time algorithm. We also show the tractability of the matching cut problem when parameterized by neighborhood diversity and other structural parameters.

N. R. Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare
Longest Previous Non-overlapping Factors Table Computation

We examine the computation of the Longest Previous non-overlapping Factor (LPnF) table. The LPnF table is the table that stores the maximal length of factors re-occurring at each position of a string without overlapping. The LPnF table is related to well-known techniques for data compression, such as Ziv-Lempel factorization. This table is useful both for string algorithms and for text compression. In this paper, we present two algorithms to compute the LPnF table of a string: one from its augmented position heap and the other from its suffix heap. The proposed algorithms run in linear time with linear memory space.

Supaporn Chairungsee, Maxime Crochemore
Modeling and Verifying Multi-core Programs

To model and verify multi-core programs, this paper formalizes an operational semantics for Cylinder Computation Model (CCM). Further, the advantages of CCM over other concurrency models are highlighted. Moreover, the principle of programming with CCM is presented. In addition, a unified model checking approach in code level to verifying CCM programs is briefly demonstrated. Finally, an example is given to show how multi-core programs with CCM can be realized and verified.

Nan Zhang, Zhenhua Duan, Cong Tian, Hongwei Du, Kai Yang
Planar Vertex-Disjoint Cycle Packing: New Structures and Improved Kernel

The Maximum Cycle Packing problem is an important class of NP-hard problems, which has lots of applications in many fields. In this paper, we study Parameterized Planar Vertex-Disjoint Cycle Packing problem, which is to find k vertex-disjoint cycles in a given planar graph. The current best kernel size for this problem is $$1209k-1317$$1209k-1317. Based on properties of maximal cycle packing, small cycles, degree-2 paths, and new reduction rules given, a kernel of size $$415k-814$$415k-814 is presented for Parameterized Planar Vertex-Disjoint Cycle Packing problem.

Qilong Feng, Xiaolu Liao, Jianxin Wang
On the Linearization of Scaffolds Sharing Repeated Contigs

Scaffolding is the final step in assembling Next Generation Sequencing data, in which pre-assembled contiguous regions (“contigs”) are oriented and ordered using information that links them (for example, mapping of paired-end reads). As the genome of some species is highly repetitive, we allow placing some contigs multiple times, thereby generalizing established computational models for this problem. We study the subsequent problems induced by the translation of solutions of the model back to actual sequences, proposing models and analyzing the complexity of the resulting computational problems. We find both polynomial-time and $$\mathcal {NP}$$NP-hard special cases like planarity or bounded degree.

Mathias Weller, Annie Chateau, Rodolphe Giroudeau
A Memetic Algorithm for the Linear Ordering Problem with Cumulative Costs

Some optimization problems need to finding a permutation of a given set of items that minimizes a certain cost function. This paper introduces an effective memetic algorithm for the linear ordering problem with cumulative costs (LOPCC). The proposed algorithm combines an order-based recombination operator with an improved forward-backward local search procedure and employs a quality based replacement criterion for pool updating. Extensive experiments on 118 benchmark instances from the literature show that the proposed algorithm achieves competitive results by identifying 46 new upper bounds. Furthermore, some critical ingredients of our algorithm are analyzed to understand the source of its performance.

Taoqing Zhou, Zhipeng Lü, Tao Ye, Kan Zhou
Backmatter
Metadaten
Titel
Combinatorial Optimization and Applications
herausgegeben von
Xiaofeng Gao
Hongwei Du
Meng Han
Copyright-Jahr
2017
Electronic ISBN
978-3-319-71147-8
Print ISBN
978-3-319-71146-1
DOI
https://doi.org/10.1007/978-3-319-71147-8