Approximation Algorithms

On two relaxations of quadratically-constrained cardinality minimization

  • Dennis Wei
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Branch and Cut Algorithms Tags , , , ,

    This paper considers a quadratically-constrained cardinality minimization problem with applications to digital filter design, subset selection for linear regression, and portfolio selection. Two relaxations are investigated: the continuous relaxation of a mixed integer formulation, and an optimized diagonal relaxation that exploits a simple special case of the problem. For the continuous relaxation, an absolute upper … Read more

    Algorithms for the Cross-dock Door Assignment Problem

  • Daniel Cardoso da Silva
  • Monique Guignard
  • Peter M. Hahn
  • Artur Alves Pessoa
    • Categories Applications - OR and Management Sciences, Approximation Algorithms, Transportation Tags , , ,

    In a cross-dock facility, goods are moved by forklift from incoming truck platforms (strip doors) to temporary holding areas and then to outgoing truck platforms (stack doors) or directly from strip doors to stack doors. Costs within the cross-dock may be minimized by appropriate assignment of strip doors to incoming trucks and stack doors to … Read more

    Moneyless strategy-proof mechanism on single-sinked policy domain: characterization and applications

  • Donglei Du
  • Qiaoming Han
    • Categories Approximation Algorithms, Game Theory Tags , , , , , , , ,

    We completely characterize deterministic strategy-proof and group strategy-proof mechanisms on single-sinked public policy domain. The single-sinked domain can be used to model any allocation problem where a single output must be chosen in an interval with the assumption that agents’ preferences have a single most loathful point (the sink) in the interval, and the preferences … Read more

    Simultaneous approximation of multi-criteria submodular function maximization

  • Donglei Du
  • Dachuan Xu
  • Naihua Xiu
  • Li Yu
    • Categories Approximation Algorithms, Game Theory, Multi-Criteria Optimization Tags , , ,

    Recently there has been intensive interest on approximation of the NP-hard submodular maximization problem due to their theoretical and practical significance. In this work, we extend this line of research by focusing on the simultaneous approximation of multiple submodular function maximization. We address existence and nonexistence results for both deterministic and randomized approximation when the … Read more

    A Constructive Proof of the Existence of a Utility in Revealed Preference Theory

  • J-P Crouzeix
  • Andrew C. Eberhard
  • Daniel Ralph
    • Categories Approximation Algorithms, Finance and Economics, Generalized Convexity/Monoticity Tags , ,

    Within the context of the standard model of rationality within economic modelling we show the existence of a utility function that rationalises a demand correspondence, hence completely characterizes the associated preference structure, by taking a dense demand sample. This resolves the problem of revealed preferences under some very mild assumptions on the demand correspondence which … Read more

    Improved approximation algorithms for the facility location problems with linear/submodular penalty

  • Donglei Du
  • Dachuan Xu
  • Naihua Xiu
  • Li Yu
    • Categories Approximation Algorithms Tags

    We consider the facility location problem with submodular penalty (FLPSP) and the facility location problem with linear penalty (FLPLP), two extensions of the classical facility location problem (FLP). First, we introduce a general algorithmic framework for a class of covering problems with submodular penalty, extending the recent result of Geunes et al. [12] with linear … Read more

    Joint Spectral Radius and Path-Complete Graph Lyapunov Functions

  • Amir Ali Ahmadi
  • Raphaël Jungers
  • Pablo A. Parrilo
  • Mardavij Roozbehani
    • Categories Approximation Algorithms, Control Applications, Semi-definite Programming Tags , , , , ,

    We introduce the framework of path-complete graph Lyapunov functions for approximation of the joint spectral radius. The approach is based on the analysis of the underlying switched system via inequalities imposed among multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of … Read more

    Joint Spectral Radius and Path-Complete Graph Lyapunov Functions

  • Amir Ali Ahmadi
    • Categories Approximation Algorithms, Control Applications, Semi-definite Programming Tags , , , , ,

    We introduce the framework of path-complete graph Lyapunov functions for approximation of the joint spectral radius. The approach is based on the analysis of the underlying switched system via inequalities imposed among multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of … Read more

    Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator

  • Lorenzo Orecchia
  • Sushant Sachdeva
  • Nisheeth K. Vishnoi
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , , ,

    We give a novel spectral approximation algorithm for the balanced separator problem that, given a graph G, a constant balance b \in (0,1/2], and a parameter \gamma, either finds an \Omega(b)-balanced cut of conductance O(\sqrt{\gamma}) in G, or outputs a certificate that all b-balanced cuts in G have conductance at least \gamma, and runs in … Read more

    A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined Into One

  • Shashi Mittal
  • Andreas S. Schulz
    • Categories Approximation Algorithms, Robust Optimization, Scheduling Tags , , ,

    In this paper, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two linear functions, parallel machine scheduling problems with the … Read more