Search

This paper considers combinatorial optimization problems with an objective of type bottleneck, so the objective is to minimize the maximum cost among all elements in a feasible solution. For these problems, the sensitivity of an optimal solution to changes in parameters has received much less attention in existing studies than the computation of an optimal solution. This paper introduces methods for computing upper and lower tolerances which measure the amount of cost change needed in an element inside and outside an optimal solution, respectively, before that solution becomes non-optimal. Our main contribution is the development of efficient computation methods for bottleneck versions of the Linear Assignment Problem and the Minimum Spanning Tree Problem. • We study sensitivity of combinatorial problems with bottleneck objective (CBPs). • We investigate the range of element costs that keep current solutions optimal. • We derive algorithms for two CBPs in particular. • We determine the elements belonging to optimal solutions of CBPs efficiently. [ABSTRACT FROM AUTHOR]

Motivated by some applications in communication networks of the diameter-constrained minimum spanning tree (Diamc-MST) problem, we address the delay-constrained minimum shortest path tree (Delayc-MSPT) problem, which is a variation of the Diamc-MST problem. Specifically, given a weighted graph G = (V , E ; w , c) and a constant d 0 , where n = | V | , m = | E | , length function w : E → R + and cost function c : E → R + , we are asked to determine a minimum shortest path tree among all shortest path trees (in G) whose delays are no more than d 0 , where the delay of a shortest path tree is the maximum distance (with respect to w (⋅)) from its source to every other leaf in that tree, and the cost of such a shortest path tree is the sum of costs of all edges (with respect to c (⋅)) in that tree. In addition, when a constant d 0 is the radius of G , we refer to this version of the Delayc-MSPT problem as the minimum radius minimum shortest path tree (MinRadius-MSPT) problem, and when a constant d 0 is the diameter of G , we refer to that version of the Delayc-MSPT problem as the maximum delay minimum shortest path tree (MaxDelay-MSPT) problem. In addition, we consider the diameter-constrained minimum shortest path tree (Diamc-MSPT) problem, except substituting the diameter for the delay of G in the Delayc-MSPT problem, where the diameter of a shortest path tree is the maximum distance (with respect to w (⋅)) between any two leaves in that tree. The main contribution of our paper is to show the following results. (1) We design an exact algorithm to solve the Delayc-MSPT problem and a similar exact algorithm to solve the MinRadius-MSPT problem, respectively, and these two algorithms run in time O (n 3) ; (2) We present an exact algorithm to solve the MaxDelay-MSPT problem, and that algorithm runs in time O (n 3) ; (3) We provide an exact algorithm to solve the special version of the Diamc-MSPT problem, where the constant d 0 is exactly the diameter of G , and that algorithm runs in time O (m n 2 + n 3 log ⁡ n). • We study the delay-constrained minimum shortest path tree problem and related problems. • The goal is to find a minimum shortest path tree whose delay is no more than d. • We design a polynomial-time algorithm to solve our problem. • we provide other polynomial-time algorithms to solve related problems. [ABSTRACT FROM AUTHOR]

The rooted Budgeted Cycle Cover (BCC) problem is a fundamental optimization problem arising in wireless sensor networks and vehicle routing. Given a metric space (V , w) with vertex set V consisting of two parts D (containing depots) and V ∖ D (containing nodes), and a budget B ≥ 0 , the rooted BCC problem asks to find a minimum number of cycles to cover all the nodes in V ∖ D , satisfying that each cycle has length at most B and each cycle must contain a depot in D. In this paper, we give new approximation algorithms for the rooted BCC problem. For the rooted BCC problem with single depot, we give an O (log ⁡ B μ) -approximation algorithm, where μ is the minimum difference of any two different distances between the vertices in V and the root. For the rooted BCC problem with multiple depots, we give an O (log ⁡ n) -approximation algorithm, where n is the number of vertices. We also test our algorithms on the randomly generated instances. The experimental results show that the algorithms have good performance in practice. • A log-factor approximation algorithm for the single depot budgeted cycle cover problem. • A log-factor approximation algorithm for the multi-depot budgeted cycle cover problem. • Experiments on randomly generated instances show good performance of the algorithms. [ABSTRACT FROM AUTHOR]

The Stop Number Problem arises in the management of a dial-a-ride system served by a fleet of autonomous electric vehicles. In such a system, clients request for a ride from an origin station to a destination station, and a fleet of capacitated vehicles must satisfy all requests. The goal is to minimize the number of pick-up/drop-off operations. In this paper we focus on a constrained unitary variant, called Unit Stop Number Problem, where each client requests for a single seat in the vehicles. This variant was recently conjectured to be NP-Hard. In this regard, we show how this problem relates to other problems known in the literature in order to derive some polynomial-time solvable variants. Moreover, we provide a positive answer to the conjecture by showing that the problem is NP-Hard for any fixed capacity greater than or equal to 2, even for the case where the graph of requests is restricted to the class of planar bipartite graphs. Our proof of NP-Hardness also improves the complexity results known in the literature for the related problems identified. [ABSTRACT FROM AUTHOR]

k -Clustering partitions a set of n points in a metric space into at most k clusters in a way that makes the resulted clusters satisfy both the homogeneity and the separation criteria. The diameter of a cluster is the maximum distance between pairs of points in the cluster, and the split of a cluster is the minimum distance between points of the cluster and ones outside the cluster. In this paper, we propose a new criterion for measuring the goodness of clusters: The ratio of the minimum cluster split to the maximum cluster diameter (abbr. RSD). We study the following two optimization problems: Maximizing RSD without and with cardinality constraints, i.e., each cluster should consist of at least N points. For both problems with k ≥ 3 , it is NP-hard to achieve a factor of (1 2 + ϵ) approximation for any ϵ > 0. For k = 2 , we solve the two problems optimally; For k ≥ 3 , we present a 1 2 -approximation and a 1 4 -approximation algorithm for the two problems, respectively. [ABSTRACT FROM AUTHOR]

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 − o (1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1 / 6 − ϵ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints. [ABSTRACT FROM AUTHOR]

The Minimum Spanning Tree problem (abbr. MSTP) is a well-known combinatorial optimization problem that has been extensively studied by the researchers in the field of evolutionary computing to theoretically analyze the optimization performance of evolutionary algorithms. Within the paper, we consider a constrained version of the problem named 2-Hop (1 , 2)-Minimum Spanning Tree problem (abbr. 2H-(1 , 2)-MSTP) in the context of evolutionary algorithms, which has been shown to be NP-hard. Following how evolutionary algorithms are applied to solve the MSTP, we first consider the evolutionary algorithms with search points in edge-based representation adapted to the 2H-(1 , 2)-MSTP (including the (1 + 1) EA, Global Simple Evolutionary Multi-Objective Optimizer and its two variants). More specifically, we separately investigate the upper bounds on their expected time (i.e., the expected number of fitness evaluations) to obtain a 3 2 -approximate solution with respect to different fitness functions. Inspired by the special structure of 2-hop spanning trees, we also consider the (1 + 1) EA with search points in vertex-based representation that seems not so natural for the problem and give an upper bound on its expected time to obtain a 3 2 -approximate solution, which is better than the above mentioned ones. [ABSTRACT FROM AUTHOR]

Rough set theory is a granular computing tool used to deal with ambiguity and uncertainty in information systems. However, many optimization problems in rough sets, such as attribute reduction, are NP-hard problems, and most of the algorithms for these problems are greedy. As a complex mathematical structure, matroids provide a powerful tool for solving combinatorial optimization problems related to attribute reduction. Therefore, it is necessary to study the combination of matroids and rough sets. This paper uses rough sets and matrix approaches to spanning matroids. Moreover, the features of spanning matroids are applied to attribute reduction in decision information systems. Firstly, we construct spanning sets based on equivalence relations which can induce matroids called spanning matroids. Secondly, some features of spanning matroids, such as closed sets, bases, are studied by matrix method. Finally, the judgment theorems with the features of spanning matroids are proposed for addressing the problems about attribute reduction in decision information systems. Simultaneously, the sufficient and necessary conditions for distinguishing upper approximation reduction in inconsistent decision information systems are obtained from the viewpoint of spanning matroids. [ABSTRACT FROM AUTHOR]

In an inverse combinatorial optimization problem, a feasible solution is given and is not optimal under the current parameters. The aim is to make the feasible solution optimal by modifying the current parameters as little as possible. The modification cost can be measured by different norms, such as weighted l 1 norm, weighted l 2 norm, weighted l ∞ norm, weighted Hamming distance and so on. In this paper, we focus on the constrained inverse minimum flow problems under the weighted Hamming distance. Three different models are considered: the general problem under the weighted bottleneck-type Hamming distance and two cases under the mixed of sum-type and bottleneck type. Strongly polynomial algorithms are presented for the models we studied. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of selfish bin packing with punishment. Different from the selfish bin packing problem proposed by Bilò in 2006, where the items are astute to minimize their shared proportional cost in a bin, we consider the case that items are into the utility defined as the load of bin it is packed in and, a unilateral moving may incur punishment. We define and consider several kinds of punishment, which can be roughly classified into two types: the punishment according to the behavior and the punishment based on the result. For both types we present the tight bound for Price of Anarchy (PoA) under the objective of minimizing the number of bins used. The results proved show that punishment does not always work, a punishment based on the result can be viewed as a delicate designed threat in advance which could perform much better, with an approximate 1.48 upper bound comparing to the optimal solution. • Initiate the consideration of punishment into the bin packing game. • Define three versions of punishment for the selfish bin packing problem. • Prove that punishment may not help to get better performance ratio. • Propose a dissuasive mechanism which could encourage agents to form a better equilibrium profile. [ABSTRACT FROM AUTHOR]

The grounded Laplacian matrix L − S of a graph G = (V , E) with n = | V | nodes and m = | E | edges is a (n − s) × (n − s) submatrix of its Laplacian matrix L , obtained from L by deleting rows and columns corresponding to s = | S | ≪ n ground nodes forming set S ⊂ V. The smallest eigenvalue of L − S plays an important role in various practical scenarios, such as characterizing the convergence rate of leader-follower opinion dynamics, with a larger eigenvalue indicating faster convergence of opinion. In this paper, we study the problem of adding k ≪ n edges among all the nonexistent edges forming the candidate edge set Q = (V × V) ﹨ E , in order to maximize the smallest eigenvalue of the grounded Laplacian matrix. We show that the objective function of the combinatorial optimization problem is monotone but non-submodular. To solve the problem, we first simplify the problem by restricting the candidate edge set Q to be (S × (V ﹨ S)) ﹨ E , and prove that it has the same optimal solution as the original problem, although the size of set Q is reduced from O (n 2) to O (n). Then, we propose two greedy approximation algorithms. One is a simple greedy algorithm with an approximation ratio (1 − e − α γ) / α and time complexity O (k n 4) , where γ and α are, respectively, submodularity ratio and curvature, whose bounds are provided for some particular cases. The other is a fast greedy algorithm without approximation guarantee, which has a running time O ˜ (k m) , where O ˜ (⋅) suppresses the poly (log ⁡ n) factors. Numerous experiments on various real networks are performed to validate the superiority of our algorithms, in terms of effectiveness and efficiency. [ABSTRACT FROM AUTHOR]

The sheer size of modern datasets has led to an urgent need for summarization techniques that can identify representative elements of the data set. Fortunately, the vast majority of data summarization tasks satisfy an intuitive diminishing returns condition known as submodularity, which allows us to find nearly-optimal solutions in linear time. However, for many applications in practice, including experimental design and sparse Gaussian processes, the objective is in general not submodular. To solve these optimization problems, an important research method is to describe the characteristics of the non-submodular functions. The non-submodular function is a hot research topic in the study of nonlinear combinatorial optimizations. In this paper, we combine and generalize the curvature and the generic submodularity ratio to design an approximation algorithm for two-stage non-submodular maximization under a matroid constraint. [ABSTRACT FROM AUTHOR]

Partitioning a network into k pieces is a fundamental problem in network science. A simple measure of partitioning a network is provided by the Max k -Uncut problem. Given an n -vertex undirected graph G with nonnegative weights defined on edges, and a positive integer k , the Max k -Uncut problem asks to find a k -partition of the vertices of G to maximize the total weight of edges that are not in the cut. This problem is the complement of the classic Min k -Cut problem, and has close relation to many combinatorial optimization problems, including the famous Densest k -Subgraph problem. In this paper, we propose a greedy approximation algorithm for the Max k -Uncut problem with performance ratio 1 − 2 (k − 1) n. The algorithm is very simple, which consists of only k − 1 min cut computations. The algorithm has fast running time O (k n 2) and is hence implementable. The experimental results show that the algorithm has excellent practical performance. [ABSTRACT FROM AUTHOR]

Popular matchings have been intensively studied recently as a relaxed concept of stable matchings. By applying the concept of popular matchings to branchings in directed graphs, Kavitha et al. introduced popular branchings. Let G = (V G , E G) be a directed graph, where each vertex has preferences over its incoming arcs, and B and B ′ be branchings in G. A vertex v ∈ V G prefers B to B ′ if v prefers its incoming arc of B to that of B ′ , where having an arbitrary incoming arc is preferred to having no incoming arc. We say that B is more popular than B ′ if the number of vertices preferring B to B ′ is greater than the number of vertices preferring B to B ′. A branching B is called a popular branching if there is no branching more popular than B. Kavitha et al. proposed an algorithm for finding a popular branching when the preferences of each vertex are given by a strict partial order. The correctness of this algorithm is proved by utilizing classical theorems on the duality of weighted arborescences. In this paper, we generalize popular branchings to weighted popular branchings in vertex-weighted directed graphs, in the same manner as weighted popular matchings by Mestre. We give an algorithm for finding a weighted popular branching for the case where the preferences of each vertex are given by a total preorder and the weights satisfy certain conditions. Our algorithm is based on Kavitha et al.'s algorithm, while it includes elaborated procedures resulting from the vertex-weights. Its correctness also builds upon the duality of weighted arborescences. [ABSTRACT FROM AUTHOR]