查看更多>>摘要：? 2020 Elsevier B.V.An online algorithm is typically unaware of the length of the input request sequence that it is called upon. Consequently, it cannot determine whether it has already processed most of its input or whether the bulk of work is still ahead. In this paper, we are interested in whether some sort of orientation within the request sequence is nevertheless possible. For a real number 0<f<1, our objective is to preemptively guess the position fn within the request sequence of unknown length n: While processing the input, the online algorithm maintains a guess and is only allowed to update its guess to the position of the current element under investigation. We give a complete characterization of the optimal guessing strategies with respect to f: For f≤f0≈0.1867, the trivial algorithm that never updates its initial guess is (asymptotically) optimal. For f>f0, we give a randomized algorithm that in expectation places the guess at distance β(f)n from fn, where β is a non-elementary function, and we prove that this is optimal. Our findings show that the position fmaxn≈0.2847n is hardest to guess. We also give upper and lower bounds for a natural extension to weighted sequences. Our work can also be seen as the first randomized approach to the online checkpointing problem.
查看更多>>摘要：? 2020 Elsevier B.V.We represent a flow of a graph G=(V,E) as a couple (C,e) with C a circuit of G and e an edge of C, and its incidence vector is the 0/±1 vector χC?e?χe. The flow cone of G is the cone generated by the flows of G and the unit vectors. When G has no K5-minor, this cone can be described by the system x(M)≥0 for all multicuts M of G. We prove that this system is box-totally dual integral if and only if G is series–parallel. Then, we refine this result to provide the Schrijver system describing the flow cone in series–parallel graphs. This answers a question raised by Chervet et al., (2018).
查看更多>>摘要：? 2020 Elsevier B.V.In d-SCATTERED SET we are given an (edge-weighted) graph and are asked to select at least k vertices, so that the distance between any pair is at least d, thus generalizing INDEPENDENT SET. We provide upper and lower bounds on the complexity of this problem with respect to various standard graph parameters. In particular, we show the following: ? For any d≥2, an O?(dtw)-time algorithm, where tw is the treewidth of the input graph and a tight SETH-based lower bound matching this algorithm's performance. These generalize known results for INDEPENDENT SET. ? d-SCATTERED SET is W[1]-hard parameterized by vertex cover (for edge-weighted graphs), or feedback vertex set (for unweighted graphs), even if k is an additional parameter. ? A single-exponential algorithm parameterized by vertex cover for unweighted graphs, complementing the above-mentioned hardness. ? A 2O(td2)-time algorithm parameterized by tree-depth (td), as well as a matching ETH-based lower bound, both for unweighted graphs. We complement these mostly negative results by providing an FPT approximation scheme parameterized by treewidth. In particular, we give an algorithm which, for any error parameter ε>0, runs in time O?((tw/ε)O(tw)) and returns a d/(1+ε)-scattered set of size k, if a d-scattered set of the same size exists.
查看更多>>摘要：? 2020 Elsevier B.V.This work focuses on finding optimal locations for charging stations for one-way electric car sharing programs. The relocation of vehicles by a service staff is generally required in vehicle sharing programs in order to correct imbalances in the network. We seek to limit the need for vehicle relocation by strategically locating charging stations given estimates of traffic flow. A mixed-integer linear programming formulation is presented with a large number of potential charging station locations. A column generation approach is used which finds an optimal set of locations for the continuous relaxation of our problem. Results of a numerical experiment using real traffic and geographic information system location data show that our formulation significantly increases the balanced flow across the network, while our column generation technique was found to produce a superior solution in much shorter computation time compared to solving the original formulation with all possible station locations.
查看更多>>摘要：? 2020 Elsevier B.V.We study a Network Security question that consists of learning where are the most important checkpoints to intercept an adversary traveling from an origin to a destination. For that we define a cooperative game where every player controls an arc, and is able to place a checkpoint on it. We assume that the adversary is trying to travel from s to t. If the adversary crosses a checkpoint there is no certainty that he will be detected, therefore the value of a coalition should reflect the number of checkpoints, in the coalition, that the adversary has to cross (the more, the better). This suggests defining the value of a coalition S as the maximum number of disjoint st-cuts included in S; this is a lower bound for the number of checkpoints in S that the adversary has to cross. The adversary can choose any shortest path (minimum cardinality) from s to t, so in any particular coalition one cannot know the exact number of checkpoints that he will cross, and thus we propose to work with a lower bound instead. We give a polynomial combinatorial algorithm for computing the nucleolus of this game. The nucleolus is an allocation of resources to each arc that reflects the contribution of each checkpoint to the common objective of detecting the adversary. The larger values in the nucleolus indicate the more important locations.
查看更多>>摘要：? 2019 Elsevier B.V.This work is devoted to the study of the Lovász–Schrijver PSD-operator LS+ applied to the edge relaxation ESTAB(G) of the stable set polytope STAB(G) of a graph G. In order to characterize the graphs G for which STAB(G) is achieved in one iteration of the LS+-operator, called LS+-perfect graphs, an according conjecture has been recently formulated (LS+-Perfect Graph Conjecture). Here we study two graph classes defined by clique cutsets (pseudothreshold graphs and graphs without certain Truemper configurations). We completely describe the facets of the stable set polytope for such graphs, which enables us to show that one class is a subclass of LS+-perfect graphs, and to verify the LS+-Perfect Graph Conjecture for the other class.
查看更多>>摘要：? 2020 The Author(s)We study the Student-Project Allocation problem with lecturer preferences over Projects (SPA-P). In this context it is known that stable matchings can have different sizes and the problem of finding a maximum size stable matching is NP-hard. There are two known approximation algorithms for MAX-SPA-P, with performance guarantees 2 and [Formula presented]. We show that MAX-SPA-P is polynomial-time solvable if there is only one lecturer involved, and NP-hard to approximate within some constant c>1 if there are two lecturers involved. We also show that this problem remains NP-hard if each preference list is of length at most 3, with an arbitrary number of lecturers. We then describe an Integer Programming (IP) model to enable MAX-SPA-P to be solved optimally in the general case. Following this, we present results arising from an empirical evaluation that investigates how the solutions produced by the approximation algorithms compare to optimal solutions obtained from the IP model, with respect to the size of the stable matchings constructed, on instances that are both randomly-generated and derived from real datasets.
查看更多>>摘要：? 2020 Elsevier B.V.Scatter Search is an evolutionary metaheuristic introduced by Glover (1977) as a heuristic for integer programming and was joined with a directional rounding strategy for 0–1 Mixed Integer Programming (MIP) problems based on Star Paths in Glover (1995). In this paper, we address directional rounding both independently and together with these other algorithmic components, studying its properties as a mapping from continuous to discrete (binary) space. We establish several useful properties of directional rounding and show that it provides an extension of classical rounding and complementing operators. Moreover, we observe that directional rounding of a line, as embodied in a Star Path, contains a finite number of distinct 0–1 points. This property, together with those of the solution space of 0–1 MIP, enables us to organize the search for an optimal solution of 0–1 MIP problems using Scatter Search in association with both cutting plane and extreme point solution approaches. Building on this, we provide a Convergent Scatter Search algorithm for 0–1 Mixed Integer Programs with proof of its finite convergence, along with two variants of its implementation and examples that illustrate the running of the approach.
查看更多>>摘要：? 2021 Elsevier B.V.Classical Lagrangian relaxations for the multicommodity capacitated fixed-charge network design problem are the so-called flow and knapsack relaxations, where the resulting Lagrangian subproblems decompose by commodities and by arcs, respectively. We introduce node-based Lagrangian relaxations, where the resulting Lagrangian subproblem decomposes by nodes. We show that the Lagrangian dual bounds of these relaxations improve upon the linear programming relaxation bound, known to be equal to the Lagrangian dual bounds for the flow and knapsack relaxations. We also develop a Lagrangian matheuristic to compute upper bounds. The computational results on a set of benchmark instances show that the Lagrangian matheuristic is competitive with the state-of-the-art heuristics from the literature.
NSTL
Elsevier