Search results for "Approximation algorithm"
showing 10 items of 46 documents
Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes
2006
A multicoloring of a weighted graph G is an assignment of sets of colors to the vertices of G so that two adjacent vertices receive two disjoint sets of colors. A multicoloring problem on G is to find a multicoloring of G. In particular, we are interested in a minimum multicoloring that uses the least total number of colors. The main focus of this work is to obtain upper bounds on the weighted chromatic number of some classes of graphs in terms of the weighted clique number. We first propose an 11/6-approximation algorithm for multicoloring any weighted planar graph. We then study the multicoloring problem on powers of square and triangular meshes. Among other results, we show that the infi…
Online Hyperparameter Search Interleaved with Proximal Parameter Updates
2021
There is a clear need for efficient hyperparameter optimization (HO) algorithms for statistical learning, since commonly applied search methods (such as grid search with N-fold cross-validation) are inefficient and/or approximate. Previously existing gradient-based HO algorithms that rely on the smoothness of the cost function cannot be applied in problems such as Lasso regression. In this contribution, we develop a HO method that relies on the structure of proximal gradient methods and does not require a smooth cost function. Such a method is applied to Leave-one-out (LOO)-validated Lasso and Group Lasso, and an online variant is proposed. Numerical experiments corroborate the convergence …
Trunk Packing Revisited
2007
For trunk packing problems only few approximation schemes are known, mostly designed for the European standard DIN 70020 [6] with equally sized boxes [8, 9, 11, 12]. In this paper two discretized approaches for the US standard SAE J1100 [10] are presented, which make use of different box sizes. An exact branch-and-bound algorithm for weighted independent sets on graphs is given, using the special structure of the SAE standard. Another branch-and-bound packing algorithm using linear programs is presented. With these algorithms axis-oriented packings of different box sizes in an arbitrary trunk geometry can be computed efficiently.
Team Theory and Person-by-Person Optimization with Binary Decisions
2012
In this paper, we extend the notion of person-by-person (pbp) optimization to binary decision spaces. The novelty of our approach is the adaptation to a dynamic team context of notions borrowed from the pseudo-boolean optimization field as completely local-global or unimodal functions and submodularity. We also generalize the concept of pbp optimization to the case where groups of $m$ decisions makers make joint decisions sequentially, which we refer to as $m$b$m$ optimization. The main contribution is a description of sufficient conditions, verifiable in polynomial time, under which a pbp or an $m$b$m$ optimization algorithm converges to the team-optimum. As a second contribution, we prese…
On central algorithms of approximation under fuzzy information
2005
We consider the problem of approximation of an operator by information described by n real characteristics in the case when this information is fuzzy. We develop the well-known idea of an optimal error method of approximation for this case. It is a method whose error is the infimum of the errors of all methods for a given problem characterized by fuzzy numbers in this case. We generalize the concept of central algorithms, which are always optimal error algorithms and in the crisp case are useful both in practice and in theory. In order to do this we define the centre of an L-fuzzy subset of a normed space. The introduced concepts allow us to describe optimal methods of approximation for lin…
On Randomness and Structure in Euclidean TSP Instances: A Study With Heuristic Methods
2021
Prediction of the quality of the result provided by a specific solving method is an important factor when choosing how to solve a given problem. The more accurate the prediction, the more appropriate the decision on what to choose when several solving applications are available. In this article, we study the impact of the structure of a Traveling Salesman Problem instance on the quality of the solution when using two representative heuristics: the population-based Ant Colony Optimization (ACO) and the local search Lin-Kernighan (LK) algorithm. The quality of the result for a solving method is measured by the computation accuracy, which is expressed using the percent error between its soluti…
On the approximability of the range assignment problem on radio networks in presence of selfish agents
2005
AbstractWe consider the range assignment problem in ad-hoc wireless networks in the context of selfish agents: A network manager aims to assigning transmission ranges to the stations in order to achieve strong connectivity of the network within a minimal overall power consumption. Station is not directly controlled by the manager and may refuse to transmit with a certain transmission range because it might be costly in terms of power consumption.We investigate the existence of payment schemes which induce the stations to follow the decisions of a network manager in computing a range assignment, that is, truthful mechanisms for the range assignment problem. We provide both positive and negat…
Scheduling shared continuous resources on many-cores
2014
We consider the problem of scheduling a number of jobs on m identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement rj∈[0,1]. The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of r_j, it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature. In this paper, …
Edge Orientation and the Design of Problem-Specific Crossover Operators for the OCST Problem
2012
In the Euclidean optimal communication spanning tree problem, the edges in optimal trees not only have small weights but also point with high probability toward the center of the graph. These characteristics of optimal solutions can be used for the design of problem-specific evolutionary algorithms (EAs). Recombination operators of direct encodings like edge-set and NetDir can be extended such that they prefer not only edges with small distance weights but also edges that point toward the center of the graph. Experimental results show higher performance and robustness in comparison to EAs using existing crossover strategies.
ε-Regularized two-level optimization problems: Approximation and existence results
2006
The purpose of this work is to improve some results given in [12], relating to approximate solutions for two-level optimization problems. By considering an e-regularized problem, we get new properties, under convexity assumptions in the lower level problems. In particular, we prove existence results for the solutions to the e-regularized problem, whereas the initial two-level optimization problem may fail to have a solution. Finally, as an example, we consider an approximation method with interior penalty functions.