| 1. |
- Bar-Noy, Amotz, et al.
(författare)
-
Online Maximum Directed Cut
- 2012
-
Ingår i: Journal of combinatorial optimization. - : Springer Science and Business Media LLC. - 1382-6905 .- 1573-2886. ; 24:1, s. 52-64
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate a natural online version of the well-known MAXIMUM DIRECTED CUT problem on DAGs. We propose a deterministic algorithm and show that it achieves a competitive ratio of 3 root 3/2 approximate to 2.5981. We then give a lower bound argument to show that no deterministic algorithm can achieve a ratio of 3 root 3/2 - epsilon for any epsilon > 0 thus showing that our algorithm is essentially optimal. Then, we extend our technique to improve upon the analysis of an old result: we show that greedily derandomizing the trivial randomized algorithm for MAXDICUT in general graphs improves the competitive ratio from 4 to 3, and also provide a tight example.
|
|
| 2. |
- Carling, Kenneth, et al.
(författare)
-
On statistical bounds of heuristic solutions to location problems
- 2016
-
Ingår i: Journal of combinatorial optimization. - : Springer Science and Business Media LLC. - 1382-6905 .- 1573-2886. ; 31:4, s. 1518-1549
-
Tidskriftsartikel (refereegranskat)abstract
- Solutions to combinatorial optimization problems, such as problems of locating facilities, frequently rely on heuristics to minimize the objective function. The optimum is sought iteratively and a criterion is needed to decide when the procedure (almost) attains it. Pre-setting the number of iterations dominates in OR applications, which implies that the quality of the solution cannot be ascertained. A small, almost dormant, branch of the literature suggests using statistical principles to estimate the minimum and its bounds as a tool to decide upon stopping and evaluating the quality of the solution. In this paper we examine the functioning of statistical bounds obtained from four different estimators by using simulated annealing on p-median test problems taken from Beasley’s OR-library. We find the Weibull estimator and the 2nd order Jackknife estimator preferable and the requirement of sample size to be about 10 being much less than the current recommendation. However, reliable statistical bounds are found to depend critically on a sample of heuristic solutions of high quality and we give a simple statistic useful for checking the quality. We end the paper with an illustration on using statistical bounds in a problem of locating some 70 distribution centers of the Swedish Post in one Swedish region.
|
|
| 3. |
- Damaschke, Peter, 1963
(författare)
-
Multiple hypernode hitting sets and smallest two-cores with targets
- 2009
-
Ingår i: Journal of Combinatorial Optimization. - : Springer Science and Business Media LLC. - 1573-2886 .- 1382-6905. ; 18:3, s. 294-306
-
Tidskriftsartikel (refereegranskat)abstract
- The multiple weighted hitting set problem is to find a subset of nodes in a hypergraph that hits every hyperedge in at least m nodes. We extend the problem to a notion of hypergraphs with so-called hypernodes and show that, for m=2, it remains fixed-parameter tractable (FPT), parameterized by the number of hyperedges. This is accomplished by a nontrivial extension of the dynamic programming algorithm for hypergraphs. The algorithm might be interesting for certain assignment problems, but here we need it as a tool to solve another problem motivated by network analysis: A d-core of a graph is a subgraph in which every vertex has at least d neighbors. We give an FPT algorithm that computes a smallest 2-core including a given set of target vertices, where the number of targets is the parameter. This FPT result is best possible in the sense that no FPT algorithm for 3-cores can be expected.
|
|
| 4. |
- Damaschke, Peter, 1963
(författare)
-
Parameterizations of hitting set of bundles and inverse scope
- 2015
-
Ingår i: Journal of Combinatorial Optimization. - : Springer Science and Business Media LLC. - 1573-2886 .- 1382-6905. ; 29:4, s. 847-855
-
Tidskriftsartikel (refereegranskat)abstract
- Hitting Set of Bundles generalizes the ordinary Hitting Set problem in the way that prescribed bundles of elements rather than single elements have to be put in a hitting set. The goal is to minimize the total number of distinct elements in the solution. First we prove that Hitting Set of Bundles, with the number of hyperedges and the solution size as parameter, is W[1]-complete. This contrasts to the to the corresponding parameterized Hitting Set version which is in FPT. Then we use this result to prove W[i]-hardness also for the Inverse Scope problem and some of its variants. This problem asks to identify small sets of chemical reactants being able to produce a given set of target compounds in a network of reactions. The problem has a graph-theoretic formulation as a reachability problem in directed graphs. On the positive side, we give an FPT algorithm where the parameter is the total number of compounds involved in the reactions.
|
|
| 5. |
- Damaschke, Peter, 1963
(författare)
-
Parameterized mixed graph coloring
- 2019
-
Ingår i: Journal of Combinatorial Optimization. - : Springer Science and Business Media LLC. - 1573-2886 .- 1382-6905. ; 38:2, s. 362-374
-
Tidskriftsartikel (refereegranskat)abstract
- Coloring of mixed graphs that contain both directed arcs and undirected edges is relevant for scheduling of unit-length jobs with precedence constraints and conflicts. The classic GHRV theorem (attributed to Gallai, Hasse, Roy, and Vitaver) relates graph coloring to longest paths. It can be extended to mixed graphs. In the present paper we further extend the GHRV theorem to weighted mixed graphs. As a byproduct this yields a kernel and a parameterized algorithm (with the number of undirected edges as parameter) that is slightly faster than the brute-force algorithm. The parameter is natural since the directed version is polynomial whereas the undirected version is NP-complete. Furthermore we point out a new polynomial case where the edges form a clique.
|
|
| 6. |
- El Ouali, Mourad, et al.
(författare)
-
An approximation algorithm for the partial vertex cover problem in hypergraphs
- 2016
-
Ingår i: Journal of combinatorial optimization. - : SPRINGER. - 1382-6905 .- 1573-2886. ; 31:2, s. 846-864
-
Tidskriftsartikel (refereegranskat)abstract
- Let be a hypergraph with set of vertices and set of (hyper-)edges . Let be the maximum size of an edge, be the maximum vertex degree and be the maximum edge degree. The -partial vertex cover problem in hypergraphs is the problem of finding a minimum cardinality subset of vertices in which at least hyperedges are incident. For the case of and constant it known that an approximation ratio better than cannot be achieved in polynomial time under the unique games conjecture (UGC) (Khot and Ragev J Comput Syst Sci, 74(3):335-349, 2008), but an -approximation ratio can be proved for arbitrary (Gandhi et al. J Algorithms, 53(1):55-84, 2004). The open problem in this context has been to give an -ratio approximation with , as small as possible, for interesting classes of hypergraphs. In this paper we present a randomized polynomial-time approximation algorithm which not only achieves this goal, but whose analysis exhibits approximation phenomena for hypergraphs with not visible in graphs: if and are constant, and , we prove for -uniform hypergraphs a ratio of , which tends to the optimal ratio 1 as tends to . For the larger class of hypergraphs where , is not constant, but is a constant, we show a ratio of . Finally for hypergraphs with non-constant , but constant , we get a ratio of for , leaving open the problem of finding such an approximation for k < m/4(.)
|
|
| 7. |
- Jäger, Gerold, et al.
(författare)
-
Improved Approximation Algorithms for Maximum Graph Partitioning Problems
- 2005
-
Ingår i: Journal of combinatorial optimization. - : Kluwer Academic Publishers. - 1382-6905 .- 1573-2886. ; 10:2, s. 133-167
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the design of approximation algorithms for a number of maximum graph partitioning problems, among others MAX-k-CUT, MAX-k-DENSE-SUBGRAPH, and MAX-k-DIRECTED-UNCUT. We present a new version of the semidefinite relaxation scheme along with a better analysis, extending work of Halperin and Zwick (2002). This leads to an improvement over known approximation factors for such problems. The key to the improvement is the following new technique: It was already observed by Han, Ye, Zhang (2002) that a parameter-driven choice of the random hyperplane can lead to better approximation factors than obtained by Goemans and Williamson (1995). But it remained difficult to find a ”good” set of parameters. In this paper, we analyze random hyperplanes depending on several new parameters. We prove that a suboptimal choice of these parameters can be obtained by the solution of a linear program which leads to the desired improvement of the approximation factors. In this fashion a more systematic analysis of the semidefinite relaxation scheme is obtained.
|
|
| 8. |
- Lingas, Andrzej, et al.
(författare)
-
Graphs with equal domination and covering numbers
- 2020
-
Ingår i: Journal of Combinatorial Optimization. - : Springer Science and Business Media LLC. - 1382-6905 .- 1573-2886. ; 39:1, s. 55-71
-
Tidskriftsartikel (refereegranskat)abstract
- A dominating set of a graph G is a set D⊆ VG such that every vertex in VG- D is adjacent to at least one vertex in D, and the domination number γ(G) of G is the minimum cardinality of a dominating set of G. A set C⊆ VG is a covering set of G if every edge of G has at least one vertex in C. The covering number β(G) of G is the minimum cardinality of a covering set of G. The set of connected graphs G for which γ(G) = β(G) is denoted by Cγ = β, whereas B denotes the set of all connected bipartite graphs in which the domination number is equal to the cardinality of the smaller partite set. In this paper, we provide alternative characterizations of graphs belonging to Cγ = β and B. Next, we present a quadratic time algorithm for recognizing bipartite graphs belonging to B, and, as a side result, we conclude that the algorithm of Arumugam et al. (Discrete Appl Math 161:1859–1867, 2013) allows to recognize all the graphs belonging to the set Cγ = β in quadratic time either. Finally, we consider the related problem of patrolling grids with mobile guards, and show that it can be solved in O(nlog n+ m) time, where n is the number of line segments of the input grid and m is the number of its intersection points.
|
|
| 9. |
- Marinakis, Yannis, et al.
(författare)
-
A hybrid genetic-GRASP algorithm using Lagrangean relaxation for the traveling salesman problem
- 2005
-
Ingår i: Journal of combinatorial optimization. - : Springer Science and Business Media LLC. - 1382-6905 .- 1573-2886. ; 10:4, s. 311-326
-
Tidskriftsartikel (refereegranskat)abstract
- Hybridization techniques are very effective for the solution of combinatorial optimization problems. This paper presents a genetic algorithm based on Expanding Neighborhood Search technique (Marinakis, Migdalas, and Pardalos, Computational Optimization and Applications, 2004) for the solution of the traveling salesman problem: The initial population of the algorithm is created not entirely at random but rather using a modified version of the Greedy Randomized Adaptive Search Procedure. Farther more a stopping criterion based on Lagrangean Relaxation is proposed. The combination of these different techniques produces high quality solutions. The proposed algorithm was tested on numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the algorithms of the DIMACS Implementation Challenge are also presented
|
|
| 10. |
- Marinakis, Yannis, et al.
(författare)
-
Multiple phase neighborhood Search-GRASP based on Lagrangean relaxation, random backtracking Lin-Kernighan and path relinking for the TSP
- 2009
-
Ingår i: Journal of combinatorial optimization. - : Springer Science and Business Media LLC. - 1382-6905 .- 1573-2886. ; 17:2, s. 134-156
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper, a new modified version of Greedy Randomized Adaptive Search Procedure (GRASP), called Multiple Phase Neighborhood Search-GRASP (MPNS-GRASP), is proposed for the solution of the Traveling Salesman Problem. In this method, some procedures have been included to the classical GRASP algorithm in order to improve its performance and to cope with the major disadvantage of GRASP which is that it does not have a stopping criterion that will prevent the algorithm from spending time in iterations that give minor, if any, improvement in the solution. Thus, in MPNS-GRASP a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is proposed. Also, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. A new variant of the Lin-Kernighan algorithm, called Random Backtracking Lin-Kernighan that helps the algorithm to diversify the search in non-promising regions of the search space is used in the Expanding Neighborhood Search phase of the algorithm. Finally, a Path Relinking Strategy is used in order to explore trajectories between elite solutions. The proposed algorithm is tested on numerous benchmark problems from TSPLIB with very satisfactory results
|
|
