-
作者：Chakrabarti, Amit; Kale, Sagar
作者单位：Dartmouth College
摘要：We study the problem of finding a maximum matching in a graph given by an input stream listing its edges in some arbitrary order, where the quantity to be maximized is given by a monotone submodular function on subsets of edges. This problem, which we call maximum submodular-function matching (MSM), is a natural generalization of maximum weight matching (MWM), which is in turn a generalization of maximum cardinality matching. We give two incomparable algorithms for this problem with space usag...
-
作者：Kaibel, Volker; Weltge, Stefan
作者单位：Otto von Guericke University
摘要：Let be the set of integer points in some polyhedron. We investigate the smallest number of facets of any polyhedron whose set of integer points is . This quantity, which we call the relaxation complexity of , corresponds to the smallest number of linear inequalities of any integer program having as the set of feasible solutions that does not use auxiliary variables. We show that the use of auxiliary variables is essential for constructing polynomial size integer programming formulations in man...
-
作者：Mnich, Matthias; Wiese, Andreas
作者单位：Max Planck Society
摘要：Fixed-parameter tractability analysis and scheduling are two core domains of combinatorial optimization which led to deep understanding of many important algorithmic questions. However, even though fixed-parameter algorithms are appealing for many reasons, no such algorithms are known for many fundamental scheduling problems. In this paper we present the first fixed-parameter algorithms for classical scheduling problems such as makespan minimization, scheduling with job-dependent cost function...
-
作者：Gupta, A.; Koenemann, J.; Leonardi, S.; Ravi, R.; Schaefer, G.
作者单位：Carnegie Mellon University; University of Waterloo; Sapienza University Rome; Centrum Wiskunde & Informatica (CWI); Vrije Universiteit Amsterdam
摘要：We consider the problem of designing efficient mechanisms to share the cost of providing some service to a set of self-interested customers. In this paper, we mainly focus on cost functions that are induced by prize-collecting optimization problems. Such cost functions arise naturally whenever customers can be served in two different ways: either by being part of a common service solution or by being served individually. One of our main contributions is a general lifting technique that allows ...
-
作者：Peng, Jiming; Zhu, Tao
作者单位：University of Houston System; University of Houston; University of Illinois System; University of Illinois Urbana-Champaign
摘要：In this paper, we consider the so-called worst-case linear optimization (WCLO) with uncertainties in the right-hand-side of the constraints. Such a problem arises from numerous applications such as systemic risk estimate in finance and stochastic optimization. We first show the problem is NP-hard and present a coarse semidefinite relaxation (SDR) for WCLO. An iterative procedure is introduced to sequentially refine the relaxation model based on the solution of the current relaxation model by s...
-
作者：Adjiashvili, David; Stiller, Sebastian; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Technical University of Berlin; Swiss Federal Institutes of Technology Domain; ETH Zurich; Johns Hopkins University
摘要：We commence an algorithmic study of Bulk-Robustness, a new model of robustness in combinatorial optimization. Unlike most existing models, Bulk-Robust combinatorial optimization features a highly nonuniform failure model. Instead of an interdiction budget, Bulk-Robust counterparts provide an explicit list of interdiction sets, comprising the admissible set of scenarios, thus allowing to model correlations between failures of different components in the system, interdiction sets of variable car...
-
作者：Golovin, Daniel; Goyal, Vineet; Polishchuk, Valentin; Ravi, R.; Sysikaski, Mikko
作者单位：Alphabet Inc.; Google Incorporated; Alphabet Inc.; Google Incorporated; University of Helsinki; Carnegie Mellon University
摘要：In this paper, we study the robust and stochastic versions of the two-stage min-cut and shortest path problems introduced in Dhamdhere et al. (in How to pay, come what may: approximation algorithms for demand-robust covering problems. In: FOCS, pp 367-378, 2005), and give approximation algorithms with improved approximation factors. Specifically, we give a 2-approximation for the robust min-cut problem and a 4-approximation for the stochastic version. For the two-stage shortest path problem, w...
-
作者：Lau, Lap Chi; Zhou, Hong
作者单位：Chinese University of Hong Kong
摘要：We present an approximation algorithm for the minimum bounded degree Steiner network problem that returns a Steiner network of cost at most two times the optimal and the degree on each vertex is at most , where is the maximum connectivity requirement and is the given degree bound on . This unifies, simplifies, and improves the previous results for this problem.
-
作者：Chatzipanagiotis, Nikolaos; Dentcheva, Darinka; Zavlanos, Michael M.
作者单位：Duke University; Stevens Institute of Technology
摘要：We propose a novel distributed method for convex optimization problems with a certain separability structure. The method is based on the augmented Lagrangian framework. We analyze its convergence and provide an application to two network models, as well as to a two-stage stochastic optimization problem. The proposed method compares favorably to two augmented Lagrangian decomposition methods known in the literature, as well as to decomposition methods based on the ordinary Lagrangian function.
-
作者：King, Douglas M.; Jacobson, Sheldon H.; Sewell, Edward C.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; Southern Illinois University System; Southern Illinois University Edwardsville
摘要：Graph partitioning is an intractable problem that arises in many practical applications. Heuristics such as local search generate good (though suboptimal) solutions in limited time. Such heuristics must be able to explore the solution space quickly and, when the solution space is constrained, differentiate feasible solutions from infeasible ones. Geographic zoning problems allocate some resource (e.g., political representation, school enrollment, police patrols) to contiguous zones modeled by ...
