1,720,985 research outputs found
The asymptotic price of anarchy for k-uniform congestion games
Get PDFWe consider the atomic version of congestion games with affine cost functions, and analyze the quality of worst case Nash equilibria when the strategy spaces of the players are the set of bases of a k-uniform matroid. In this setting, for some parameter k, each player is to choose k out of a finite set of resources, and the cost of a player for choosing a resource depends affine linearly on the number of players choosing the same resource. Earlier work shows that the price of anarchy for this class of games is larger than 1.34 but at most 2.15. We determine a tight bound on the asymptotic price of anarchy equal to ≈1.35188. Here, asymptotic refers to the fact that the bound holds for all instances with sufficiently many players. In particular, the asymptotic price of anarchy is bounded away from 4/3. Our analysis also yields an upper bound on the price of anarchy <1.4131, for all instances
Approximationsalgorithmen für Packungs- und Scheduling-Probleme
Get PDFAlgorithms for solving optimization problems play a major role in the industry. For example in the logistics industry, route plans have to be optimized according to various criteria.
However, many natural optimization problems are hard to solve. That is, for many optimization problems no algorithms with running time polynomial in the size of the instance are known. Furthermore, it is a widely accepted assumption that many optimization problems do not allow algorithms that solve the problem optimally in polynomial time.
One way of overcoming this dilemma is using approximation algorithms. These algorithms have a polynomial running time, but their solutions are in general not optimal but rather close to an optimum.
The main subject of this thesis is approximation algorithms for packing and scheduling problems:
For the three-dimensional orthogonal knapsack problem (OKP-3) without rotations we present algorithms with approximation ratios arbitrarily close to 9, 8 and 7. For OKP-3 with 90 degree rotations around the z-axis or around all axes, we present algorithms with approximation ratios arbitrarily close to 6 and 5, respectively.
Both for the malleable and for the non-malleable case of the non-preemptive parallel job scheduling problem in which the number of available machines is polynomially bounded in the number of jobs, we present polynomial time approximation schemes. For the cases in which additionally the machines allotted to each job have to be contiguous, we show the existence of approximation algorithms with ratio arbitrarily close to 1.5
On the Approximation Complexity Hierarchy
No full textThis paper presents an extension of Ladner’s Theorem to the approximation complexity hierarchy. In 1975 Ladner proved that if P≠NP, then there exists an incomplete problem A which is neither in P nor NP-complete. Here we show that if RP≠NP, then there is a counting problem πA which neither has a fully polynomial randomised approximation scheme (FPRAS), nor is as hard to approximate as #SAT. This work is motivated by recent results showing that approximately counting H-colouring problems appears to fall into three complexity groups. Those problems which admit an FPRAS, those which are ‘AP-interreducible’ with #SAT and an intermediate class of problems all AP-interreducible with #BIS (counting independent sets in bipartite graphs). It has been asked whether this intermediate class in fact collapses into one of the former two classes, or whether it truly occupies some middle ground. Moreover, supposing it does occupy some middle ground, does it capture all the ground between? Our results reveal that there are counting problems whose approximation complexity lies between FPRASable and #SAT, under the assumption that NP≠RP. Indeed, there are infinitely many complexity levels between. Moreover we show that if #BIS is genuinely in the middle ground (neither having an FPRAS, nor as hard to approximate as #SAT), then there are problems that do not admit an FPRAS, are not equivalent in approximation complexity to #BIS and are not ‘AP-interreducible’ with #SAT, thus also occupy the middle ground. The proof is based upon Ladner’s original proof that there are classes between P and NP, and suffers the same drawback that the problems constructed are not natural. In particular our constructed problems are not H-colourings. The question of the approximation complexity of #BIS remains open
Algorithms for Integer Programming and Allocation
Get PDFThe first part of the thesis contains pseudo-polynomial algorithms for integer linear programs (ILP). When certain parameters of an ILP are fixed, that is, they are treated as constants in the running time, it is possible to obtain algorithms with a running time that is pseudo-polynomial in the entries of the ILP’s matrix. We present a tight pseudo-polynomial running time for ILPs with a constant number of constraints. Furthermore, we study an extension of this model to MILPs (linear programs that contain both fractional and integer variables). Then we move to n-fold ILPs, a class of ILPs with block structured matrices. We present the first algorithm for n-folds, which is near-linear in the dimensions of the ILP.
The second part is about scheduling in non-identical machine models, more precisely, restricted allocation problems. Here a set of jobs has to be allocated to a set of machines. However, every job has a subset of machines and may only be assigned to a machine from this subset. We consider the objectives of minimizing the makespan or maximizing the minimum load. We study the integrality gap of a particularly strong linear programming relaxation, the configuration LP, for variations of this problem. The integrality gap can be seen as a measure of strength of an LP relaxation. A local search technique can be used to bound this value. However, the proofs are generally non-constructive, i.e., they do not give an efficient approximation algorithm right away. We derive better upper bounds on the integrality gap of the problems Restricted Assignment, Restricted Santa Claus, and Graph Balancing. Furthermore, we give the first (constructive) quasi-polynomial time approximation algorithm for Restricted Assignment with an approximation ratio strictly less than 2.Der erste Teil der Thesis umfasst pseudopolynomielle Algorithmen für ganzzahlige lineare Programme (ILP). Wenn bestimmte Parameter eines ILPs fixiert sind, d.h. sie werden in der Laufzeit als Konstanten betrachtet, dann ist es möglich Algorithmen zu entwerfen, deren Laufzeit pseudopolynomiell in dem größten absoluten Wert eines Eintrags der Matrix des ILPs ist. Ein Ergebnis, das wir präsentieren, ist eine scharfe Schranke für die pseudopolynomielle Laufzeit, die nötig ist um ein ILP mit konstant vielen Bedingungen zu lösen. Danach befassen wir uns mit n-fold ILPs, eine Klasse von ILPs, deren matrix eine Blockstruktur besitzt. Wir geben den ersten Algorithmus für n-folds an, dessen Laufzeit gleichzeitig nahezu linear in der Dimension
des ILPs ist.
Der zweite Teil handelt von nicht-identischen (heterogenen) Maschinen Modellen, genauer gesagt restricted allocation problems. Hier soll eine Menge von Jobs auf eine Menge von Maschinen verteilt werden. Jeder Job darf aber nur auf bestimmte Maschinen zugewiesen werden. Wir betrachten als Zielfunktionen sowohl die Minimierung des Makespans als auch die Maximierung der minimalen Last einer Maschine. Wir untersuchen den integrality gap einer besonders starken LP Relaxierung, dem Konfigurations LP, für Variationen dieses Problems. Der integrality gap kann als Maß für die Stärke einer LP Relaxierung gesehen werden. Über ein Argument mittels einer lokalen Suche wird dieser Wert beschränkt. Jedoch sind die Beweise typischerweise nicht konstruktiv, d.h. sie implizieren nicht direkt effiziente Approximationsalgorithmen. Wir beweisen neue obere Schranken an den integrality gap für die Probleme Restricted Assignment, Restricted Santa Claus und Graph Balancing. Desweiteren präsentieren wir den ersten (konstruktiven) Quasipolynomialzeit Approximationsalgorithmus für das Restricted Assignment Problem mit Approximationsrate echt kleiner als 2
Robustness and approximation in combinatorial optimization
No full textThe robustness function of an optimization problem measures the maximum change in the value of its optimal solution that can be produced by changes of a given total magnitude on the values of the elements in its input. The problem of computing the robustness function of matroid optimization problems is studied under two cost models: the discrete model, which allows the removal of elements from the input, and the continuous model, which permits finite changes on the values of the elements in the input. For the discrete model, an -approximation algorithm is presented for computing the robustness function of minimum spanning trees, where k is the number of edges to be removed. The algorithm uses as key subroutine a 2-approximation algorithm for the problem of dividing a graph into the maximum number of components by removing k edges from it. For the continuous model, a number of results are presented. First, an algorithm is given for computing the robustness function of any matroid. The algorithm runs in strongly polynomial time on matroids with a strongly polynomial time independence test. Faster algorithms are also presented for some particular classes of matroids: (1) an O(n\sp3m\sp2\log(n\sp2/m))-time algorithm for graphic matroids, where m is the number of elements in the matroid and n is its rank, (2) an O(mn(m+n\sp2)\vert E\vert\log(m\sp2/\vert E\vert+2))-time algorithm for transversal matroids, where is a parameter of the matroid, (3) an O(m\sp2n\sp2)-time algorithm for scheduling matroids, and (4) an -time algorithm for partition matroids. For this last class of matroids an optimal algorithm is also presented for evaluating the robustness function at a single point. Two other bicriteria optimization problems are considered: (1) finding a rooted spanning tree of small weight and small sum of distances from the root to the other vertices in the tree, and (2) finding, in a graph with red and green edges, a minimum capacity cut in which the total capacity of the green edges is bounded by a given value. Several NP-hardness results and approximation algorithms are presented for these problems
Neighborhood-Preserving Mapping between Trees
No full textWe introduce a variation of the graph isomorphism problem, where, given two graphs G = (V,E) and G = (V,E) and three integers l, d, and k, we seek for a set ⊆ V and a one-to-one mapping f:V → V such that |D| ≤ k and for every vertex v ∈ V \ D and every vertex u ∈ N (v) \ D we have f(u) ∈ N (f(v)). Here, for a graph G and a vertex v, we use N(v) to denote the set of vertices which have distance at most i to v in G. We call this problem Neighborhood-Preserving Mapping (NPM). The main result of this paper is a complete dichotomy of the classical complexity of NPM on trees with respect to different values of l,d,k. Additionally, we present two dynamic programming algorithms for the case that one of the input trees is a path
On the Approximability of the Minimum Fundamental Cycle Basis Problem
No full textWe consider the problem of finding a fundamental cycle ba- sis of minimum total weight in the cycle space associated with an undi- rected biconnected graph G, where a nonnegative weight is assigned to each edge of G and the total weight of a basis is defined as the sum of the weights of all the cycles in the basis. Although several heuristics have been proposed to tackle this NP-hard problem, which has several interesting applications, nothing is known regarding its approximability. In this paper we show that this problem is MAXSNP-hard and hence does not admit a polynomial-time approximation scheme (PTAS) unless P=NP. We also derive the first upper bounds on the approximability of the problem for arbitrary and dense graphs. In particular, for complete graphs, it is approximable within 4 + ε , for any ε > 0
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
