-
61
An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs
Published 2023-11-01“…We give an approximation algorithm for Quantum Max-Cut which works by rounding an SDP relaxation to an entangled quantum state. …”
Get full text
Article -
62
An Improved Approximation Algorithm for the Minimum Power Cover Problem with Submodular Penalty
Published 2022-10-01Subjects: Get full text
Article -
63
-
64
Structural rounding: Approximation algorithms for graphs near an algorithmically tractable class
Published 2020“…We develop a framework for generalizing approximation algorithms from the structural graph algorithm literature so that they apply to graphs somewhat close to that class (a scenario we expect is common when working with real-world networks) while still guaranteeing approximation ratios. …”
Get full text
Article -
65
-
66
A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees
Published 2005Subjects: Get full text
-
67
-
68
Nonlinear Formations and Improved Randomized Approximation Algorithms for Multiway and Multicut Problems
Published 2004Get full text
Working Paper -
69
Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
Published 2010“…Our structural results are motivated by the meta question: Suppose we are given a poly(log n) approximation algorithm for a flow or cut problem when can we give a poly(log k) approximation algorithm for a generalization of this problem to a Steiner cut or flow problem? …”
Get full text
Get full text
Article -
70
Approximation algorithms via structural results for apex-minor-free graphs
Published 2011“…We develop new structural results for apex-minor-free graphs and show their power by developing two new approximation algorithms. The first is an additive approximation for coloring within 2 of the optimal chromatic number, which is essentially best possible, and generalizes the seminal result by Thomassen [32] for bounded-genus graphs. …”
Get full text
Get full text
Article -
71
A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees
Published 2004Subjects: Get full text
-
72
-
73
-
74
Adaptive Galerkin approximation algorithms for partial differential equations in infinite dimensions
Published 2011“…All constants in our error and complexity bounds are shown to be independent of the number of "active" coordinates identified by the proposed adaptive Galerkin approximation algorithms.…”
Report -
75
-
76
Stochastic Approximate Algorithms for Uncertain Constrained <i>K</i>-Means Problem
Published 2022-01-01Subjects: “…stochastic approximate algorithms…”
Get full text
Article -
77
A Combinatorial Approximation Algorithm for the Vector Scheduling with Submodular Penalties on Parallel Machines
Published 2023-01-01“…Our main work is to design a 2−1/mminr,d-approximation algorithm to solve this problem. Here, r denotes the maximum ratio of the maximum load to the minimum load on the d-dimensional vectors among all jobs.…”
Get full text
Article -
78
Approximation Algorithms for Maximum Link Scheduling under SINR-Based Interference Model
Published 2015-07-01“…To date, several approximation algorithms have been proposed to solve MLS under the SINR-based interference model. …”
Get full text
Article -
79
Heuristic analysis of a near optimal approximation algorithm for the determination of investment options
Published 2009-02-01Get full text
Article -
80
APPLICATION OF THE SOFTWARE TOOLS EXPERIMENTAL DESIGN FOR THE GENETIC APPROXIMATION ALGORITHM PARAMETER OPTIMIZATION
Published 2010-08-01“…Experimental optimization of convergence rate of the genetic approximation algorithm accomplished with the application of the specialized scientific design of experiments software tools is described.…”
Get full text
Article