Maxim Sviridenko

According to our database1, Maxim Sviridenko authored at least 125 papers between 1999 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2019
On the computational complexity of the probabilistic label tree algorithms.
CoRR, 2019

Submodular Optimization with Contention Resolution Extensions.
Proceedings of the Approximation, 2019

2018
Energy-efficient scheduling and routing via randomized rounding.
J. Scheduling, 2018

Solving Optimization Problems with Diseconomies of Scale via Decoupling.
J. ACM, 2018

Integrated Supply Chain Management via Randomized Rounding.
INFORMS Journal on Computing, 2018

Matching Auctions for Search and Native Ads.
Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

2017
Maximizing Polynomials Subject to Assignment Constraints.
ACM Trans. Algorithms, 2017

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature.
Math. Oper. Res., 2017

Sponsored Search Auctions with Rich Ads.
Proceedings of the 26th International Conference on World Wide Web, 2017

Greedy Minimization of Weakly Supermodular Set Functions.
Proceedings of the Approximation, 2017

Determining Tournament Payout Structures for Daily Fantasy Sports.
Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments, 2017

2016
Inapproximability of the Multilevel Uncapacitated Facility Location Problem.
ACM Trans. Algorithms, 2016

Unrelated Machine Scheduling with Stochastic Processing Times.
Math. Oper. Res., 2016

No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem.
Math. Oper. Res., 2016

Submodular Stochastic Probing on Matroids.
Math. Oper. Res., 2016

Polynomial-Time Approximation Schemes for Circle and Other Packing Problems.
Algorithmica, 2016

Bidding Strategies for Fantasy-Sports Auctions.
Proceedings of the Web and Internet Economics - 12th International Conference, 2016

A Bi-Criteria Approximation Algorithm for k-Means.
Proceedings of the Approximation, 2016

An Algorithm for Online K-Means Clustering.
Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, 2016

2015
Approximation algorithms for the joint replenishment problem with deadlines.
J. Scheduling, 2015

Concentration inequalities for nonlinear matroid intersection.
Random Struct. Algorithms, 2015

Greedy Minimization of Weakly Supermodular Set Functions.
CoRR, 2015

New Approximations for Broadcast Scheduling via Variants of α-point Rounding.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm.
ACM Trans. Algorithms, 2014

Preemptive and non-preemptive generalized min sum set cover.
Math. Program., 2014

Optimization Problems with Diseconomies of Scale via Decoupling.
CoRR, 2014

Stochastic Scheduling on Unrelated Machines.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Polynomial-Time Approximation Schemes for Circle Packing Problems.
Proceedings of the Algorithms - ESA 2014, 2014

2013
Matroid Matching: The Power of Local Search.
SIAM J. Comput., 2013

A Harmonic Algorithm for the 3D Strip Packing Problem.
SIAM J. Comput., 2013

Supermodularity and Affine Policies in Dynamic Robust Optimization.
Operations Research, 2013

Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms.
Operations Research, 2013

Tight Bounds for Submodular and Supermodular Optimization with Bounded Curvature.
CoRR, 2013

Optimizing Maximum Flow Time and Maximum Throughput in Broadcast Scheduling.
CoRR, 2013

Approximating the Configuration-LP for Minimizing Weighted Sum of Completion Times on Unrelated Machines.
Proceedings of the Integer Programming and Combinatorial Optimization, 2013

An Efficient Polynomial-Time Approximation Scheme for the Joint Replenishment Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Large Neighborhood Local Search for the Maximum Set Packing Problem.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012
A Complete 4-parametric complexity classification of short shop scheduling problems.
J. Scheduling, 2012

Integer preemptive scheduling on parallel machines.
Oper. Res. Lett., 2012

Discretization orders for distance geometry problems.
Optimization Letters, 2012

A note on the Kenyon-Remila strip-packing algorithm.
Inf. Process. Lett., 2012

Concentration and moment inequalities for polynomials of independent random variables.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Inapproximability of the multi-level uncapacitated facility location problem.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

New and Improved Bounds for the Minimum Set Cover Problem.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Sum edge coloring of multigraphs via configuration LP.
ACM Trans. Algorithms, 2011

Tight Approximation Algorithms for Maximum Separable Assignment Problems.
Math. Oper. Res., 2011

Properties of optimal schedules in preemptive shop scheduling.
Discrete Applied Mathematics, 2011

2010
Dynamic pricing for impatient bidders.
ACM Trans. Algorithms, 2010

Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints.
SIAM J. Discrete Math., 2010

Submodular Maximization over Multiple Matroids via Generalized Exchange Properties.
Math. Oper. Res., 2010

2009
Approximating the minimum quadratic assignment problems.
ACM Trans. Algorithms, 2009

A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing.
SIAM J. Comput., 2009

Special Section On The Thirty-Ninth Annual ACM Symposium On Theory Of Computing (STOC 2007).
SIAM J. Comput., 2009

Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems.
Oper. Res. Lett., 2009

On the Maximum Quadratic Assignment Problem.
Math. Oper. Res., 2009

Tight Bounds for Permutation Flow Shop Scheduling.
Math. Oper. Res., 2009

Non-monotone submodular maximization under matroid and knapsack constraints.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Complete Complexity Classification of Short Shop Scheduling.
Proceedings of the Computer Science, 2009

Integrality Property in Preemptive Parallel Machine Scheduling.
Proceedings of the Computer Science, 2009

On Hardness of Pricing Items for Single-Minded Bidders.
Proceedings of the Approximation, 2009

2008
Minimum Makespan on Unrelated Machines.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs.
ACM Trans. Algorithms, 2008

Improved Approximation Algorithms for Broadcast Scheduling.
SIAM J. Comput., 2008

High-multiplicity cyclic job shop scheduling.
Oper. Res. Lett., 2008

Optimal bundle pricing with monotonicity constraint.
Oper. Res. Lett., 2008

Approximation Algorithms for the Capacitated Multi-Item Lot-Sizing Problem via Flow-Cover Inequalities.
Math. Oper. Res., 2008

A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem.
Management Science, 2008

Min Sum Edge Coloring in Multigraphs Via Configuration LP.
Proceedings of the Integer Programming and Combinatorial Optimization, 2008

2007
Machine scheduling with resource dependent processing times.
Math. Program., 2007

Inventory allocation and transportation scheduling for logistics of network-centric military operations.
IBM Journal of Research and Development, 2007

Two-dimensional bin packing with one-dimensional resource augmentation.
Discrete Optimization, 2007

Harmonic algorithm for 3-dimensional strip packing problem.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Approximation Algorithms for the Multi-item Capacitated Lot-Sizing Problem Via Flow-Cover Inequalities.
Proceedings of the Integer Programming and Combinatorial Optimization, 2007

Bundle Pricing with Comparable Items.
Proceedings of the Algorithms, 2007

Optimal bundle pricing for homogeneous items.
Proceedings of the Sixth Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2007

Test Machine Scheduling and Optimization for z/ OS.
Proceedings of the 2007 IEEE Symposium on Computational Intelligence in Scheduling, 2007

2006
Approximation algorithms for shop scheduling problems with minsum objective: A correction.
J. Scheduling, 2006

Minimizing migrations in fair multiprocessor scheduling of persistent tasks.
J. Scheduling, 2006

Job Shop Scheduling with Unit Processing Times.
Math. Oper. Res., 2006

Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes.
Math. Oper. Res., 2006

Dynamic placement for clustered web applications.
Proceedings of the 15th international conference on World Wide Web, 2006

The Santa Claus problem.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Tight approximation algorithms for maximum general assignment problems.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Improved approximation algorithms for multidimensional bin packing problems.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem.
Proceedings of the Approximation, 2006

LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times.
Proceedings of the Approximation, 2006

2005
An improved upper bound for the TSP in cubic 3-edge-connected graphs.
Oper. Res. Lett., 2005

Minimizing Makespan in No-Wait Job Shops.
Math. Oper. Res., 2005

Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs.
J. ACM, 2005

Hamiltonian completions of sparse random graphs.
Discrete Applied Mathematics, 2005

Dynamic Application Placement Under Service and Memory Constraints.
Proceedings of the Experimental and Efficient Algorithms, 4th InternationalWorkshop, 2005

Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times.
Proceedings of the Integer Programming and Combinatorial Optimization, 2005

A Tale of Two Dimensional Bin Packing.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004
Buffer Overflow Management in QoS Switches.
SIAM J. Comput., 2004

A note on maximizing a submodular set function subject to a knapsack constraint.
Oper. Res. Lett., 2004

Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee.
J. Comb. Optim., 2004

A Note on Permutation Flow Shop Problem.
Annals OR, 2004

Approximations for Maximum Transportation with Permutable Supply Vector and Other Capacitated Star Packing Problems.
Algorithmica, 2004

New approximability and inapproximability results for 2-dimensional Bin Packing.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Further Improvements in Competitive Guarantees for QoS Buffering.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003
Makespan Minimization in No-Wait Flow Shops: A Polynomial Time Approximation Scheme.
SIAM J. Discrete Math., 2003

A 5/8 Approximation Algorithm for the Maximum Asymmetric TSP.
SIAM J. Discrete Math., 2003

Makespan Minimization in Job Shops: A Linear Time Approximation Scheme.
SIAM J. Discrete Math., 2003

Approximating asymmetric maximum TSP.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

2002
The diameter of a long-range percolation graph.
Random Struct. Algorithms, 2002

A linear time approximation scheme for makespan minimization in an open shop with release dates.
Oper. Res. Lett., 2002

A (2+epsilon)-approximation algorithm for the generalized preemptive open shop problem with minsum objective.
J. Algorithms, 2002

Approximations for Maximum Transportation Problem with Permutable Supply Vector and Other Capacitated Star Packing Problems.
Proceedings of the Algorithm Theory, 2002

An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2002

2001
A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of Parts.
SIAM J. Discrete Math., 2001

Approximating the maximum quadratic assignment problem.
Inf. Process. Lett., 2001

Best Possible Approximation Algorithm for MAX SAT with Cardinality Constraint.
Algorithmica, 2001

Online server allocation in a server farm via benefit task systems.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000
Worst-case analysis of the greedy algorithm for a generalization of the maximum p-facility location problem.
Oper. Res. Lett., 2000

Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem.
Proceedings of the STACS 2000, 2000

New and improved algorithms for minsum shop scheduling.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Approximability and in-approximability results for no-wait shop scheduling.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

An Approximation Algorithm for Hypergraph Max k-Cut with Given Sizes of Parts.
Proceedings of the Algorithms, 2000

An approximation algorithm for MAX DICUT with given sizes of parts.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999
An 0.828-approximation Algorithm for the Uncapacitated Facility Location Problem.
Discrete Applied Mathematics, 1999

Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

A Linear Time Approximation Scheme for the Job Shop Scheduling Problem.
Proceedings of the Randomization, 1999

Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts.
Proceedings of the Integer Programming and Combinatorial Optimization, 1999

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999


  Loading...