Abstract On the Maximum Quadratic Assignment Problem (2009)
Viswanath Nagarajan, Maxim Sviridenko
Quadratic Assignment is a basic problem in combinatorial optimization, which generalizes several other problems such as Traveling Salesman, Linear Arrangement, Dense k Subgraph, and Clustering with...
Abstract Dynamic Pricing for Impatient Bidders (2009)
Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, Maxim Sviridenko
We study the following problem related to pricing over time. Assume there is a collection of bidders, each of whom is interested in buying a copy of an item of which there is an unlimited supply....
Non-monotone submodular maximization under matroid and knapsack constraints (2009)
Lee, Jon, Mirrokni, Vahab, Nagarjan, Viswanath, Sviridenko, Maxim
Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain...
Retsef Levi, Robin Roundy, David Shmoys, Maxim Sviridenko
Deterministic inventory theory provides streamlined optimization models that attempt to capture tradeoffs in managing the flow of goods through a supply chain. We will consider two well-studied...
Moshe Lewenstein, Maxim Sviridenko
Abstract The asymmetric maximum travelling salesman problem, also known as the Taxicab Ripoff problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with...
Retsef Levi, Andrea Lodi, Maxim Sviridenko
We study the classical capacitated multi-item lot-sizing problem with hard capacities. There are N items, each of which has specified sequence of demands over a finite planning horizon of T discrete...
Tight Bounds for Permutation Flow Shop Scheduling (2008)
Viswanath Nagarajan, Maxim Sviridenko
Abstract. In flow shop scheduling there are m machines and n jobs, such that every job has to be processed on the machines in the fixed order 1,..., m. In the permutation flow shop problem, it is...
Nikhil Bansal, Tracy Kimbrel, Maxim Sviridenko
Job shop scheduling with unit processing times
Static and Dynamic Hot-Potato Packet Routing in Communication Networks (2008)
David Gamarnik, Maxim Sviridenko
We consider a problem of scheduling packets in communication networks subject to the “hot potato ” restriction. In a static version, the problem is to route a set of packets in a communication...
Bundle pricing with comparable items (2008)
Er Grigoriev, Joyce Van Loon, Maxim Sviridenko, Marc Uetz, Tjark Vredeveld
Abstract. We consider a revenue maximization problem where we are selling a set of items, each available in a certain quantity, to a set of bidders. Each bidder is interested in one or several...
Abstract Dynamic Pricing for Impatient Bidders (2008)
Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, Maxim Sviridenko
We study the following problem related to pricing over time. Assume there is a collection of bidders, each of whom is interested in buying a copy of an item of which there is an unlimited supply....
Refael Hassin, Asaf Levin, Maxim Sviridenko
the minimum quadratic assignment problems
T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko
A web content hosting service provider needs to dynamically allocate servers in a server farm to its customers ’ web sites. Ideally, the allocation to a site should always suffice to handle its...
Optimal bundle pricing with monotonicity constraint (2008)
Grigoriev, Alexander, Loon, Joyce Van, Sviridenko, Maxim, Uetz, Marc, Vredeveld, Tjark
We consider the problem to price (digital) items in order to maximize the revenue obtainable from a set of bidders. We suggest a natural monotonicity constraint on bundle prices, show that the...
Buffer Overow Management in QoS Switches (2007)
Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-shamir, Baruch Schieber, Maxim Sviridenko
We consider two types of buffering policies that are used in network switches supporting QoS (Quality of Service). In the FIFO type, packets must be released in the order they arrive; the difculty in...
The diameter of a long-range percolation graph (2007)
David Gamarnik, Maxim Sviridenko
We consider the following long range percolation model: an undirected graph with the node set f0; 1; : : : ; Ng
Klaus Jansen, Roberto Solis-oba, Maxim Sviridenko
linear time approximation scheme for job shop scheduling
Klaus Jansen, Idsia Lugano, Roberto Solis-oba, Mpii Saarbrucken, Maxim Sviridenko
approximation schemes
Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-shamir, Baruch Schieber, Maxim Sviridenko
yx
Minimizing Makespan in No-Wait Job Shops (2007)
Nikhil Bansal, Mohammad Mahdian, Maxim Sviridenko
In this paper we study polynomial time approximation schemes (PTASes) for the no-wait job shop scheduling problem with the makespan objective function. It is known that the problem is MaxSNP-hard in...
Bin packing in multiple dimensions: Inapproximability results and approximation schemes (2006)
Nikhil Bansal, Claire Kenyon, Maxim Sviridenko
Abstract. We study the multidimensional generalization of the classical Bin Packing problem: Given a collection of d-dimensional rectangles of specified sizes, the goal is to pack them into the...
Tight approximation algorithms for maximum general assignment problems (2006)
Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko
A separable assignment problem (SAP) is defined by a set of bins and a set of items to pack in each bin; a value, fij, for assigning item j to bin i; and a separate packing constraint for each bin...
Tight approximation algorithms for maximum general assignment problems (2006)
Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko
A separable assignment problem (SAP) is defined by a set of bins and a set of items to pack in each bin; a value, fij, for assigning item j to bin i; and a separate packing constraint for each bin...
Bin packing in multiple dimensions: Inapproximability results and approximation schemes (2006)
Nikhil Bansal, José R. Correa, Claire Kenyon, Maxim Sviridenko
informs ® doi 10.1287/moor.1050.0168
Machine scheduling with resource dependent processing times (2005)
Grigoriev, Alexander, Sviridenko, Maxim, Uetz, Marc
We consider several parallel machine scheduling settings with the objective to minimize the schedule makespan. The most general of these settings is unrelated parallel machine scheduling. We assume...
Buffer Overflow Management in QoS Switches (2004)
Kesselmann,Alexander, Lotker,Zvi, Mansour,Yishay, Patt-Shamir,Boaz, Schieber,Baruch, Sviridenko,Maxim
Unrelated parallel machine scheduling with resource dependent processing times (2004)
Grigoriev, Alexander, Sviridenko, Maxim, Uetz, Marc
We consider machine scheduling problems where jobs have to be processed on unrelated parallel machines in order to minimize the schedule makespan. The processing time of any job is dependent on the...
Buffer Overflow Management in QoS Switches (2004)
Kesselmann, Alexander, Lotker, Zvi, Mansour, Yishay, Patt-Shamir, Boaz, Schieber, Baruch, Sviridenko, Maxim
Improved approximation algorithms for broadcast scheduling (2004)
Nikhil Bansal, Maxim Sviridenko
We consider two scheduling problems in the broadcast setting. The first is that of minimizing the average response time of requests. For the offline version of this problem we give an algorithm with...
Improved approximation algorithms for broadcast scheduling (2004)
Nikhil Bansal, Maxim Sviridenko, Nikhil Bansal, Maxim Sviridenko
been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be...
Further improvements in competitive guarantees for QoS buffering (2004)
Nikhil Bansal, Lisa K Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, Maxim Sviridenko
Abstract. We study the behavior of algorithms for buffering packets weighted by different levels of Quality of Service (QoS) guarantees in a single queue. Buffer space is limited, and packet loss...
Buffer Overflow Management in QoS Switches (2004)
Kesselmann, Alexander, Lotker, Zvi, Mansour, Yishay, Patt-Shamir, Boaz, Schieber, Baruch, Sviridenko, Maxim
Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs (2003)
Haim Kaplan, Nira Shafrir, Moshe Lewenstein, Maxim Sviridenko
A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall’s theorem one can represent such a multigraph as a combination of at most n 2 cycle...
A 5/8 approximation algorithm for the asymmetric maximum TSP (2002)
Moshe Lewenstein, Maxim Sviridenko
Abstract The Asymmetric Maximum Travelling Salesperson problem, also known as the Taxicab Ripoff problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with...
The diameter of a long range percolation graph (2001)
Coppersmith, Don, Gamarnik, David, Sviridenko, Maxim
We consider the following long range percolation model: an undirected graph with the node set $\{0,1,...,N\}^d$, has edges $(\x,\y)$ selected with probability $\approx \beta/||\x-\y||^s$ if...
Buffer overflow management in QoS switches (2001)
Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-shamir, Baruch Schieber, Maxim Sviridenko
Abstract. We consider two types of buffering policies that are used in network switches supporting Quality of Service (QoS). In the FIFO type, packets must be transmitted in the order in which they...
Online server allocation in a server farm via benefit task systems (Extended Abstract) (2001)
T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko
A web content hosting service provider needs to dynamically allocate servers in a server farm to its customers' web sites. Ideally, the allocation to a site should always suce to handle its...
Buffer overflow management in QoS switches (2001)
Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, Maxim Sviridenko
We consider two types of buffering policies that are used in network switches supporting QoS (Quality of Service). In the FIFO type, packets must be transmitted in the order they arrive; the...
Alexander Kesselman, Boaz Patt-shamir, Zvi Lotker, Baruch Schieber, Yishay Mansour, Maxim Sviridenko
We consider two types of buffering policies that are used in network switches supporting QoS (Quality of Service). In the FIFO type, packets must be released in the order they arrive; the difficulty...
New and Improved Algorithms for Minsum Shop Scheduling (2000)
Maurice Queyranne, Maxim Sviridenko
We consider a general class of multiprocessor shop scheduling problems with a minsum objective, and present approximation methods based on linear programming relaxations in the operation completion...
Approximating the Maximum Quadratic Assignment Problem (2000)
Esther M. Arkin, Refael Hassin, Maxim Sviridenko
this paper appeared in Proc. Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00), 889-890, January, 2000.
A 0.5-Approximation Algorithm For Max Dicut With Given Sizes Of Parts (2000)
Alexander Ageev, Refael Hassin, Maxim Sviridenko
Given a directed graph G and an arc weight function w : E(G) -> R+, the maximum directed cut problem (MAX DICUT) is that of finding a directed cut (X) with maximum total weight. In this paper we...
Approximation schemes for minimizing average weighted completion time with release dates (1999)
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation...
Makespan minimization in job shops: a polynomial time approximation scheme (1999)
Klaus Jansen, Idsia Lugano, Roberto Solis-oba, Mpii Saarbrucken, Maxim Sviridenko
approximation scheme
A linear time approximation scheme for the job shop scheduling problem (1999)
Klaus Jansen, Roberto Solis-oba, Maxim Sviridenko
Abstract. We study the preemptive and non-preemptive versions of the job shop scheduling problem when the number of machines and the number of operations per job are xed. We present linear time...
Approximation schemes for minimizing average weighted completion time with release dates (1999)
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation...
Makespan Minimization in Job Shops: A Linear Time Approximation Scheme (1999)
Klaus Jansen, Idsia Lugano, Roberto Solis-oba, Maxim Sviridenko
In this paper we present a linear time approximation scheme for the job shop scheduling problem with xed number of machines and xed number of operations per job. This improves on the previously best...
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates (1999)
Foto Afrati Evripidis, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation...
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates (1999)
Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, ...
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation...
Machine Scheduling with Resource Dependent Processing Times
Grigoriev,Alexander, Sviridenko,Maxim, Uetz,Marc
We consider several parallel machine scheduling settings with the objective to minimize the schedule makespan. The most general of these settings is unrelated parallel machine scheduling. We assume...
Unrelated parallel machine scheduling with resource dependent processing times
Grigoriev,Alexander, Sviridenko,Maxim, Uetz,Marc
We consider machine scheduling problems where jobs have to be processed on unrelated parallel machines in order to minimize the schedule makespan. The processing time of any job is dependent on the...
Approximating the Maximum Quadratic Assignment Problem
Esther M. Arkin, Refael Hassin, Maxim Sviridenko
this paper will appear, in Proc. Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00), January, 2000.